[Wedstrijd] CodeCup 2022 - Spaghetti

[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 Spaghetti, een variatie van Black Path.
CodeCup website: https://www.codecup.nl/intro.php

Over het spel

Spaghetti wordt gespeeld met 2 spelers op een bord van 9 x 7 (h x b) vakjes Blauw heeft zijn thuisfront links, rood rechts. Het spel start met 2 vakjes gevuld (door de scheidsrechter bepaald) De spelers moeten om en om 1 van 3 tegeltjes op het bord leggen. Elk tegeltje bestaat uit 2 pad delen, die je op een willekeurig lege plek mag neerleggen. Het spel stopt als het hele bord vol ligt.
Als een speler een tegeltje neerlegt, waardoor een pad ontstaat naar beide zijkanten, krijgt die speler punten. Het aantal punten is de lengte van het pad vanaf het gelegde tegeltje tot aan de eigen zijde.
In het geval dat het pad de laatst gelegde tegel meerdere keren doorloopt, telt de langste route.
Paden die naar de boven- of onderkant lopen, leveren geen punten op. Dat geldt ook voor een pad helemaal van boven naar beneden.
Als een speler een pad maakt naar 2 punten aan dezelfde zijkant levert dat 3 strafpunten op. Het maakt niet uit of die zijde van de speler is, of van de tegenstander.
Als een speler een cyclisch pad maakt, levert dat 5 strafpunten op.
Beide spelers beginnen met 50 punten. Elk potje speel je een keer met blauw en een keer met rood met dezelfde startopstelling. Bovenstaand voorbeeld is ook als voorbeeld spel op de site te bekijken.

Talen waarin je mee kan doen

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

Competitie

De finale wordt op 22 januari 2022 gespeeld.

Je kunt op elk moment een (nieuwe) versie van je programma opsturen.
Die krijgt maximaal 30 seconden CPU denktijd, op een 2GHz XEON CPU, single threaded met max 2GB geheugen.
Als het programma een spel volgens de regels kan spelen, zal die automatisch meedoen aan een eerstvolgende testcompetitie.
Zo kun je nagaan, hoe goed je programma het op dat moment ten opzichte van anderen doet.
Je kunt alle potjes van alle testcompetities op de site bekijken om zo nieuwe tactieken te ontdekken. Bij elke testcompetitie zijn er altijd wel een aantal nieuwe spelers.

10 juli 2021	Testcompetitie
31 juli 2021	Testcompetitie
21 augustus 2021	Testcompetitie
11 september 2021	Testcompetitie
2 oktober 2021	Testcompetitie
23 oktober 2021	Testcompetitie
13 november 2021	Testcompetitie
4 december 2021	Testcompetitie
25 december 2021	Testcompetitie
8 januari 2022	Testcompetitie
22 januari 2022	Finale

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.
Hierbij zit een referee die de uitslag van een spel een html zet, zodat je het spel achteraf in je browser kunt bekijken. Ook zijn er 3 spelers toegevoegd.
De rest (manager en caiaio) moet je zelf compileren.

[ Voor 16% gewijzigd door Vaan Banaan op 16-07-2021 15:25 ]

[Vaan Banaan]

Het leuke bij dit spel vind ik, dat je niets kan wegleggen, wat tegen de regels is. Je kan altijd elk tegeltje op een willekeurig lege positie van het bord leggen. Dus bij dit spel gaat het puur om tactiek.

Ik ga dit jaar maar weer los met Monte Carlo. Heel veel random potjes laten spelen en dan na een tijdje kijken wat het beste lijkt te werken.
Dit jaar ook weer totaal 30 seconden denktijd per speler, voor dit spel wel meer geheugen (2GB) tot je beschikking.

-edit-
Tweaker Soultaker (winnaar 2011 met DVONN) maakt op het forum daar wel een heel goede opmerking: Prisoners Dilemma

2 plegers van een misdrijf kunnen een gevangenisstraf krijgen.
Ze kenden elkaar niet van voor het misdrijf en mogen ook niet met elkaar communiceren.
De lengte van de straf (of vrijuit gaan) per persoon hangt af van wie zwijgt of de ander verraadt.
Ze weten dat deze afspraak voor beide geldt.

	B zwijgt (cooperate)	B verraadt A (defect)
A zwijgt (cooperate)	Beide 1 jaar	A: 3 jaar B: vrijuit
A verraadt B (defect)	A vrijuit B: 3 jaar	Beide 2 jaar

A kent B dus niet heeft daarom geen idee wat B zal doen:

• Als B zwijgt (cooperate), zal A de ander verraden (defect)
  Vrijuit gaan is beter dan 1 jaar zitten
• Als B verraadt (defect), zal A de ander ook verraden (defect)
  2 jaar zitten is in ieder geval nog beter dan 3

A zal B dus altijd verraden. (defect)
B denkt precies hetzelfde over A, en zal A ook verraden. (defect)
Dus beide 2 jaar gevangenisstraf (defect - defect).

Zie hier het dilemma.
Als ze elkaar hadden kunnen vertrouwen en gezwegen (cooperate - cooperate) hadden ze maar 1 jaar gekregen.

Spaghetti voorbeeld max cooperate-cooperate vs defect-defect:

Maar als merkt dat een speler altijd cooperate kun je daar misbruik van maken door zelf defect zetten te doen. Dat levert dan nog veel meer punten op. Spaghetti always cooperate-defect Dit is hetzelfde als: A zwijgt altijd (cooperate) B weet dat op een of andere manier, verraadt (defect) en gaat vrijuit

-edit-
Op 10 juli is met (nog maar) 8 deelnemers + 3 organisatie, de eerste testcompetitie gespeeld.
De winnaar heeft "maar" 11 van 18 potjes gewonnen.
Dit potje is verloren met 89 - 79, maar beide dus nog steeds veel punten.

Goed, dat wordt de komende weken weer heel veel wikipedia....

[ Voor 237% gewijzigd door Vaan Banaan op 19-07-2021 14:10 ]

[Vaan Banaan]

Ik blijf gewoon stug doorposten, ook al zijn er nog geen reacties van anderen.

Vanmorgen is de 4de van 10 testrondes gespeeld, inmiddels 28 deelnemers (+4 onofficiële van de organisatie).
Hoewel de beste spelers vrij agressief spelen, lijkt me dat samenwerken uiteindelijk meer punten op kan leveren.

Een potje waar 2 spelers elkaar het licht niet gunnen, levert niks op. En elkaar blokkeren is in dit spel vrij eenvoudig.
Aan de andere kant heeft de winnaar, met in deze testcompetitie 62 potjes gespeeld, een gemiddelde van ruim 85 punten.
Dat krijg je met samenwerken nauwelijks voor elkaar, er zit dan ook nog veel kanonnenvoer tussen.

Ik ben weer een plekje gezakt (sta nu 4de) en wil iets doen met een waarschijnlijkheid van dom / agressief / meewerkend.
Versimpeld voorbeeld:
2 paden zijn al een eind gevorderd. Meewerkend zou zijn:

Blauw (ik) zet b1, rood r2, blauw b3, rood r4, beide krijgen nu 7 punten.

Andere scenario's: blauw zet b1

• Rood zet b3 en krijgt 1 punt.
  Daarmee weet blauw dat rood niet meewerkend is (of geen zetten vooruit denkt)
  In ieder geval zal blauw, bij een zet van rood op r2, ook direct de boel blokkeren met r4
• Rood zet iets heel anders dan r2, b3, of r4
  Blauw zet dan alsnog b3 en krijgt 7 punten
  Waarschijnlijk is rood geen slimme speler

Daarmee zou ik dan mijn tactiek kunnen aanpassen, door te blijven samenwerken, defensief gaan spelen, of voor enorme winst gaan.

Er zijn ook spelers die met 1 lang pad op het eind een slag proberen te slaan. Aangezien die tijdens het spel steeds allerlei andere paden het bos insturen, is mogelijk ook daar iets tegen te verzinnen.

[Vaan Banaan]

Ok, nog een post omdat het kan.
Door drukte is er een paar maanden niet veel van gekomen.
Ik sta nu 5de (van 44), hopelijk krijg ik mijn laatste ideeën er nog in voor de finale in januari.

De betere spelers maken zo te zien meerdere bijna paden naar de andere kant en gaan die pas voltooien als de ander ook een aantal bijna paden heeft om dat te doen.
Verder valt me op dat ze tot ongeveer halverwege het spel bijna alleen op hun eigen helft van het veld zetten doen. Daar had ik me nog totaal niet mee bezig gehouden, maar kan ik ook vrij makkelijk toepassen.
round0: 61 vakjes * 3 (links/rechtdoor/rechts) mogelijkheden,
round1: 60 * 3,
round2: 59 * 3, enz
Met maar de helft bij eigen zetten proberen, maakt de boom zeker in het begin minder breed, dus mogelijk een zet verder "denken"

Ik heb ook nog een poging gedaan om de Spaghetti Cygwin caia te porten naar een Windows native versie. Ik had de ballen verstand van Windows processen, consoles, asynchrone pipes, etc, dus dat bleek nogal een uitdaging achteraf.
Het werkt, maar daar is ook alles mee gezegd..... (Vanaf Windows7)
Het staat inmiddels op de site: https://www.codecup.nl/download_caia.php
De windows zip bevat source en alles is ook al gecompileerd om direct te proberen. Als je caiaio.exe runt, zal die een aantal potjes spelen met de player[x].exe testspelers (door de organisatie geleverd, geen source van)
De zetten worden gecontroleerd door de referee.exe (ook aangeleverd door de organisatie, dus geen source van) en die schrijft dat weer in een refereelog. Alle zetten per potje worden in een html gezet, zo kun je ze achteraf in je browser bekijken.
In principe is de caiaio spelonafhankelijk (zolang het communicatie protocol niet wijzigt) dus mogelijk kan die een volgende competitie ook nog mee.

[Soultaker]

Hey Vaan Banaan, bedankt voor het starten van deze topic!

Ik kwam zelf niet meer aan het insturen van een inzending toe (door een combinatie van weinig vrije tijd en weinig inspiratie hoe ik met het niet-nulsom-aspect van het spel om moest gaan), maar ik vind het leuk om te zien dat de CodeCup nog steeds aanwezig is op het Tweakers forum. (Ik heb in het verleden ook wel wat topics gestart, die niet altijd heel veel reacties kregen.)

Ik zie dat je als 11e geëindigd bent. Gefeliciteerd, dat is best een goede prestatie!

Hopelijk doe ik volgend jaar weer mee, en kunnen we ook wat Tweakers overtuigen mee te doen.

[Vaan Banaan]

Hoi @Soultaker ,

Ja, dit was echt een lastig probleem en ik heb er door tijdgebrek ook niet heel veel aan kunnen doen. Met mijn 2de (final) versie was ik in december dus nog 5de, maar die is met de finale wel gruwelijk ingehaald.
Overigens heeft @Boreus volgens mij dit jaar ook meegedaan, maar ook niet doorgezet tot het eind.
Ik ben niet verder gekomen dan MCTS met random playout en af en toe heel simpele pruning.
De bot ging daardoor heel vaak blind een pad maken, zonder de ander de kans te geven een ander pad te maken.
Maar wat ik van de betere spelers heb gelezen, is dat iedereen daarmee heeft geworsteld.
Dus ik ben er wel tevreden mee.

[offtopic Windows rant]
In september en oktober heb ik een poging gedaan om de caiaio (communicatie tussen de manager, referee en de players) te porten naar Windows native.
Daarmee kun je dan thuis je bot testen tegen de door CodeCup meegeleverde testspelers en scheidsrechter.
Man, man, man wat een drama was dat...
Windows stderr redirection is echt een WTF naar non "TTY"
Linux (en Cygwin) doen line buffering, daardoor kun je die prima redirecten naar een pipe.
Maar Windows moet weer eigenwijs zijn: standaard full buffering.
En setvbuf line buffering werkt uiteraard ook niet https://docs.microsoft.co...nce/setvbuf?view=msvc-170

_IOLBF
For some systems, this provides line buffering. However, for Win32, the behavior is the same as _IOFBF - Full Buffering.

Omdat ik ervan moest uitgaan dat een fflush(stderr) nooit nodig zou hoeven zijn, moest ik de stderr dan maar redirecten naar een Pseudo terminal. Want alles op consoles is gelukkig nog wel standaard nonbuffered.
Dus dat was feest met hidden consoles en dan maar van het "scherm" lezen. Consoles en Windows....

Komende maanden nog maar eens fatsoeneren, mogelijk dat het de volgende competitie wat tweakers over de streep kan trekken, zolang de CodeCup organisatie nog geen platform onafhankelijke versie heeft.
Ze waren in ieder geval wel blij met mijn poging.
Overigens zag ik dat jij ooit ook een bijdrage hebt gedaan wat betreft CPU timing.