Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie
Toon posts:

[Wedstrijd]CodeCup 2021 - Zuniq

Pagina: 1
Acties:

  • Vaan Banaan
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter

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.

500 "The server made a boo boo"


  • Vaan Banaan
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter



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]

500 "The server made a boo boo"


  • Bolukan
  • Registratie: oktober 2002
  • Laatst online: 18:32
2^60 bordsituatie, 1.152.921.504.606.850.000 combinaties, zal wel te veel zijn voor bruto-force ja.

  • Vaan Banaan
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
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]

500 "The server made a boo boo"


  • Morrar
  • Registratie: juni 2002
  • Laatst online: 22:36
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
  • Registratie: oktober 2002
  • Laatst online: 18:32
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
  • Registratie: november 2004
  • Laatst online: 17:37
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

Bordspellenopruiming! https://www.marktplaats.nl/u/martijn/14875712/


  • Bolukan
  • Registratie: oktober 2002
  • Laatst online: 18:32
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# bordmogelijkhedenontspiegeld
011
1609
21.770243
334.2204.323
4487.63561.314
55.461.512683.014
650.063.860etc
7386.206.920
82.558.620.845
914.783.142.660
1075.394.027.566
11342.700.125.300
121.399.358.844.975
135.166.863.427.600
1417.345.898.649.800
1553.194.089.192.720
16149.608.375.854.525
17387.221.678.682.300
18925.029.565.741.050
192.044.802.197.953.900
204.191.844.505.805.490
217.984.465.725.343.800
2214.154.280.149.473.100
2323.385.332.420.868.600
2436.052.387.482.172.400
2551.915.437.974.328.300
2669.886.166.503.903.500
2788.004.802.264.174.700
28103.719.945.525.635.000
29114.449.595.062.769.000
30118.264.581.564.861.000
31114.449.595.062.769.000
32103.719.945.525.635.000
3388.004.802.264.174.700
3469.886.166.503.903.500
3551.915.437.974.328.300
3636.052.387.482.172.400
3723.385.332.420.868.600
3814.154.280.149.473.100
397.984.465.725.343.800
404.191.844.505.805.490
412.044.802.197.953.900
42925.029.565.741.050
43387.221.678.682.300
44149.608.375.854.525
4553.194.089.192.720
4617.345.898.649.800
475.166.863.427.600
481.399.358.844.975
49342.700.125.300
5075.394.027.566
5114.783.142.660
522.558.620.845
53386.206.920
5450.063.860
555.461.512
56487.635
5734.220
581.770
5960
601
Totaal1.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
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
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.

500 "The server made a boo boo"


  • Bolukan
  • Registratie: oktober 2002
  • Laatst online: 18:32
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
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
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]

500 "The server made a boo boo"


  • boreus
  • Registratie: december 2011
  • Laatst online: 20-09 15:30
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
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
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.

500 "The server made a boo boo"


  • boreus
  • Registratie: december 2011
  • Laatst online: 20-09 15:30
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
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
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 |:( :X 8)7 :'(

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.

500 "The server made a boo boo"


  • Vaan Banaan
  • Registratie: februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
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 zetlaatste
Winnaar1419 (alles)
2de1219 (alles)
ik (6de)1017

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]

500 "The server made a boo boo"

Pagina: 1


Apple iPhone SE (2020) Microsoft Xbox Series X LG CX Google Pixel 4a CES 2020 Samsung Galaxy S20 4G Sony PlayStation 5 Nintendo Switch Lite

'14 '15 '16 '17 2018

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2020 Hosting door True