[Wedstrijd] CodeCup 2026 - 0.1 (Zero Point One)

[Joep]

De CodeCup is een jaarlijkse programmeerwedstrijd, ontstaan uit de Nederlandse Informatica Olympiade, waarbij deelnemers een programma schrijven dat een spel kan spelen. Die programma's nemen het dan tegen elkaar op in een toernooi.

Het spel van dit jaar heet 0.1 (Zero Point One) dat erg veel weg heeft van een vroege versie van schaken. De belangrijkste verschillen met schaken zijn de andere "schaak"-stukken, het feit dat je ze bij aanvang van het spel zelf op het bord mag plaatsen en het feit dat je verslagen schaakstukken op het bord mag terugplaatsen als eigen schaakstuk.



Voorbeeld van het spelverloop. Voor details, lees de volledige regels op de CodeCup site.

Technische details

Om mee te doen moet je een speler schrijven in één van de ondersteunde programmeertalen: C, C++, C#, Go, Haskell, Java, JavaScript, OCaml, Pascal, Python of Rust.

Je programma mag per potje maximaal 30 seconde CPU-tijd gebruiken op een 2 GHz CPU (geen multithreading), en maximaal 2 GB geheugen. Zie verder de technische details op de CodeCup site.

Lokaal testen

Voordat je je programma instuurt, kun je lokaal testen dat je aan het spelprotocol voldoet. Daarvoor stelt de organisatie een tool genaamd Caia ter beschikking. Ook zitten er drie testspelers in de Caia distributie. Die zijn heel handig om je speler te verbeteren.

Belangrijke data

De finale is op zaterdag 14 januari 2026. Dat is nog ver weg. Tot die tijd is er elke drie weken een testcompetitie, waarvan de eerste op zaterdag 20 september 2024 plaatsvond.

De testcompetities zijn nuttig om te verifiëren dat je programma correct werkt in het CodeCup systeem, en om uit te vinden hoe sterk je speler is vergeleken met die van andere deelnemers.

[Joep]

Gereserveerd.

[Bolukan]

Dank Joep voor de post.

Ik heb er even naar zitten kijken en vraag me af of dit oplosbaar is zonder AI? (Daar zit niet mijn kracht). Kortom, aan anderen de vraag: hoe stel je hier vast wat de passende aanpak is?

Ik tel 16!/(8! 4! 2! 1! 1!) 10.810.800 begin opstellingen. Het aantal lijkt me niet relevant, want je kunt daar vooronderzoek naar doen. Het lijkt op Stratego waar mensen hun voorkeurs-opstellingen hebben.Misschien kan je je opening nog optimaliseren op de voorkeuren van de tegenstanders.

De 8 Alfils/'pionnen' die 2/2 kunnen springen, lijken op het eerste zich heel krachtig, maar bewegen zich in 8 verschillende sets van cellen, net zoals lopers bij schaken niet kunnen wisselen tussen 2 sets de zwarte en witte vlakken.

Bruto heb je met de initiele set stukken een upperbound van 68 opties voor een zet (1x4+1x8+2x4+4x4+8x4). Gecorrigeerd voor niet over de rand van het bord springen, breng je het terug naar gemiddeld 45 opties en met niet op elkaar springen=je eigen stuk slaan, wordt het nog lager. Het neerzetten van een eerder geslagen stuk verhoogt het aantal opties echter weer enorm. De voorlopige conclusie is dat brute force geen optie lijkt. Maar bruto forcen van de laatste zetten rond het bijna "schaakmat" zetten met de nabije stukken, sluit ik niet uit.

[Soultaker]

Bolukan schreef op zondag 28 september 2025 @ 13:29:
Ik heb er even naar zitten kijken en vraag me af of dit oplosbaar is zonder AI? (Daar zit niet mijn kracht). Kortom, aan anderen de vraag: hoe stel je hier vast wat de passende aanpak is?

Het spel is niet volledig oplosbaar, net zoals b.v. het schaakspel dat niet is.

De competitie zou niet interessant zijn als iedereen optimaal speelt. De uitdaging is om een zo sterk mogelijke speler te bouwen gegeven de tijd- en geheugenlimieten.

Aangezien het spel lijkt op schaken, kun je ook vergelijkbare algoritmen gebruiken. Daar zijn heel veel mogelijkheden voor, maar de bekendste methoden zijn gebaseerd op minimax game tree search, en
Monte Carlo tree search (MCTS).

Ik zou bij minimax beginnen; dat is eenvoudiger te begrijpen, hoewel het in zekere zin lastiger te implementeren is, omdat je zowel de zoekroutine moet schrijven, als een evaluatie-functie voor een willekeurige positie, terwijl je bij (de basisvariant van) MCTS alleen een stelling hoeft uit te spelen totdat de wazir (koning) geslagen is.

Beide algoritmen kun je verder nog enorm veel verbeteren. Bijvoorbeeld, voor minimax search kun je gebruik maken van transposition tables om identieke stellingen die via meerdere paden bereikt kunnen worden te elimineren, en bij MCTS kun je heuristieken gebruiken om random playouts realistischer te maken.

Ik tel 16!/(8! 4! 2! 1! 1!) 10.810.800 begin opstellingen.

Goed gezien. Voor de eerste zet kun je die nog delen door twee, vanwege de horizontale symmetrie van het spel.

De 8 Alfils/'pionnen' die 2/2 kunnen springen, lijken op het eerste zich heel krachtig, maar bewegen zich in 8 verschillende sets van cellen, net zoals lopers bij schaken niet kunnen wisselen tussen 2 sets de zwarte en witte vlakken.

Klopt, en dit geldt voor alle stukken: je hebt precies evenveel stukken van een type dat nodig is om het hele bord te kunnen bereiken.

De dabbaba's, die twee velden horizontaal of verticaal kunnen springen, kunnen 1 van 4 sets van velden bereiken, dus heb je er 4 van. De Ferzes die 1 stap diagonaal zetten, zijn net als lopers gebonden aan de zwarte of witte velden, en dus heb je er 2. De wazir (koning) en paard kunnen beiden alle vakjes bereiken dus heb je er 1.

[Soultaker]

Wie het spel uit wil proberen, kan dat via mijn website doen.

(Je kunt tegen jezelf spelen, of tegen een ander door een speler-link te delen, of tegen een van de 3 voorbeeldspelers uit de Caia-distributie.)

Het is best een leuk spel; het lijkt wat op schaken, maar doordat je geslagen stukken opnieuw in het spel kunt brengen, gaat het veel sneller. Het lijkt dus ook minder van belang wie de meeste stukken geslagen heeft, want zelfs als je qua materiaal fors achterstaat, kan je soms toch nog de Wazir van de tegenstander slaan (die minder mobiel is dan de koning in het schaakspel).

[Vaan Banaan]

Ik ga ook meedoen.
Qua tactieken heb ik nog totaal geen idee, eerst maar een "vanilla" Monte Carlo Tree Search werkend krijgen.
De rollouts zonder enige heuristic gaat waarschijnlijk inderdaad behoorlijk zuigen. Die zal heel vaak geslagen stukken weer random terug op het bord knikkeren.

Ook transpositie ben ik nog niet uit. Omdat het spel na 100 zetten remise is, moet je bij een gelijke stelling ook enigszins rekening houden met de speelronde. Anders kan het voorkomen dat een "domme" tegenspeler ook een stuk/stukken heen en weer blijft schuiven. Maar als remise de beste uitkomst is, heb je geen alternatief

De volgende testronde is 1 november, dat ga ik niet redden. Mijn eerste deelname aan een testcompetitie wordt dus waarschijnlijk 22 november.

[Soultaker]

Vaan Banaan schreef op zondag 26 oktober 2025 @ 22:51:
Ik ga ook meedoen.

Leuk!

Qua tactieken heb ik nog totaal geen idee, eerst maar een "vanilla" Monte Carlo Tree Search werkend krijgen.

Ik was met minimax begonnen maar daarmee kom ik nog niet in de buurt van de topspelers, dus ik vraag me af of ik het over een andere boeg moet gooien, of verder moet ontwikkelen.

[allemensen]

Ik doe ook mee, en ik gebruik ook minimax. Maar ik vindt het echt lastig goede ideeën voor een evaluatiefunctie te verzinnen.
Wat is nou een goede aanval? En wat is een sterke positie om uit te verdedigen? Dat blijkt niet zo eenvoudig te formuleren.

Ik twijfel of MCTS beter is, dit lijkt me een tactisch spel waar precies zetten doen veel impact heeft. Maar goed, daar heb ik me vaker in vergist, dus ik laat me verrassen.

Vaan Banaan schreef op zondag 26 oktober 2025 @ 22:51:
Ook transpositie ben ik nog niet uit. Omdat het spel na 100 zetten remise is, moet je bij een gelijke stelling ook enigszins rekening houden met de speelronde. Anders kan het voorkomen dat een "domme" tegenspeler ook een stuk/stukken heen en weer blijft schuiven. Maar als remise de beste uitkomst is, heb je geen alternatief

Ik zou gewoon de speelronde opnemen in je definitie van "positie". Het aantal keren dat er in verschillende speelrondes exact dezelfde positie ontstaat (incl. wie aan de beurt is), lijkt me erg klein. En dan is je probleem met remise gelijk opgelost.

[allemensen]

Ik heb toch een doorbraak bereikt met mijn evaluatie functie, ik ben erg benieuwd hoe het morgen uitpakt.

[Soultaker]

allemensen schreef op vrijdag 31 oktober 2025 @ 22:10:
Ik heb toch een doorbraak bereikt met mijn evaluatie functie, ik ben erg benieuwd hoe het morgen uitpakt.

Het lijkt behoorlijk goed gewerkt te hebben (5e plaats).

Wil je iets kwijt over hoe diep je komt in je Minimax algoritme? Ik zit op 4 plies (soms moet ik die afkappen om niet over de tijdlimiet te gaan), en ik vraag me af of ik moet investeren in het efficiënter maken van m'n zoekalgoritme zodat ik dieper kan komen, of dat ik m'n evaluatie-functie moet verbeteren.

[allemensen]

Ik zoek ook 4 zetten vooruit momenteel (wat idd niet altijd lukt qua tijd). Daar valt nog wel in te optimaliseren voor mij, 5 of 6 zetten kan misschien ook wel.

Ik zie met testen dat verder vooruit kijken zeker helpt, maar dat de evaluatie functie veel meer uitmaakt. Niet zo gek: met 4 zetten vooruit wordt je beter in niet direct geslagen worden en in hetgeen je evaluatie functie kan zien. Als je bijvoorbeeld het aantal stukken van jou telt, zal je met 4 zetten vooruit kijken vaker stukken kunnen pakken en die van jezelf beter verdedigen. Maar de andere aspecten die belangrijk zijn voor winnen blijven grotendeels onbekend. Pas met veel meer zetten vooruit zoeken komen die in beeld.

[Vaan Banaan]

Ik heb inmiddels een random runner in elkaar geklust, die geldige zetten doet.
Nu dus naar mogelijke tactieken. Het terug kunnen plaatsen van geslagen stukken is echt een drama voor mijn hersens.
Ze zijn superhandig om stellingen te forceren, andersom verschrikkelijk voor een goede verdediging.
Zeker als door beide spelers al een aantal stukken zijn geslagen.

Ik heb wel wat ideeën over wat een goede of slechte zet is, maar dat is beperkt tot 2 à 3 zetten
Ik ga daarom toch stug door met een Monte Carlo. De rollouts kan ik wel iets intelligenter maken, hopelijk zonder te veel bevooroordeelde kennis.
Ik heb al wel gemerkt dat dit heel goed kan werken. Met een minimax weet je zeker hoe goed een stelling is, maar Monte Carlo kan soms verrassend goed uit de hoek komen vanwege het optimisme. (Of gruwelijk op zijn bek gaan, tegen een slim uitgekiend minimax pad)

[Soultaker]

allemensen schreef op vrijdag 7 november 2025 @ 14:53:
Ik zoek ook 4 zetten vooruit momenteel (wat idd niet altijd lukt qua tijd).

Aha, dus dan ligt het bij mij echt aan de evaluatie-functie. Eens zien of ik daar nog wat kan verbeteren.

Daar valt nog wel in te optimaliseren voor mij, 5 of 6 zetten kan misschien ook wel.

6 is behoorlijk ambitieus. Het probleem is dat de branching factor best hoog is (iets van 40?) dus voor elke ply dieper moet je je algoritme 40x zo efficiënt maken. Dat is niet zo eenvoudig te realiseren.

[allemensen]

Soultaker schreef op maandag 10 november 2025 @ 14:39:
6 is behoorlijk ambitieus. Het probleem is dat de branching factor best hoog is (iets van 40?) dus voor elke ply dieper moet je je algoritme 40x zo efficiënt maken. Dat is niet zo eenvoudig te realiseren.

Het is zeker ambitieus, geen idee of dat gaat lukken! Maar met alpha-beta pruning is dat effectief een stuk minder (√40, als ik het goed heb). En beter move-ordering toepassen (nu nog niks) zou ook nog moeten helpen.

[Soultaker]

allemensen schreef op maandag 10 november 2025 @ 19:17:
Het is zeker ambitieus, geen idee of dat gaat lukken! Maar met alpha-beta pruning is dat effectief een stuk minder (√40, als ik het goed heb). En beter move-ordering toepassen (nu nog niks) zou ook nog moeten helpen.

Klopt, maar die wortel is het minimum dat je alleen kunt bereiken als je perfecte move ordering hebt.

Het minimale aantal stellingen dat je moet evalueren met alfa-beta-snoeien is b^d/2 = (√b)^d (waarbij b de branching factor is, het gemiddelde aantal zetten per stelling, en d de zoekdiepte) en het maximale is b^d. In de praktijk kom je ergens tussen beiden uit; hopelijk wat dichter bij het eerste dan het tweede.

Het minimum haal je als je steeds de beste zet eerst probeert, en het maximum wanneer je de beste zet als laatste probeert. Dus goede move ordering is inderdaad erg belangrijk. Daar valt veel winst te behalen, maar het is niet realistisch om te verwachten dat je consequent het minimum haalt. Immers, als je move ordering zó goed zou zijn dat je altijd de beste zet identificeert, dan zou je het zoekalgoritme überhaupt niet uit hoeven te voeren.

[Vaan Banaan]

Ik heb move ordering icm alpha beta pruning met een eerdere competitie ook wel gebruikt om te vibe-prunen.
Door maar een deel van de (eigen) zetten door te rekenen, kun je net een paar zetten dieper binnen je bepaalde tijd.
Geen shallow search / iterative deepening en dat soort dingen, gewoon experimenteren met net te veel zetten vooruit zoeken en vergelijken of het resultaat (en tijd) verschil maakt met een complete ab-prune op die diepte.
Dat was toen ook een soort van check op blinde vlekken in de heuristic.

[ Voor 8% gewijzigd door Vaan Banaan op 10-11-2025 22:18 ]

[Vaan Banaan]

Ik heb afgelopen weekend meegedaan met een 1-ply kanonnenvoer versie.
Sowieso was het kansloos (35ste), maar mijn bitboards bleken ook nog eens een keer niet te allemaal te kloppen, dus dat is alvast winst
Een aantal observaties waarvan ik nog geen idee heb, of ik er iets mee ga doen:

• Knights lijken door de mobiliteit heel erg sterk
.n.n..
n...n. ik heb het idee dat als je die hebt geslagen
..N... je daarna veel makkelijker op de Wazir kunt jagen
n...n.
.n.n..

• Een Alfil bedreigd door een Dabbaba kan maar 2 kanten op vluchten
• Hetzelfde geldt voor de Dabbaba die wordt bedreigd door een Ferze.
x.D.x ..x..
..... ...F.
..a.. +.d.x
..... .....
+...+ ..+..
-edit- andersom ook!
Op die onbeschermde stukken kun je makkelijker jagen / met een revival klem zetten.
Mogelijk zal dat alleen bij de beginzetten wat schelen, dus iets om als blauw te kunnen gebruiken bij het opzetten van de stukken.

Eerst maar weer verder prutsen, volgende testcompetitie is dus 13 december.
(En ik doe niet mee aan de advent of code)