[Wedstrijd]CodeCup 2021 - Zuniq

[Vaan Banaan]

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.
Dit jaar draait het om Zuniq, een pen-and-paper variant van Dots and Boxes
Website: https://www.codecup.nl/intro.php

Over het spel

Zuniq wordt gespeeld met 2 spelers op een 6 x 6 raster De spelers moeten om en om een horizontale of verticale lijn tussen 2 punten zetten. Degene die de laatste lijn zet, is de winnaar
Een lijn kan dus horizontaal zijn (bijvoorbeeld A2h) of verticaal (bijvoorbeeld C4v) Je bent vrij om ergens een lijn te zetten, het hoeft niet ergens op aan te sluiten In de afbeelding hiernaast hebben de spelers de lijnen A2h, B3h, C1v, C4v, E3h, E5h en E5v gezet
Als gedurende het spel een lijn gezet wordt, wat een gesloten gebied maakt, wordt het aantal vakjes in dat gebied geteld. Binnen een gesloten gebied (als dat meer dan 1 vakje is) mag je geen lijnen meer zetten
Ook mag daarna niet nog een gebied van eenzelfde grootte afgesloten worden. A3v, A6v, C5v, E4v en E6v (oranje) zijn ongeldige zetten geworden. Wel mag je een gebied van andere grootte afsluiten Bijvoorbeeld A2v (blauw) -> gebied van 2 vakjes D6v (groen) -> gebied van 3 vakjes
Het spel eindigt als er geen lijnen meer gezet kunnen worden
De winnaar krijgt 100 punten, de verliezer 50 Als je denkt dat je gaat winnen, kun je voor extra punten ook nog een uitroepteken achter je zet meegeven. Maar als je dan toch verliest, krijg je helemaal geen punten. Bovenstaand voorbeeld is ook als voorbeeld spel op de site te bekijken.

Talen waarin je mee kan doen

Pascal, C, C++, Java, Javascript, Python, Haskell en OCaml
C# wordt dus niet ondersteunt

Competitie

De finale is op 23 januari 2021

Je kunt op elk moment een (nieuwe) versie van je programma opsturen.
Die krijgt maximaal 30 seconden CPU denktijd, op een 3.1GHz XEON CPU, single threaded met max 256MB geheugen.

Elke 3 weken wordt een testcompetitie gehouden, waaraan je inzending meedoet.
Zo kun je alvast testen hoe goed je programma het ten opzichte van anderen doet.

De eerstvolgende testcompetitie is op 22 augustus
Daarna (vermoedelijk) 12 september, 3 oktober, 24 oktober, 14 november, 5 december en 2 januari

Om lokaal versies tegen elkaar te laten spelen is er caia
Dit is beschikbaar voor OSX en Linux.
Voor Windows 10 is er een Cygwin versie of moet je met Subsystem for Linux aan de slag.

[Vaan Banaan]

Ook dit spel lijkt weer bedrieglijk simpel, maar is het niet.
Om iets te maken, wat een beetje presteert, zul je er een hoop tijd in moeten steken, het is zeker niet te vergelijken met iets als de Advent Of Code series

Vorig jaar ben ik nog 2de geworden met Gomoku (beginnersgeluk?), maar dit jaar hang ik nog wel even laag in de middenmoot ben ik bang.
Soultaker heeft overigens in 2011 met DVONN gewonnen

Uiteindelijk komt het er bij elk spel op neer, om je tactiek en beslissingsboom zo snel / intelligent / klein mogelijk te maken.

Het spel van dit jaar lijkt geschikt voor Monte Carlo Tree Search,
dat is waar Google's AlphaGo een aantal jaar geleden het nieuws mee haalde.
Tenminste dat was mijn eerste gedachte.
Aangezien je niet snel ziet, of een zet goed is of niet, heb ik geen idee hoe ik een evaluatie in een minimax (variant) kan stouwen.

Ik heb nu voor het eerst een mcts functie in mijn bot gebouwd.
Die heeft de testcompetitie van 1 augustus gespeeld, maar was nog niet echt een succes.
Sowieso verlies ik nog altijd van de testspeler, die je inzendingen valideert.

[Voor 95% gewijzigd door Vaan Banaan op 15-08-2020 12:46]

[Bolukan]

2^60 bordsituatie, 1.152.921.504.606.850.000 combinaties, zal wel te veel zijn voor bruto-force ja.

[Vaan Banaan]

Nou het is eigenlijk 60! en zelfs dat nog niet eens.
Met dit spel heb je maximaal 41 zetten, alleen heb je in het begin wel max 60 x 59 x 58 x 57 (afgesloten gebied van 1) x 56 x 55 x 54 of 53 (iets wat niet meer afgesloten mag worden) enzovoort.
In ieder geval veeeeel te veel mogelijkheden.

Met de wedstrijd van vorig jaar (soort van 5 op een rij) had je bij elke zet wel een grof idee of die zet slim was of niet.
Daarom ging, van wat ik heb gelezen, de betere spelers (en ik ook) voor Alpha Beta pruning met o.a. een transposition table (om dubbele stellingen niet nog een keer te berekenen)
En in mijn geval ook nog eens sortering na elke zet, om de boom flink te snoeien.

Met dit spel heb ik niet het gevoel dat je vooraf kan bepalen of een zet goed is of niet. Maar je hebt wel 30 seconden CPU tijd, dat is lekker veel.
Vandaar dat ik met de Monte Carlo Search Tree aan de slag ben gegaan. Had ik alleen maar over gelezen, maar het viel me nog mee om te programmeren.

Bij het begin van het spel gaat dat als volgt:

• Je begint met een root node: 0 simulaties, 0 gewonnen
• Je kiest een willekeurige zet (expansion) daar maak je een node van in de boom, ook weer 0 simulaties, 0 gewonnen
• Dan doe je weer een rits random zetten, tot het spel is afgelopen (simulation)
• Voor de nodes van de net gemaakte expansion tot de root (nu nog maar 2 nodes diep) doe je een +1 voor aantal simulaties en voor de gewonnen potjes bij de node(s) met zet van de tegenstander (is nu alleen nog maar de desbetreffende expansion node) een +1 gewonnen
  Dat is de back propagation

Dat doe je dan bij de eerste zet voor alle 60 mogelijkheden (als je mag beginnen), zodat de root node volledig expanded is.
En dan treedt het briljante deel van mcts in werking: de selection
Omdat de root node volledig expanded is, kan die een zet verder gaan "denken". Maar welke child node is nu het beste?
Over een goede keuze wordt nog steeds veel onderzoek gedaan en heet Upper Bound Confidence in Trees, ik gebruik de pure (originele) formule: Wi / Si + C * sqrt(log(Sp) / Si)
Wi = gewonnen potjes child
Si = gesimuleerde potjes child
C = exploration parameter
Sp = Aantal gesimuleerde potjes parent (in het begin is dat de root)

Op de expanded nodes laat je die formule los:

• met Wi / Si kun je de beste winst factor van een node berekenen (exploitation)
• Maar omdat je maar wat random simulaties doet, wil je ook wel andere zetten bekijken (exploration) Mischien had een node pech en een kneus random simulation, maar is die stiekem toch wel ok.
  Daarvoor is C * sqrt(log(Sp) / Si)
  Met de C kun je de agressie instellen. Met een kleine C zal die meer exploiten (dieper de boom in), met een hoge meer exploren (waardoor je boom sneller breder wordt)
  Een balans hierin is de waarde sqrt(2)
• De node met de hoogste waarde is de "dat lijkt me wel een goede zet" en met die ga je weer een expansion en een simulation doen.

Dat doe je dan zo vaak mogelijk en uiteindelijk kies je de root-child met de meeste simulaties als beste zet.
Dat hoeft dus niet de node te zijn met de meest gewonnen potjes en dat maakt het hele principe lastig te doorgronden.

Het mooie van dit ding is, dat je boom asymmetrisch opgebouwd wordt. Maar dat je niet, zoals met alpha-beta, een diepte hoeft te gokken of klooien met iterative deepening, sorteringen of andere kunstgrepen.
Voorwaarde is wel, dat je veel simulaties moet kunnen doen binnen de gestelde tijd, zodat een zet niet al te gok-de-goals wordt,
Naarmate het spel vordert, zal dit algoritme automagisch richting ideale zet(ten) neigen.

Verder heb ik de simulation niet helemaal random gemaakt, dat heet overigens Policy, maar mag in mijn programma geen naam hebben.
Het is in ieder geval geen artificial-neural-network-deep-supervised-reinforcement-learning-glazen-bol-hocus-pocus-agent-heuristics
Het lastige is, als je de simulation "slim" probeert te maken, er bevooroordeelde zetten kunnen ontstaan. Dat werkt het algoritme juist tegen, dus random doet het eigenlijk nog het best goed. Alleen wordt je boom snel onmeunig groot.
-edit- de policy is juist de hocus-pocus en bepaalt je selection strategie, kom ik nu achter tijdens het lezen van weer vanalles en nog wat.

Overigens had ik een ongelooflijke domme fout gemaakt in die formule.
Hij deed ruim een miljoen simulaties (over het hele spel) maar was nog steeds te dom was om te kakken.
Nu ik deze bug heb opgelost heb ik ook voor het eerst van de testspeler gewonnen (die valideert je programma)
YEAH!!

[Voor 13% gewijzigd door Vaan Banaan op 12-08-2020 10:52]

[Morrar]

Leuke challenge! Beetje kamertje verhuren, maar dan anders. Lijkt me ook een mooie case voor reinforcement learning: Wikipedia: Reinforcement learning

Je kan het algoritme vaak genoeg tegen zichzelf laten spelen om het zo te trainen. Ook de reward structure is overzichtelijk, al kan het natuurlijk zijn dat eerst iets weggeven later meer oplevert.

[Bolukan]

Het lijkt toch echt een impartial game, dus 2^60. De volgorde van de streepjes maakt echt niet uit.

PS: In het voorbeeld kan toch bijvoorbeeld E2v of E2h worden gespeeld? Oftewel het gebied van 9 splitten in 4 en 5?

[Voor 27% gewijzigd door Bolukan op 13-08-2020 08:20]

[BSTNjitRam]

Bolukan schreef op woensdag 12 augustus 2020 @ 19:52:
Het lijkt toch echt een impartial game, dus 2^60. De volgorde van de streepjes maakt echt niet uit.

2^60 impliceert dat er elke zet 2 opties zijn. Echter zijn er 60 posities waar de eerste streep gezet kan worden. Doordat die daarna niet meer mogelijk is, zijn er voor de 2e streep nog 59 posities over. Echter zijn deze posities dmv rotaties en spiegelingen uiteraard veel verder terug te brengen (A1h is technisch gezien dezelfde openingsmove als E6v maar dan 90 graden geroteerd).

Bolukan schreef op woensdag 12 augustus 2020 @ 19:52:
PS: In het voorbeeld kan toch bijvoorbeeld E2v of E2h worden gespeeld? Oftewel het gebied van 9 splitten in 4 en 5?

Uit de regels van de startpost:
Binnen een gebied (als dat meer dan 1 vakje is) mag je geen lijnen meer zetten

[Bolukan]

Ah op die manier. Ik doelde op het maximaal aantal bordposities. Zoals hieronder.
NB: Die regel had ik over het hoofd gelezen. Een 9 splitsen in 4 en 5 is dus illegaal.

zet	# bordmogelijkheden	ontspiegeld
0	1	1
1	60	9
2	1.770	243
3	34.220	4.323
4	487.635	61.314
5	5.461.512	683.014
6	50.063.860	etc
7	386.206.920
8	2.558.620.845
9	14.783.142.660
10	75.394.027.566
11	342.700.125.300
12	1.399.358.844.975
13	5.166.863.427.600
14	17.345.898.649.800
15	53.194.089.192.720
16	149.608.375.854.525
17	387.221.678.682.300
18	925.029.565.741.050
19	2.044.802.197.953.900
20	4.191.844.505.805.490
21	7.984.465.725.343.800
22	14.154.280.149.473.100
23	23.385.332.420.868.600
24	36.052.387.482.172.400
25	51.915.437.974.328.300
26	69.886.166.503.903.500
27	88.004.802.264.174.700
28	103.719.945.525.635.000
29	114.449.595.062.769.000
30	118.264.581.564.861.000
31	114.449.595.062.769.000
32	103.719.945.525.635.000
33	88.004.802.264.174.700
34	69.886.166.503.903.500
35	51.915.437.974.328.300
36	36.052.387.482.172.400
37	23.385.332.420.868.600
38	14.154.280.149.473.100
39	7.984.465.725.343.800
40	4.191.844.505.805.490
41	2.044.802.197.953.900
42	925.029.565.741.050
43	387.221.678.682.300
44	149.608.375.854.525
45	53.194.089.192.720
46	17.345.898.649.800
47	5.166.863.427.600
48	1.399.358.844.975
49	342.700.125.300
50	75.394.027.566
51	14.783.142.660
52	2.558.620.845
53	386.206.920
54	50.063.860
55	5.461.512
56	487.635
57	34.220
58	1.770
59	60
60	1
Totaal	1.152.921.504.606.850.000
2^60 =	1.152.921.504.606.850.000

[Voor 18% gewijzigd door Bolukan op 14-08-2020 23:22]

[Vaan Banaan]

Ehm je krijgt maar 256MB geheugen, dus die aantallen boeien me totaal niet
En Monte Carlo + transposition table is overigens andere koek dan bij een MiniMax(variant) boom. Daar ga ik me nog even niet aan wagen.

Ik krijg iets van 1,5 miljoen expanded nodes (dus simulaties) weggestouwd binnen de tijd.
Ben nu een beetje aan het experimenteren met hetvolgende:
Doe je elke zet ongeveer 1,5 seconden, of de eerste x zetten quasi random en ga je de laatste y zetten lange tijd broeden op een uitkomst?
Had al een versie die elke ronde steeds iets meer zoekt, maar zo'n burst halverwege / driekwart lijkt het tegen de validatiespeler net iets beter te doen.
Ik denk dat ik eerst maar zelf eens een manager ga schrijven, zodat ik versies tegen elkaar kan laten spelen.

En later ga ik nog eens uitzoeken hoe ik, als een potje al vrij ver gevorderd is, delen kan ontdekken die er niet toe doen. Dat wil zeggen: er zijn nog een paar muurtjes in een stukje veld over, die niet meer helemaal dichtgezet kunnen worden.
Dan maakt het eigenlijk niet zoveel uit welk muurtje je zet. Meestal is het aantal toch hetzelfde.
Ik denk dat daar de meeste winst zit, maar dat idee moet bij mij nog even pruttelen.

[Bolukan]

Tijd verdelen waar de meeste waarde (om het verschil te maken richting winnen) is te behalen. Ik denk ook dat 20 x 1,5 sec niet optimaal is, Heb je nagedacht over een voorbereid openingsboek?

[Vaan Banaan]

Ja, maar openingbook komt bij mij altijd op de laatste plaats == nog nooit van gekomen.
Dat wil ik dit jaar anders doen, ik ben met deze competitie al vanaf dag 1 (begin juli) aan het brainstormen..
Maar er zijn nog zat optimalisaties mogelijk, die zal ik toch moeten aanspreken als het openingbook uitgeput raakt.

PS: de sourcecode mag max 1.44MB groot zijn en moet in 1 file staan. En niets van/naar bestanden lezen of schrijven, memory only (256MB)

Morrar schreef op woensdag 12 augustus 2020 @ 09:25:
...Lijkt me ook een mooie case voor reinforcement learning: Wikipedia: Reinforcement learning,,,,

Ik heb een haat-liefde verhouding met algoritmes op Wikipedia.
Op die Wiki ben ik al tig-keer vastgelopen vanwege allerlei verwijzingen, die weer verwijzen naar een verwijzing waar ik allemaal de ballen verstand van heb. Het is zo overweldigend en abstract dat ik er steeds memory overload van krijg.
Q-learning, Bellman equation, Stochastic environments, Markov Decision Processes, WTFBBQ en weet ik wat.
En dan ook nog zonder een regel pseudocode. Het is dat ik wiskunde altijd leuk heb gevonden, anders had ik dat allang opgegeven.
Hier bijvoorbeeld wordt het allemaal net even wat makkelijker uitgelegd met plaatjes en code Dan lees ik daarna de wiki nog wel eens door, als ik er aan toe ben.

Sowieso wordt dat dan een offline simulatie, die meerdere dagen zal moeten lopen, om er iets bruikbaars uit te laten komen.
En dat moet dan op een of andere manier nog in die ene sourcefile en mag niet al te groot zijn.
Wel weer handig voor een openingsboek, maar voor mij nu allemaal nog te hoog gegrepen voor de online competitie.

[Voor 75% gewijzigd door Vaan Banaan op 15-08-2020 23:34]

[boreus]

Ik ben vooral druk geweest zo vroeg mogelijk(*) het eindspel door te kunnen rekenen. Met een winnende score vaak rond 106 lijkt dat redelijk gelukt, als ik vergelijk met de resultaten van de vorige testronde.

(*) Lastig om het goede moment te kiezen; vrij pijnlijk als je te vroeg alles gaat doorrekenen.

Opening en middenspel heb ik nog niet echt goede ideeën voor.

Succes allemaal morgen!

[Vaan Banaan]

Tof dat je meedoet!
Dat moment van flink doorrekenen is inderdaad lastig. Ik reken nu net voorbij de helft van het spel flink door, maar dat is het ook niet altijd.
Deze testronde ben ik toch ook aardig gestegen, sta nu 7de overall (8ste met unofficials meegerekend).

Ik ben nog aan het brainstormen over het eindspel.
Mijn huidige versie doet nog veel te veel onnodige combinaties, waardoor ik geen enkel spel heb gewonnen met meer dan 102 punten.
Bijvoorbeeld:

Hier vallen enorm veel combinaties af.
De 1-tjes zijn allemaal stukjes veld, waar nog maar 1 muur gezet kan worden. Welke boeit niet, dat zijn altijd in totaal nog maar 3 zetten.
De roze muren zijn ook altijd 3 zetten. En als je de 2 grijze muren eerder zet, hou je nog maar een combi van 2 roze muren over.

Hier moet dus al makkelijk een eindspel uit te peuteren zijn. Met dan inderdaad een score van 106/107
In ieder geval zie je ook al veel eerder, of dit potje sowieso wel te winnen valt.

[boreus]

Mijn eindspel berekening moet het nu hebben van optimalisatie en caching. Dat kost ook wat geheugen (ging slecht bij de test competitie; voortaan met ulimit -v 250000 testen).

Qua opening heb ik nu een lijstje met standen waarin ik weet dat ik kan winnen en daar probeer ik dan naar toe te spelen.

De huidige nummer 1 scoort af en toe 110 punten, dus er is nog wel ruimte voor verbetering.
(Er zit ook iemand bij die bluft af en toe 110 punten. Ik heb de nummer 1 geen 0 punten zien scoren.)

Jouw idee lijkt me wel wat, maar ik heb het gevoel dat het nog niet genoeg is voor 110 punten.

Ik ga mijn zoekfuncties opschonen, omdat ik denk dat daar nog wel winst te halen is met een goede heuristiek voor de volgende zet. Momenteel geeft mijn programma het een beetje op als hij door heeft dat de tegenstander een winst kan forceren, dus daar moet ook nog wat aan gedaan worden.

[Vaan Banaan]

Ik heb net een fabeltastische optimalisering gevonden: de tijd.
Met ver doorrekenen houd ik rekening met de verstreken tijd, maar ik kom er nu net achter dat ik de wall-time heb gebruikt.
Oftewel: ook de tijd die de tegenstander gebruikt

In deze testcompetitie heeft mijn programma dus een behoorlijke rits potjes gespeeld met 13-15 seconde rekentijd, MAN wat is dit frustrerend. AAAGGHHH

En ik dacht al bij het valideren van mijn inzendingen: waarom heeft dat ding nog zoveel tijd over? Nou ja, gewonnen is gewonnen. En door...
Aan de andere kant heb ik nu van alle spelers een grove indicatie, wanneer zij er vol voor gaan.

[Vaan Banaan]

Met de testcompetitie van vandaag weer een plekje gestegen.
Maar de beste spelers hebben wel heel veel meer punten.

In dit spel ben je overigens wel zwakker als je moet beginnen.

	Gewonnen
	1ste zet	laatste
Winnaar	14	19 (alles)
2de	12	19 (alles)
ik (6de)	10	17

Ik denk dat mijn mcts-random-mover niet heel veel sneller meer kan.
In ieder geval heeft die bij verloren potjes vaak nog geen flauw idee dat die kansloos is, terwijl de tegenstander al wel weet dat die heeft gewonnen.
Komende weken ga ik dus maar gegevens verzamelen van de gespeelde potjes van de afgelopen testcompetities.
Mogelijk is er iets te halen uit het aantal overgebleven geldige zetten per beurt of zo (even / oneven)
Dat heb ik al heel vroeg laten varen, maar misschien is daar toch nog iets van een heuristic voor te bakken.

[Voor 83% gewijzigd door Vaan Banaan op 12-09-2020 15:46]