[Wedstrijd] CodeCup 2023 - Entropy: Chaos and Order Vorige deel Overzicht Volgende deel Laatste deel

Dit topic is onderdeel van een reeks. Ga naar het meest recente topic in deze reeks.

Pagina: 1
Acties:

Acties:
  • +4 Henk 'm!

  • Vaan Banaan
  • Registratie: Februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
Afbeeldingslocatie: https://tweakers.net/i/XoGynUh_Bb0IquxTMprchPjilR0=/full-fit-in/4000x4000/filters:no_upscale():fill(white):strip_exif()/f/image/ghWo5RCdYjOxTINTrVxWrvZ0.png?f=user_large

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 Entropy, een abstract strategisch spel ontworpen in 1977 door Eric Solomon.
CodeCup website: https://www.codecup.nl/intro.php

Talen waarin je mee kan doen

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

Over het spel

Entropy wordt gespeeld met 2 spelers (Chaos en Order) op een bord van 7 x 7 vakjes.
Er zijn in totaal 49 fiches in 7 kleuren, van elke kleur 7 fiches.

Het spel start met een leeg bord.
Chaos pakt blind een fiche uit een zak en legt die op een willekeurig leeg vak.

Afbeeldingslocatie: https://tweakers.net/i/Ob9cnui02fZx0G5FtVfwgWFSHSE=/full-fit-in/4000x4000/filters:no_upscale():fill(white):strip_exif()/f/image/GUUYS454IYXdDR0Y7j0AGcs9.png?f=user_large
Order mag (hoeft niet) een fiche horizontaal of verticaal verschuiven naar een ander leeg vak op die lijn.
Als er ergens al een ander fiche op de horizontale of verticale lijn ligt, mag je daar niet overheen "springen".

Daarna pakt Chaos weer blind een fiche en plaatst die op het bord.

Order kan weer kiezen om het bord zo te laten, of één willekeurig fiche horizontaal of verticaal te verschuiven.

Dit wordt herhaald tot het bord vol ligt.

Afbeeldingslocatie: https://tweakers.net/i/W66c6mHlIlUSk_FDM1IUH23kPrw=/full-fit-in/4000x4000/filters:no_upscale():fill(white):strip_exif()/f/image/p1fiU36jO5XlJTuJYu98GcLV.png?f=user_large

In het spel kan alleen Order punten scoren.
Dit kan door het maken van palindromen met de kleuren van de fiches.
Net zoals met woorden (lepel, kok) lees je van links naar rechts hetzelfde als van rechts naar links.

De score is de lengte van de palindroom, binnen langere palindromen (bijvoorbeeld: Be t/m Ge) bevinden zich altijd ook kortere, die punten tellen ook mee.
Een ander voorbeeld (niet in de afbeelding) is bijvoorbeeld de palindroom:
oranje-oranje-oranje.
Die is 3 + 2 + 2 = 7 punten waard.

Afbeeldingslocatie: https://tweakers.net/i/TcGNIxDAJ1SvROZXXZFugGeMJ38=/full-fit-in/4000x4000/filters:no_upscale():fill(white):strip_exif()/f/image/CrkSyB74lLgNbIxx7qJj7Nzj.png?f=user_large

Chaos probeert de fiches dus steeds zo neer te leggen, dat Order zelfs met schuiven lastig palindromen kan maken.

Het spel gaat door tot het bord vol ligt
(en ook alle fiches op zijn)

Afbeeldingslocatie: https://tweakers.net/i/ZHl-3jXXMTKGa8ZPE6y45PRIvaY=/full-fit-in/4000x4000/filters:no_upscale():fill(white):strip_exif()/f/image/2HuoRGgRRegZsD2Crn4crs0n.png?f=user_large

Bij de CodeCup wedstrijd worden daarna die punten gebruikt voor de eindscore.
Chaos begint met 280 punten, het aantal punten dat Order heeft gescored (93 in bovenstaand voorbeeld) wordt daarvan afgetrokken.
Order begint met 120 punten, de punten die zijn gescored met de palindromen worden daarbij opgeteld.
Dus de eindstand is:
Chaos: 187, Order: 213

Daarna wordt het spel nog een keer gespeeld waarbij de rollen worden omgedraaid.

Bovenstaand voorbeeld is ook als voorbeeld spel op de site te bekijken.


Software om het spel lokaal te spelen / testen

Om thuis te kunnen testen, is door de CodeCup organisatie een software pakketje gemaakt. https://www.codecup.nl/download_caia.php
Dit is beschikbaar voor Linux, OSX (ARM) en Windows.

De software bevat een door de organisatie gecompileerde scheidsrechter en ook 3 gecompileerde test spelers.
Verder een manager die de spelers selecteert en de caiaio voor de communicatie tussen alle processen.
Voor Mac en Linux is een install_game.sh script die o.a. de manager en de caiaio compileert, bij de Windows versie is dat al gebeurd.

De referee maakt van elk spel een html bestand, zodat je het spel achteraf in een web browser kunt bekijken.
Om het hele spul te starten moet je de caiaio uitvoeren (Voor Mac en Linux dus eerst install_game.sh om de manager en de caiaio te compileren)
Verdere uitleg is te vinden in de bijgeleverd PDF's.

Competitie

De finale wordt ergens in de 2de helft van januari 2023 gespeeld. (Exacte dag is nog niet bekend)

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.
Dan heb je gelijk een idee, hoe goed je programma het op dat moment ten opzichte van anderen doet.

Verder kun je 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.

20 augustus 2022
Testcompetitie
waarschijnlijk 3 weken later
Testcompetitie
waarschijnlijk 3 weken later
Testcompetitie
waarschijnlijk 3 weken later
Testcompetitie
waarschijnlijk 3 weken later
Testcompetitie
waarschijnlijk 3 weken later
Testcompetitie
....
Testcompetitie
2de helft januari 2023
Finale


Prijzen

Hoofdprijs: Eeuwige roem en een vermelding op de wiki Wikipedia: CodeCup

Tweakers in die lijst:
Soultaker: winnaar 2011
Vaan Banaan: beste NL speler 2020

[ Voor 3% gewijzigd door Vaan Banaan op 26-07-2022 22:15 ]

500 "The server made a boo boo"


Acties:
  • +2 Henk 'm!

  • Vaan Banaan
  • Registratie: Februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
Dit keer weer een bestaand spel, met een oneindig hoeveelheid aantal combinaties.

In het VK wordt jaarlijks de Mind Sports Olympiad in Londen gehouden en ook daar wordt / werd Entropy gespeeld. Van 2018 staat de 4u25m livestream online.
(Link naar 23m09s https://www.youtube.com/watch?v=05zpFDcvqp8&t=1389s daar worden de regels uitgelegd)


Het spel ziet er zoals gewoonlijk super simpel uit om te begrijpen, maar qua tactieken zal het weer een enorme breinbreker worden.
Het niveau van de betere CodeCup stamgasten ligt ook flink hoog. Als je ambitieus bent, gaat dat serieus veel tijd kosten.
Vandaar dat de finale pas over zowat een half jaar is.

Ik heb op dit moment nog geen idee hoe ik dit spel ga aanpakken.
Voor de eerste testcompetitie van 20 augustus zal het een random runner worden, om te kijken of ik een fatsoenlijk framework in elkaar kan zetten. Als ik dat al haal, anders wordt het een van de latere testcompetities.
Maar het zal sowieso broeden worden op wat een goede zet is en wat niet, om daar een of andere heuristic van te kunnen maken. En hoe zo slim mogelijk een aantal zetten door te kunnen rekenen met zo belachelijk veel mogelijkheden.

[ Voor 152% gewijzigd door Vaan Banaan op 26-07-2022 22:17 ]

500 "The server made a boo boo"


Acties:
  • +1 Henk 'm!

  • Dricus
  • Registratie: Februari 2002
  • Laatst online: 15:33

Dricus

ils sont fous, ces tweakers

Leuk spel deze keer! Uniek ten opzichte van vorige jaren (voor zover ik het meegekregen heb) is dat het een "asymmetrisch" spel is. Order en chaos hebben totaal andere "moves" tot hun beschikking en een tegengesteld doel.

Het lukt mij de afgelopen jaren maar niet om door te zetten met CodeCup. Ik begin altijd wel met een basisopzet, maar doorzetten om ook echt iets af te maken wil niet echt lukken. Vorig jaar heb ik nog een zeer basic MCTS algoritme geschreven, maar dat was bij lange na niet genoeg om enigszins mee te doen...

Ik ga wel weer een poging wagen in Java. Ik zie wel hoe ver ik kom. Deze keer ga ik maar eens met Minimax aan de slag denk ik.

[ Voor 14% gewijzigd door Dricus op 28-07-2022 15:01 ]

Stel niet uit tot morgen wat je vandaag nog tot morgen kunt uitstellen...


Acties:
  • +1 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 00:05
Hier nog wat leesvoer qua strategie: Abstract Games issue 11 (PDF), pagina 5 t/m 9.
Dricus schreef op donderdag 28 juli 2022 @ 14:54:
Deze keer ga ik maar eens met Minimax aan de slag denk ik.
Ik vermoed dat de meeste deelnemers weer voor MCTS zullen gaan; dat lijkt de trend te zijn de afgelopen jaren.

Aan de andere kant, de enige keer dat ik gewonnen heb was met een minimax-algoritme (concreet, negamax met alfa-beta-snoei), dus het kán wel. Belangrijk voor minimax is om een goede evaluatiefunctie voor tussentijdse posities te vinden. Een van de grote voordelen van Monte Carlo technieken is dat ze geen tussentijdse evaluatie-functie nodig hebben (al kan het wel helpen, zoals de policy network in AlphaGo).

Acties:
  • 0 Henk 'm!

  • Dricus
  • Registratie: Februari 2002
  • Laatst online: 15:33

Dricus

ils sont fous, ces tweakers

Soultaker schreef op vrijdag 29 juli 2022 @ 18:14:
Ik vermoed dat de meeste deelnemers weer voor MCTS zullen gaan; dat lijkt de trend te zijn de afgelopen jaren.
Ik doe sowieso niet mee om te winnen, maar vooral voor het plezier. De vraag is dan: Wil ik vooral bezig zijn met het tweaken van UCB/RAVE formules, exploration/expoitation, etc, of wil ik meer bezig zijn met manieren om een board state te evalueren? Momenteel heb ik meer zin in het tweede, dus daar begin ik dan maar mee :). Misschien doe ik wel beiden en laat ik ze tegen elkaar spelen om te beslissen welke het wordt.

PS: Oh, en ik vind het ook wel een leuke uitdaging om dit soort dingen primair met test-driven development te bouwen.

[ Voor 8% gewijzigd door Dricus op 29-07-2022 19:17 ]

Stel niet uit tot morgen wat je vandaag nog tot morgen kunt uitstellen...


Acties:
  • 0 Henk 'm!

  • Vaan Banaan
  • Registratie: Februari 2001
  • Niet online

Vaan Banaan

Heeft ook Apache ontdekt

Topicstarter
Met mijn eerste deelname aan CodeCup 2020 werd ik 2de met Gomoku (soort 5 op een rij) met alpha-beta pruning en met elke diepte een sortering. Dat was achteraf echt beginnersgeluk.
Het jaar daarop gingen inderdaad de meesten voor Monte Carlo. (7de geëindigd)
Vorig jaar ook veel Monte Carlo (11de geëindigd), de extra moeilijkheid was: samenwerken of niet (prisoner's dilemma)

Met dit spel dus 2 rollen.
Maar ik denk dat je hetzelfde algoritme kunt gebruiken.
Zetten waar je als Order moeite mee hebt, speel je juist in de rol van Chaos
@Soultaker _/-\o_ Hoe heb je dat nou weer gevonden, dat zijn tactieken beschreven door degene die het spel in 1977 heeft ontworpen!

Op SourceForge is het spel voor Windows te vinden. Het is wat gedateerd (2001) maar je kunt daarmee wel tegen een zwakke of sterke AI spelen. https://sourceforge.net/projects/es-entropy/files/

500 "The server made a boo boo"


Acties:
  • 0 Henk 'm!

  • Douweegbertje
  • Registratie: Mei 2008
  • Laatst online: 12-05 19:36

Douweegbertje

Wat kinderachtig.. godverdomme

Oei, ik ga er misschien eens naar kijken. Ik zal het echt niet halen om iets fatsoenlijks in elkaar te zetten want dit staat zo ver van mij vandaan qua dagelijks werk :+ Dank voor het topic!

Ik vind overigens de talen wel "grappig" - Geen C# of Go, maar toch wel wat dingen die je normaal wat minder ziet.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 00:05
Vaan Banaan schreef op zaterdag 30 juli 2022 @ 02:42:
Op SourceForge is het spel voor Windows te vinden. Het is wat gedateerd (2001) maar je kunt daarmee wel tegen een zwakke of sterke AI spelen. https://sourceforge.net/projects/es-entropy/files/
Fuu.. Ik kan nog niet van die AI winnen. Wel leuk om te oefenen. (Het draait ook prima op Linux trouwens.)

Acties:
  • 0 Henk 'm!

  • allemensen
  • Registratie: Maart 2021
  • Laatst online: 14-05 09:15
Oh ik had helemaal gemist dat de Codecup ook op Tweakers werd besproken! Dat had me wel geholpen, aangezien ik de laatste twee jaar de dominante strategie had gemist 8)7
Dit jaar heb ik een goed begin, maar nu begint het natuurlijk lastig te worden om veel te verbeteren.


Die bot op SourceForge is niet zo heel goed, die zou je met je eigen bot makkelijk moeten kunnen verslaan. Zelf winnen daarentegen is wel lastig...
Ook kwam ik dit Youtube filmpje tegen, waarin er commentaar gegeven wordt bij een aantal wedstrijden van het Entropy wereldkampioenschap.


MCTS lijkt me enigzins lastig, want ik zou niet verwachten dat random spelen (de rollout strategy) enigzins goed is. Maar als je dat weet te tackelen, zou MCTS juist goed moeten zijn, omdat er veel duidelijk slechte zetten zijn. Minimax is juist goed in slechte zetten voorkomen, maar kan niet zo goed inschatten hoeveel punten de toekomstige zetten gaan opleveren.

[ Voor 23% gewijzigd door allemensen op 18-09-2022 20:46 ]


Acties:
  • 0 Henk 'm!

  • allemensen
  • Registratie: Maart 2021
  • Laatst online: 14-05 09:15
Nog ongeveer een maand tot de finale! Mijn programma wordt steeds beter, en ik doe het zeker niet slecht. Maar ik gok dat ik hier niet mee ga winnen. Ik ben op een minimax-variant blijven hangen, met een slimme evaluatie functie kom je echt al heel ver. Maar ik denk dat Entropy ook erg geschikt is voor een MCTS aanpak.

Doen er nog andere tweakers mee? Ik ben benieuwd of iemand nog slimme inzichten heeft.
Pagina: 1