You need a browser with Java support to see this applet.

is een spel bedacht door Christian Freeling. Java applet © 1997 Ed van Zon.

Caïssa is een soort schaakspel dat voor het eerst werd gepubliceerd op www.mindsports.net. Kijk hier voor de spelregels. Ik heb met een eigen versie meegedaan aan de CodeCup 2003. Mijn programma heet HIPP en is gemaakt in C. Je kunt een projectversie downloaden en bekijken (Engels gedocumenteerd). Voor het berekenen van de beste zet maakt HIPP gebruik van het MTD(f) algoritme. Dit algoritme maakt gebruik van het constant aanroepen van alfabeta schrappen (zonder geheugenfunctie) met een zogenaamde zero-window search. Het bereik van de evaluatiefunctie heb ik beperkt van -25 tot 25 om het aantal aanroepen te verminderen. Het algoritme wordt iteratief aangeroepen waarbij steeds een niveau dieper wordt doorgerekend. In het begin is het niet nodig om de verbindingsregel te controleren en zoekt HIPP vier niveau's diep. In het eindspel waarbij de verbindingsregel wel gecontroleerd moet worden neemt HIPP drie niveau's diep. Na het sorteren van deze zetten rekent HIPP de beste vijf zetten één niveau dieper door. Door gebruik te maken van een snelle zettengenerator vindt HIPP per stelling in het beginspel in totaal ± 3 miljoen zetten. Er worden daarvan 30.000 zetten uitgevoerd en worden er 27.000 stellingen gewaardeerd. Dat duurt ± 3 seconden. Ik heb nog meer ideeën verwerkt die ik beschreven heb in een PDF-document. Dit Engelstalige document kan je downloaden, afdrukken en lezen. Een samenvatting daarvan:

  1. Wanneer in een bepaalde situatie schaak wordt gegeven, rekent HIPP vanaf dat punt altijd een extra niveau dieper door omdat het aantal tegenzetten in zo'n situatie beperkt is. Ook wanneer er in de beginstelling slechts twee of drie zetten zijn wordt er één niveau dieper doorgerekend. Daardoor is een matsituatie soms al op tien niveau's diep te vinden. Op die manier schat ik in dat HIPP effectief zes á zeven zetten diep kijkt.
  2. De basis van mijn evaluatiefunctie is simpel en dus snel: Waarde = AantalZettenVanMijzelf - AantalZettenVanTegenstander. Hiervoor wordt het aantal zetten van de tegenstander vanuit het aangeroepen niveau gebruikt. Dat heeft als voordeel dat als hij schaak staat, dat het in mijn voordeel werkt!
  3. De eerste vier zetten van wit en de eerste drie zetten van zwart zijn van tevoren doorgerekend. Het maken van het openingenboek heeft ongeveer drie weken geduurd op een 850 MHz-machine. Het meer dan tien zetten diep doorrekenen waarborgt een veilige, snelle en kansrijke opening.