[Wedstrijd] Gomoku

[Corniel]

Het spel

Gomoku, also called Five in a Row, is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a square board, using 16×16 grid intersections. Players alternate turns placing a stone of their color on an empty intersection. The winner is the first player to form an unbroken chain of five stones horizontally, vertically, or diagonally.

Wat je wilt weten

De finale is 18 januari 2020

Handige links

Wedstrijdsite

[Vaan Banaan]

Ik had hem ook al in de Devschuur Coffee Corner gemeld.

CodeCup wordt elk jaar georganiseerd door o.a. Nederlandse Informatica Olympiade
Dit jaar is het spel Gomoku, een 5-op-een-rij op een Go achtig bord van 16x16


• De talen waarin je kan meedoen zijn:
Pascal, C, C++, Java, Javascript, Python, Haskell en OCaml:
• Je speler krijgt per potje maximaal 5 seconden CPU denktijd (op een 3.1GHz XEON CPU) draait single threaded met max 256MB geheugen.
• De finale is zoals gemeld op 18 januari 2020
• Elke 3 weken is er een test competitie (inmiddels zijn er 5 van de 9 testrondes gespeeld)
De volgende testrondes zijn op 26 oktober, 16 november, 7 en 28 december. Ze beginnen altijd om 06:00 uur.

Je kunt op elk moment een versie opsturen. Als die door de validator wordt goed gekeurd, is dat je versie waarmee de eerstvolgende testcompetitie wordt gespeeld.
Bij opsturen worden 2 potjes gespeeld tegen een "test"speler. 1 keer mag jij beginnen en 1 keer mag de tegenstander beginnen.
En dat kreng is verschrikkelijk goed, ik kan er nog niet van winnen.

[ Voor 4% gewijzigd door Vaan Banaan op 07-10-2019 13:58 ]

[Corniel]

Ik ben nog in dubio of ik zelf een poging ga doen. Als je 5 seconde totaal hebt lijkt machine learning bijvoorbeeld al best lastig.

[Vaan Banaan]

Ik kan een paar miljoen stenen per seconde op het bord knikkeren met enigszins bruikbare uitkomst, maar daarmee alleen kom je nog helemaal nergens.

Monte Carlo Tree Search (Waar o.a. Googles AlphaGO het nieuws mee haalde) is misschien bruikbaar.
Maar zelfs met 10 miljoen "coin flips" in een seconde lijkt me dat nog te weinig tegen een speler met goede tactiek.

Ik ben daarom eerst maar begonnen met een minimax variant: Alpha-beta_pruning
Mijn tactiek is op dit moment ook niet bepaald rocket science: van alle mogelijke zetten per beurt de waarden sorteren en dan de beste x-aantal een aantal zetten verder doorrekenen.
De sortering per zet is enorm duur qua tijd, maar ik gok dat de a-b-pruning daardoor wel lekker subtrees kan weghakken.

Ik had vorige week mijn eerste versie ingeleverd en verloor genadeloos van de validatiebot.
Des te groter was mijn verbazing, toen bleek dat ik in de testcompetitie van afgelopen zaterdag 3de sta (van de officiële deelnemers)

[ThomasG]

Er zijn verschillende onderzoeken gedaan naar winnende strategieën voor Gomuku, waaronder door Nederlanders: Go-Moku and Threat-Space Search. Je zou met delen daarvan een eind moeten kunnen komen.

[ Voor 8% gewijzigd door ThomasG op 07-10-2019 09:11 ]

[Vaan Banaan]

Grappig, daar houdt mijn bot ook al een heel eind rekening mee.
Ik heb een aantal dagen met backgammon fishes gespeeld en die "threats" zie je na een tijdje vrij snel aankomen.

Voorbeeld: Je kan .x+xx. maken (de + wordt je nieuwe zet)
De tegenstander kan je nu niet meer blokkeren, dus heb je de zet daarna gewonnen (BEHALVE als de tegenstander ook al ergens een 4van5 heeft, dan wint die net wat snellerderder)

En zo heb je inderdaad nog wel een aantal varianten:

code:

5van5    4van5    2x 4van5      4van5 +       2x
          open                3van5open   3van5open
                    .....       .....      ......
x+xxx   .x+xx.      ..x..       x+xx.      ..x...
                    .x+xx       .x...      .x+x..
                    ..x..       .x...      ..x...
                    ..x..       .....      ......
                                .....      ......

De richtingen maken natuurlijk niet uit, (combi) horizontaal, verticaal en/of diagonalen is allemaal gevaarlijk

Als de tegenstander, na jouw zet, een van deze stellingen kan maken, ga je waarschijnlijk verliezen.
Als je zelf niks beters kan maken, moet je dus direct gaan blokkeren.

[ Voor 5% gewijzigd door Vaan Banaan op 07-10-2019 12:24 ]

[Hydra]

Wel erg cool! Ik zit al een tijdje met 't idee in m'n hoofd toch weer eens in C++ te duiken, en dan is dit wel een erg mooi project om op te pakken.

[Joep]

Het lijkt me ook erg leuk om aan deze wedstrijd mee te doen, maar ik krijg caia niet geïnstalleerd. Ik heb de Windows subsystem for Linux aangezet, vervolgens Debian geïnstalleerd, reboot gedaan, de tarball in C:\Users\Joep\AppData\Local\Packages\TheDebianProject.DebianGNULinux_76v4gfsz19hv4\LocalState\rootfs\home\joep gezet, debian gestart en tar -xzf caia_gomoku_linux64.tar.gz uitgevoerd, maar ik krijg een foutmelding waar ik niet verder mee kom:



Even googlen levert me deze pagina op: https://askubuntu.com/que...-when-creating-a-tar-file ,maar wat ik ook probeer, niks werkt. Heeft iemand tips? Ik moet er wel bijzeggen dat ik echt 0,0 ervaring heb met linux

[Vaan Banaan]

Ik zit op Windows 7 en heb het geprobeerd met Cygwin. Maar daar krijg ik bij het compileren ook allerlei fouten en heb dat maar opgegeven.
Als je op CodeCup een accountje aanmaakt, mag je op het forum, maar daar is verder ook geen Windows versie te vinden.

Op dit moment speel ik dus nog "blind".
Ik geef mijn bot een bepaalde stelling, waar ik een tijd op heb zitten broeden en kijk dan of de oplossing binnen een paar tienden van een seconde gevonden wordt.

Bijvoorbeeld een stelling uit de paper die ThomasG linkte:
De eerste stelling geef ik aan mijn bot, die moet dan 1 van de 2 zetten geven (+-jes van de 2de stelling) waardoor die altijd wint.

code:

                                                 +      
   x               x               x              x     
                    + O             x o            x o  
                    O+              ox             ox   
   ox              ox              ox +           ox x  
  oxx             oxx             oxx  O         oxx  o 
  xox   o         xox   o         xox   o        xox   o
 o  o            o  o            o  o           o  o

Misschien dat ik nog wel die caiaio ga verbouwen naar een Windows versie, zodat ik potjes met verschillende bots tegen elkaar kan laten spelen.
Maar dat wordt nog een heel gepuzzel met processen spawnen, suspend/resume, io redirecten en nauwkeurige tijdmeting.

Eerst maar weer eens een paar ideeën uitwerken, zodat ik hopelijk een betere versie voor de volgende testronde klaar heb...

[veldsla]

Joep schreef op maandag 7 oktober 2019 @ 19:11:
Het lijkt me ook erg leuk om aan deze wedstrijd mee te doen, maar ik krijg caia niet geïnstalleerd. Ik heb de Windows subsystem for Linux aangezet, vervolgens Debian geïnstalleerd, reboot gedaan, de tarball in C:\Users\Joep\AppData\Local\Packages\TheDebianProject.DebianGNULinux_76v4gfsz19hv4\LocalState\rootfs\home\joep gezet, debian gestart en tar -xzf caia_gomoku_linux64.tar.gz uitgevoerd, maar ik krijg een foutmelding waar ik niet verder mee kom:

[Afbeelding]

Even googlen levert me deze pagina op: https://askubuntu.com/que...-when-creating-a-tar-file ,maar wat ik ook probeer, niks werkt. Heeft iemand tips? Ik moet er wel bijzeggen dat ik echt 0,0 ervaring heb met linux

De error geeft aan dat het tar proces geen toegang heeft tot de archief file. Je kunt even kijken met

ls -la

welke user eigenaar van het bestand is en welke permissies erop staan. Een

chmod 664 caia_gomoku_linux64.tar.gz

kan het bestand world readable maken, maar dat moet als de eigenaar of als root worden uitgevoerd. (En ik heb dan weer geen idee hoe dat in de Windows subsystem for Linux zou kunnen)

[Joep]

@veldsla Thx! Ik ga het proberen

Edit: En zo kom ik erachter dat je in WSL niet zomaar bestanden met de verkenner van Windows kunt kopiëren naar de directory van je distro. Dat moet in de cli van je distro gebeuren d.m.v. het commando cp. Nu heb ik de benodigde rechten op de tar-file en kan ik verder

Edit 2: En na 'sudo apt-get update && sudo apt-get upgrade' en 'sudo apt-get install build-essential' kan caia eindelijk fatsoenlijk geïnstalleerd worden, want het commando make ontbreekt standaard in debian. Als ik alleen make geïnstalleerd zou hebben, zou ik waarschijnlijk tijdens de installatie van caia op een ander ontbrekend commando zijn gestuit, vandaar 'sudo apt-get install build-essential'. Nu werkt caia eindelijk en kan ik beginnen met coderen.

[ Voor 122% gewijzigd door Joep op 09-10-2019 15:13 ]

[Vaan Banaan]

De volgende testronde is 26 oktober (volgende week zaterdag)

Ik heb inmiddels mijn sorteer routine geoptimaliseerd naar een soort groepering, op wat het effect van een lege positie is, op het maken van 5 op een rij om zich heen. (Dus horizontaal, verticaal, en de diagonalen)
Ik wilde al een tijdje iets proberen met een Radix sort en daar is die groepering nu losjes op gebaseerd.

Verder ben ik nog een aantal enorme denkfouten tegengekomen, waardoor de bot in sommige gevallen te dom was om te kakken.

Ik heb nu voor het eerst de 2 potjes van de validatie testbot gewonnen.
Dat is wel met een beetje geluk geweest, want door verder vooruit te "denken" doet een zet er ongeveer 0,2 seconden over. Dus ik zal wel mank gaan bij lange potjes.
Maar de versie is verder wel stabiel, en ik wil niet minder zetten vooruit denken, dus die gaat de volgende testronde spelen.
-edit-
Weer een paar fouten gevonden. Daardoor lijkt de bot het met een zet minder vooruit te denken, nog net zo goed te doen.
En omdat de zoekboom een stuk kleiner is, weer een stuk sneller, dus mag een potje nu ook lang duren.

[ Voor 11% gewijzigd door Vaan Banaan op 22-10-2019 01:04 ]

[Corniel]

Ook suf:

Subject: CodeCup 2020: C# support?!

I was wondering if you would consider supporting .NET. Core 2.0 or so, would be nice.

Thanks in advance.

Response:

We have had earlier request for other languages, but so far that was not a big succes. And it takes us time to maintain the compiler. So we are not doing it at the moment. We're sorry.

Tja, deze wordt hem niet voor mij. Ik heb geen zin om mijn programma te gaan poorten. Daarnaast is het vrij suf dat ze drie smaakjes C++ ondersteunen, een geen C#, wat toch een zeer populaire taal is.

[Vaan Banaan]

De competitie draait op Ubuntu 18.04.2 LTS, zie https://www.codecup.nl/rules_tech.php
Ik heb nooit wat in C# gedaan, maar zo te lezen is er inmiddels goede Linux ondersteuning (en open source), dus dat is dan wel jammer.
Wat C en C++ betreft: ze gebruiken de GCC compiler, daar zitten ze allemaal standaard in.

Ik ben met de laatste testronde van 26 oktober gezakt naar de 4de plaats in een groep van plaats 3 t/m 7 met ongeveer evenveel punten.

Maar ik heb nu eindelijk een idee hoe ik dat Threat Space Search in mijn programma zou kunnen toepassen.
Dat heet tegenwoordig blijkbaar Victory by Continuous Threes (VCT) / Fours (VCF) en is nog steeds een van de heilige gralen van Gomoku "AI"
Je maakt dus een open 3 (bijvoorbeeld ..xxx.) of een 4 (bijvoorbeeld xxx.x)
Daardoor moet de tegenstander jouw bijna-5-op-een-rij blokkeren en probeer jij de volgende zet weer een open 3 of een 4 maken, enzovoort. Net zolang tot je een stelling hebt met 2 kansen, waardoor je wint.
Omdat je de tegenstander dwingt tot maar een paar mogelijke zetten, kun je zelf meer zetten vooruit denken om die threats vol te houden.

De kunst is natuurlijk HOE zo lang mogelijk zo veel mogelijk threats te houden (en niet allerlei losse 4-en op het bord te maken, die geen nieuwe threats maken)
Dat kan dus door met de ene threat een andere op te bouwen, zodat je de beurt daarop een echt nieuwe threat kan maken (die weer een volgende opbouwt / combineert)
In de paper geven ze een aantal voorbeelden met dependency trees.
Maar een idee hoe je zoiets (efficiënt) zou kunnen maken, heeft bij mij dus wel even moeten pruttelen.

Eens kijken of ik dat voor de testronde van 16 november ga redden, anders zal een iets verbeterde versie van afgelopen testronde spelen.

[ Voor 20% gewijzigd door Vaan Banaan op 03-11-2019 21:10 ]

[Anoniem: 1272616]

Hallo
Graag zou ik dit ook willen oppakken, maar het installeren van het Caia verloopt niet helemaal soepel...
Ik kan het .tar.gz bestand downloaden, en ook het uitvoeren van dat bestand (met "tar –xzf caia_gomoku_linux64.tar.gz") gaat nu wel goed, maar de tweede stap, het daadwerkelijk installeren van caia (deze: "caia_install_gomoku/install_game.sh gomoku") lukt niet. Eerst kreeg ik "make: command not found", en later "g++: command not found".

Weet iemand hier hoe ik dit kan oplossen?
En in welke cli zouden deze commands precies uitgevoerd moeten worden?

[ Voor 0% gewijzigd door Anoniem: 1272616 op 06-11-2019 18:09 . Reden: Typo ]

[Vaan Banaan]

Het lijkt erop alsof je GCC nog niet hebt geïnstalleerd, om de code te kunnen compileren.

Aangezien je het over een CLI hebt, gebruik je waarschijnlijk Windows?
Als je op 10 zit, kun je met Windows Subsystem for Linux een distributie toevoegen https://docs.microsoft.com/en-us/windows/wsl/install-win10
Daarna zou je in de bash(?) shell van die distributie de edit2 commando's van Joep moeten kunnen uitvoeren.

Als je op een oudere Windows versie zit, heb je pech (net zoals ik)
Want dan zal dat ding nooit willen compileren.

[KopjeThee]

Dit lijkt mij een klusje voor deep reinforcement learning om de waarde van een stelling te bepalen.

[Vaan Banaan]

Ik weet nog niet hoe ik daarmee moet beginnen.
Voor deze competitie heb je:
• 5 seconden CPU tijd per spel, single threaded
• je kan niet vooruitdenken tijdens de beurt van de ander
• alle code moet in 1 source file, niet groter dan 1,44MB
• je mag niets naar een bestand schrijven / uit een bestand lezen
Daarom heb ik de machine-deep-reinforcement-neural-network-learning-glazen-bol-hocus-pocus voor de online versie bij voorbaat al opgegeven.

Maar ik wil nog wel iets met een opening book doen, als ik er tijd voor heb.
Die zou misschien wel met hulp van al die hippe technieken gemaakt kunnen worden.

Ik begin dan "gewoon" met de Monte Carlo Tree Search.
Grofweg werkt dat als volgt:
• Je kijkt naar een zet (selection).
• Dan kijk je welke mogelijke zetten daarna mogelijk zijn (expansion).
• Van een mogelijke zet knikker je daarna nog een hele rits random stenen op het bord, totdat het potje klaar is (simulation)
Dat levert een winst / verlies / gelijk spel op
• Die uitkomst (#simulaties: +1, score: +2(bij winst) of +1(bij gelijkspel) o.i.d.) tel je op bij je selection / expansion (update / back propagation)
Daarmee krijg je dus een idee hoe goed / slecht een zet is. Door expansion zetten meer te simuleren wordt die uitkomst steeds betrouwbaarder.

De simulation fase kun je ook nog iets slimmer maken. Dat heet dan blijkbaar policy of reinforcement learning. Die kan supervised (met kennis van een mens) of unsupervised (doe maar wat en vind zelf uit of dat goed of slecht is)
Dan lees ik nog van alles over agents en exploration / exploitation en bla bla bla wat je daarvoor kan gebruiken.
Inmiddels snap ik de wat-en-hoe's (en dan is het smijten met al die termen ook allemaal niet zo magisch meer)

Maar voor nu heb ik nog andere ideeën die ik eerst aan mijn bot wil toevoegen.
Inmiddels is de testronde van 16 november geweest en staat de bot 3de. Dit keer redelijk los van de subgroep daaronder.
De threat space search (of VCT / VCF of whatever) zit er nu in en lijkt af en toe zijn werk te doen.
Dat was nogal stressen, de code heb ik vannacht nog op het laatste moment opgestuurd, maar lijkt het zonder fouten te doen.
Wel 4 fails vanwege de tijdslimiet (na 50-60 zetten is die door zijn tijd heen)

Dus nu weer verder optimaliseren.
-edit-
En toch nog wat bugs pletten. Ik heb een fabeltastische optimalisatie gemaakt, waarbij mijn bot een paar zetten voor het einde kan zien, dat hij hoe dan ook gaat winnen.
Het probleem is, dat die daarna de pot niet altijd zo snel mogelijk afmaakt. En met het threat space search is dat alleen maar erger geworden.
Hier: https://www.codecup.nl/showgame.php?ga=147879 crasht de tegenspeler (wit) al bij de eerste zet.
Zijn zetten worden daarna voortgezet met random zetten door de "scheidsrechter", waardoor ik (zwart) dus eigenlijk heel makkelijk kan winnen. (Moet in zet 11 kunnen)
Maar de bot speelt gewoon nog vrolijk zijn TSS routine tot in het frustrerende door. En maakt het pas af, nadat die bij toeval in zet 17 de killer-move doet.

-edit2-
De testronde van 7 december is geweest.
Ik heb aan de laatste versie een transposition table toegevoegd, met behulp van zobrist hashes, zodat hij stellingen niet dubbel gaat doorzoeken.

Ik sta zowaar 1ste met wel 1 punt verschil met nummer 2
Nog wel 3 keer een fail vanwege tijdoverschrijding. Maar ik heb de potjes tegen (nu) nummer 2 wel gewonnen en dat was me tot dusver nog geen enkele keer gelukt.

[ Voor 46% gewijzigd door Vaan Banaan op 07-12-2019 14:28 ]