[Wedstrijd] CodeCup 2024 - Sudoku

[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: Sudoku
CodeCup website: https://www.codecup.nl/intro.php

Over het spel

Bij deze CodeCup competitie is het de bedoeling met 2 spelers een sudoku te genereren.
Het spel start met een lege sudoku.
De spelers vullen om en om een getal in.
Een speler die een ongeldige zet maakt, verliest met 0 - 2.
Een speler die een onmogelijk oplosbare sudoku maakt, verliest met 1 - 2.
Een speler, die denkt dat de opgebouwde sudoku een eenduidige oplossing gaat krijgen (of al heeft), geeft dat aan met een uitroepteken. Dit mag in de eigen beurt (dus zet+!), of met alleen het uitroepteken. Dat laatste kan als de andere speler een eenduidige oplossing heeft gemaakt, maar het niet doorhad.	Speler 2 denkt dat speler 1 een eenduidige oplossing heeft gemaakt. Dat blijkt juist te zijn, speler 2 wint.
Als de sudoku inderdaad een eenduidige oplossing heeft, heeft die speler gewonnen met 2 - 1. Als er toch meerdere oplossingen blijken te zijn, verliest die speler met 0 - 2
Een voorbeeld spel is op de site te bekijken.

Talen waarin je mee kan doen

C, C++, Java, Javascript, Python, Rust, Go, Haskell, Pascal en OCaml
C# wordt dus niet ondersteund
Een speler krijgt 30 seconden CPU denktijd per spel (meer op https://www.codecup.nl/rules_tech.php)

Competitie

De finale wordt 20 januari 2024 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.
Je mag niet naar bestanden schrijven en tijdens de beurt van de andere speler, staat je programma op pauze.
Als het programma een spel volgens de regels kan spelen, zal die automatisch meedoen aan een eerstvolgende testcompetitie tot en met de finale.
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.
De testcompetities en de finale starten meestal op een zaterdagochtend (ik geloof om een uur of 9)

5 augustus	Testcompetitie
26 augustus	Testcompetitie
16 september	Testcompetitie
7 oktober	Testcompetitie
zondag 29 oktober	Testcompetitie
18 november	Testcompetitie
9 december	Testcompetitie
30 december	Testcompetitie
20 januari 2024	Finale

Prijzen

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

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 scheidsrechter maakt van elk spel een html bestand, zodat je het spel achteraf in een web browser kunt bekijken.
Dit ziet er net zo uit, als het voorbeeld spel op de site.
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.

[ Voor 38% gewijzigd door Vaan Banaan op 01-08-2023 09:25 ]

[Vaan Banaan]

Dit is weer eens een totaal andere competitie dan die van vorige jaren.
Was ik toen vooral bezig met uitzoeken van allerlei minimax algoritmes (en heb ik vorig jaar uiteindelijk niet eens meegedaan), lijkt me hier de focus liggen op een sodoku generator / solver.

De moeilijkheid zit hem er natuurlijk in dat de andere speler ook mee bouwt.
Het doel wordt dan dus de sudoku uiteindelijk zo op te bouwen, dat, waar de tegenstander ook iets invult, je daarna met de laatste zet altijd een eenduidige oplossing kan maken.

Het niveau van de CodeCup competities is elk jaar heel hoog. Het zal me niets verbazen, als iemand op een of andere manier de 5,472,730,538 unieke sudoku's in 2 GB weet te persen.

In ieder geval kan ik hier vrijwel direct ergens mee beginnen. Ongetwijfeld zal ik nog wel allerlei problemen tegenkomen, maar het is weer eens wat anders dan weken wiki-spitten.

[ Voor 14% gewijzigd door Vaan Banaan op 17-07-2023 01:02 ]

[Anoniem: 80910]

Ik kom maar op 387.420.489 mogelijkheden het is toch 9*9*9*9*9*9*9*9*9 ?

[Soultaker]

Yes! Een nieuwe Codecup. En wel een leuk probleem dit jaar. Sudoku is bekend genoeg dat het spel makkelijk uit te leggen is, en veel programmeurs hebben ooit wel eens een Sudoku solver geschreven, dus is het ook niet zo moeilijk om een simpele speler te implementeren.

Tegelijkertijd denk ik dat knap lastig kan zijn om een sterke speler te bouwen. Met simpelweg een snelle Sudoku solver ben je er nog niet.

Het enige nadeel van dit spel is dat het als mens praktisch niet te spelen is. Dat is jammer, want in het verleden probeerde ik vaak intuïtie voor spelstrategie te ontwikkelen door tegen de voorbeeldspelers (of een zwakke versie van mijn eigen AI) te spelen. En de meest memorabele edities van de CodeCup zijn de jaren waarin het spel zelf ook leuk was om te spelen. Voor mij waren dat vooral: Caïssa (ja ik ben oud), Dvonn, Poly-Y, AYU, Less, en Blackhole.

Voor deelnemers die niet bekend zijn met Sudoku solvers, hier een aantal nuttige links:

1. Peter Norvig's Solving Every Sudoku Puzzle: de basistechniek
2. Donald Knuth's Dancing Links en Algorithm X, vaak gecombineerd tot DLX. Ik ken geen artikel waarin de toepassing op Sudoku compleet uitgelegd wordt maar als je zoekt op "Sudoku DLX" vind je wel wat. Dit is meestal een snellere versie van Norvig's backtracking algoritme.
3. Tom Dillon's Nerd Sniped: A Sudoku Story, de snelste Sudoku solver die er is, gebaseerd op technieken van SAT solvers.

(Alledrie de technieken zijn min of meer op backtracking gebaseerd.)

Anoniem: 80910 schreef op dinsdag 18 juli 2023 @ 14:05:
Ik kom maar op 387.420.489 mogelijkheden het is toch 9*9*9*9*9*9*9*9*9 ?

Het zijn 9×9 = 81 vakjes die je moet vullen, niet 9, dus kom je op 9⁸¹. Dat is dan weer een grove overschating omdat de beperkingen van de puzzel (elk cijfer mag maar 1 keer voor komen in elke rij, kolom en 3x3 blok) het aantal mogelijkheden aanzienlijk vermindert.

(Bijvoorbeeld, een eenvoudige observatie is dat elke rij een permutatie is van de cijfers 1 tot 9, dus het aantal mogelijkheden per rij is niet 9⁹ maar 9! (9 faculteit). Dan hou je 9!⁹ over, maar aangezien je de eerste rij willekeurig kunt kiezen en de laatste rij maar op 1 manier ingevuld kan worden kun je dat reduceren tot 9!⁷, en zo kun je nog wel even doorgaan. De echte analyse is ingewikkelder.)

[allemensen]

Mee eens, @Soultaker, het lijkt me moeilijk om een sterk programma te maken dit jaar. Een of twee zetten voor het einde voorspellen wie gaat winnen moet vast lukken, maar eerder? De branching factor is vrij hoog, en het checken van unieke oplossingen is ook niet super snel. En jammer dat het als mens niet echt te spelen is.

Maar eens nadenken of het toch mogelijk is vooraf een inschatting te maken van de winkans... Misschien werkt MCTS met een of andere slimme rollout wel?

[Joep]

Ik zou graag mee willen doen, maar ik zoek me rot om uit te vogelen hoe ik GNU GCC kan downloaden en instellen voor Visual Studio op Windows. Heb geen trek in de Windows Subsystem for Linux, want dat heb ik een eerdere editie al geprobeerd en was onwerkbaar. De drempel voor beginners en/of programmeurs met amper Linux-kennis ligt wederom behoorlijk hoog.

Edit: Blijkbaar heb je MinGW of Cygwin nodig om de GCC compiler werkend te krijgen onder Windows. En zo wordt meedoen aan deze wedstrijd weer teveel gedoe

Edit: Wat Soultaker hieronder zegt

[ Voor 22% gewijzigd door Joep op 21-07-2023 00:14 ]

[Soultaker]

Joep schreef op donderdag 20 juli 2023 @ 21:38:
Edit: Blijkbaar heb je MinGW of Cygwin nodig om de GCC compiler werkend te krijgen onder Windows. En zo wordt meedoen aan deze wedstrijd weer teveel gedoe

Waarom wil je per se GCC gebruiken? Je kunt lokaal in principe elke C/C++ compiler gebruiken, tenzij je hele bijzondere dingen van plan bent.

(Overigens vind ik MSYS zelf erg fijn werken! En de instructies om GCC te installeren staan letterlijk op de homepage https://www.msys2.org/)

[Joep]

Soultaker schreef op donderdag 20 juli 2023 @ 23:24:
[...]

Waarom wil je per se GCC gebruiken? Je kunt lokaal in principe elke C/C++ compiler gebruiken, tenzij je hele bijzondere dingen van plan bent.

(Overigens vind ik MSYS zelf erg fijn werken! En de instructies om GCC te installeren staan letterlijk op de homepage https://www.msys2.org/)

Ik dacht dat een fout die ik kreeg te maken had met de manier waarop ik m'n programma gecompiled had. I was wrong. Programmaatje doet 't nu

[Soultaker]

Bumpje: aanstaande zaterdag is de eerste testcompetitie. Als je een werkend programma hebt dat je wil testen tegen andere spelers is het handig om dat uiterlijk vrijdagavond in te sturen.

Ik heb al een versie ingestuurd. Het presteert vrij goed tegen de bij CAIA meegleverde voorbeeldspelers. Ik ben benieuwd hoe het gaat tegen andere programma's.

[allemensen]

Ik heb ook een inzending, maar dat is van het niveau "Kan ik nu winnen? Ja = yay! Nee = random zet". Verder ben ik er nog weinig mee bezig geweest.

Heb je iets slims kunnen bedenken, @Soultaker? Of is het vrij simpel een paar zetten diep kijken en veel sudoku's oplossen?

[Soultaker]

allemensen schreef op donderdag 3 augustus 2023 @ 20:41:
Ik heb ook een inzending, maar dat is van het niveau "Kan ik nu winnen? Ja = yay! Nee = random zet". Verder ben ik er nog weinig mee bezig geweest.

Je moet ergens beginnen!

Heb je iets slims kunnen bedenken, @Soultaker? Of is het vrij simpel een paar zetten diep kijken en veel sudoku's oplossen?

Zonder al te veel te verklappen: m'n huidige inzending is aanzienlijk slimmer dan dit. Sudoku's oplossen kost momenteel maar een klein percentage van de rekentijd.

Een interessante observatie is deze: bij de huidige versie van mijn speler lijkt het er sterk op dat de eerste speler een groot voordeel heeft. Als ik mijn speler tegen zichzelf laat spelen wint de eerste speler praktisch altijd. In eerste instantie dacht ik dat dat komt omdat mijn speler niet random genoeg is en dus altijd in dezelfde patronen vervalt als 'ie tegen zichzelf speelt, maar het bijzondere is dat het ook gebeurt tegen de voorbeeldspelers, b.v. player1 die (volgens mij) niet meer doet dan willekeurige (geldige) zetten.

Dat betekent niet dat ik verlies tegen de voorbeeldspelers, maar dat op het eerste moment in het spel waarop ik de uitkomst kan berekenen, ik als eerste speler (vrijwel) altijd gewonnen sta en als tweede speler (vrijwel) altijd verloren. Dat ik toch nog win als tweede speler komt doordat de voorbeeldspelers praktisch altijd een fout maken, maar spelers die minstens zo goed zijn als de mijne doen dat natuurlijk niet, dus ik verwacht dat mijn speler tegen goede tegenstanders gaat verliezen wanneer ik als tweede speel.

Dit is behoorlijk verrassend, want intuïtief heb ik geen idee waarom speler 1 een voordeel zou hebben ten opzichte van speler 2 in dit spel. Ik ben benieuwd of dit patroon ook zichtbaar is in de competitie.

[allemensen]

Ah dat klinkt interessant! Dat was ook zo bij Zuniq (2021), al had ik dat toen zelf niet door.

Dus goed spelen betekent waarschijnlijk zowel heuristisch goede zetten maken in het begin van het spel (bv MCTS), als het doorrekenen van (bijna) alle zetten zodra dit mogelijk wordt. Nou, genoeg om aan te knutselen dus!

[Vaan Banaan]

Het is inderdaad, net zoals Zuniq, een even / oneven wedstrijd.
Degene die begint, wil met een oneven aantal clues beurten eindigen en de ander een even aantal.

Het lijkt er volgens Soultaker dus op, dat je makkelijker kan uitkomen op altijd oneven aantal clues beurten, dan even.
Een aantal spelers zullen (later in de competitie) daar dan wel op anticiperen, door sudoku's te genereren die bijvoorbeeld de MCTS algoritmes om de tuin leiden. (Door te "lokken" met oppervlakkige zetten die veel winst simulaties geven, maar ergens heel diep met maar een paar paden toch net de pariteit om kunnen draaien)

-edit 5 augustus-

Gefeliciteerd Soultaker met deze testcompetitie gedeeld 1ste!
De verloren potjes zijn inderdaad allemaal als de andere speler mocht beginnen.

Het valt me op dat de betere spelers al best snel weten dat in x beurten een unieke sudoko gegenereerd kan worden. De laatste 30/40 zetten is gewoon vullen van de hidden of naked singles en zijn voor beide spelers allang bekend (en voor de verliezer uitstellen van het onvermijdelijke)
Dus stel:

+-+-+-+-+-+-+-+-+-+ |1| |3|4|5|6| |8|9| +-+-+-+-+-+-+-+-+-+ |4| |6|1|8|9| |3|5| +-+-+-+-+-+-+-+-+-+ |5|8|9|2|3|7|1|4|6| +-+-+-+-+-+-+-+-+-+

of

+-+-+-+-+-+-+-+-+-+ |4| |7|5|1|8| |6|9| +-+-+-+-+-+-+-+-+-+ |5| |8|6|2|9| |4|7| +-+-+-+-+-+-+-+-+-+ |6| |9|4|3|7| |5|8| +-+-+-+-+-+-+-+-+-+

Degene die nu aan de beurt is, wint door waar dan ook een cell te vullen.
Het aantal oplossingen van deze stellingen maakt dus niet uit,

[ Voor 58% gewijzigd door Vaan Banaan op 05-08-2023 17:23 ]

[Soultaker]

Vaan Banaan schreef op vrijdag 4 augustus 2023 @ 12:49:
Gefeliciteerd Soultaker met deze testcompetitie gedeeld 1ste!
En inderdaad alleen verloren als de andere speler mocht beginnen.

Bedankt! Welke speler was de jouwe (of wil je dat niet zeggen)?

Het verliep inderdaad zoals verwacht. Er is ook wat discussie op het CodeCup forum over het voordeel dat speler 1 (mogelijk) heeft.

Het valt me op dat de betere spelers al best snel weten dat in x beurten een unieke sudoko gegenereerd kan worden. De laatste 30/40 zetten is gewoon vullen van de hidden of naked singles en zijn voor beide spelers allang bekend (en voor de verliezer uitstellen van het onvermijdelijke)

Klopt, mijn speler probeert het aantal opties hoog te houden als 'ie verloren staat, in de hoop dat de tegenstander nog een fout maakt (of misschien uit de tijd loopt). Dat werkt vrij goed tegen minder sterke spelers, die dan vroeg of laat een verkeerde zet doen, maar tegen sterke spelers gebeurt dat natuurlijk niet.

[allemensen]

Ik heb ook iets beters in elkaar geklust: een depth-2 minimax met domweg veel sudoku's doorrekenen. Ook daar merk ik al een enorm voordeel voor de eerste speler.

We zullen wel zien hoe dat in de toekomst uitpakt, het zou mooi zijn als iemand een goede truc implementeert voor de tweede speler!

[Corniel]

Jammer dat ze geen C# ondersteunen. Anders had ik zeker een poging gewaagd.

Ben wel benieuwd hoe goed de besten gaan blijken te zijn.

[Soultaker]

Een bumpje: omdat de CodeCup organisatie ook erkende dat de eerste speler een groot voordeel had, waardoor de tweede speler praktisch niet kon winnen tegen een goede tegenstander, is er een extra regel toegevoegd: elke zet die je doet moet het aantal mogelijke oplossingen ook verkleinen. Praktisch betekent dat dat wanneer er in een vakje maar 1 cijfer mogelijk is, je daar niet meer mag zetten.

Dat lijkt het probleem goed op te lossen: in de test competitie van vanochtend winnen speler 1 en 2 ongeveer even vaak, dus lijkt het probleem daarmee opgelost.

[Soultaker]

De finale was vandaag. Ik ben op een gedeelde vierde plek geëindigd. Ik zag dat @allemensen op de elfde plek uitkwam (net 1 punt te weinig voor de top 10!). Hebben andere mensen nog meegedaan? (Ik kan Tweakers usernames niet zo eenvoudig correleren met namen op het Codecup scorebord.)

[veldsla]

De winnaar heeft zijn (Rust) code gepubliceerd met een beschrijving van het algoritme

Leuk om even door te bladeren!

[Soultaker]

veldsla schreef op maandag 22 januari 2024 @ 16:45:
De winnaar heeft zijn (Rust) code gepubliceerd met een beschrijving van het algoritme

Leuk om even door te bladeren!

Inderdaad leuk om te lezen. Zijn Sudoku-solver is wel serieus overengineered, aangezien Sudoku solving maar een klein onderdeel van de speler is (ter vergelijking: mijn relatief simpele backtracking solver is gemiddeld slechts 50% trager dan tdoku, gebaseerd op hetzelfde principe, en heeft worst case nooit meer dan 1 seconde nodig gehad, van de 30 seconde totaal). Toch is het interessant om te lezen, omdat zowel zijn algoritme (gebaseerd op DPLL SAT solving) als zijn implementatie (met vectorized instructies) behoorlijk geavanceerd is.

Meer informatie over hoe deelnemers het probleem aangepakt hebben is te vinden in deze CodeCup thread: How does your bot work?

Overigens lijkt het er op dat de nummer twee in de competitie eigenlijk beter was, maar door het beperkte aantal wedstrijden in de officiële competitie is de eindscore enigszins van het toeval afhankelijk.

[Janoz]

Soultaker schreef op maandag 22 januari 2024 @ 23:03:

Overigens lijkt het er op dat de nummer twee in de competitie eigenlijk beter was, maar door het beperkte aantal wedstrijden in de officiële competitie is de eindscore enigszins van het toeval afhankelijk.

Dat is dan eigenlijk wel weer jammer. Zeker als je bedenkt dat het houden van wedstrijden eigenlijk alleen door CPU power wordt beperkt.

Toen dit topic weer omhoog kwam begon het bij mij wel te jeuken om hier ook weer eens wat mee te doen. Heb alleen zo weinig tijd. Ik heb niet eens de advent of code afgemaakt dit jaar vanwege vakantie. Volgens mij de laatste daadwerkelijke versus game waar ik iets mee gedaan heb was een veld met mierenhopen.

Toch CodeCup maar eens wat beter in de gaten houden

[lucky81]

Soultaker schreef op maandag 22 januari 2024 @ 23:03:

Overigens lijkt het er op dat de nummer twee in de competitie eigenlijk beter was, maar door het beperkte aantal wedstrijden in de officiële competitie is de eindscore enigszins van het toeval afhankelijk.

(Winnaar hier)

Ik ben het ermee eens dat de resultaten erg willekeurig zijn, maar het is niet helemaal juist om te zeggen dat de tweede plaats absoluut beter was. Wat hij zei was dat hij nooit enkele prestatieproblemen op het concurrentieplatform kon debuggen die hij thuis niet zag, en na de wedstrijd uitvoerbare code (zonder broncode) plaatste die beter werkt op andere platforms. Het is niet duidelijk wie met meer games op het daadwerkelijke competitieplatform zou hebben gewonnen.

Hoe dan ook, mijn geluk is een essentieel onderdeel van mijn strategie