CodeCup 2011: DVONN

[Soultaker]

De 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 DVONN, een abstract bordspel uit de GIPF reeks.

Over het spel

DVONN is een spel voor twee spelers die elk een kleur (wit of zwart) spelen. Het wordt gespeeld op een bord met 49 velden en 49 stukken: 23 witte, 23 zwarte en 3 rode Dvonn stenen. Het spel wordt gespeeld in twee fasen. In de eerste fase zetten spelers om de beurt (wit begint) een steen op een leeg veld op het bord, waarbij eerst de drie Dvonn stenen geplaatst worden, en de spelers daarna verder gaan met de stenen van hun eigen kleur.

Na zes zetten (I3 K3 C3 J3 K4 J2) zou het bord er bijvoorbeeld zo uit kunnen zien: Merk op dat de eerste speler twee van de drie Dvonn stenen heeft geplaatst en de tweede speler daardoor een zwarte steen meer heeft geplaatst.
Dit gaat zo door tot alle stenen geplaatst zijn, bijvoorbeeld:

Nu begint de tweede fase van het spel, waarin wit weer als eerste zet. Elke beurt verplaatst een speler een stapel stenen (een enkele steen zien we gemakshalve ook als stapel) waarbij de volgende regels in acht genomen moeten worden:

• Een speler mag alleen met een stapel zetten als de bovenste steen zijn kleur heeft.
• Een stapel moet in een rechte lijn in één van de zes richtingen verplaatst worden, en wel precies zoveel stappen als de stapel hoog is. (Het is niet toegestaan een deel van een stapel te verplaatsen.)
• Met een stapel mag niet gezet worden als alle zes buurvelden met stenen bezet zijn (de kleur maakt daarbij niet uit; stapels aan de rand van het bord hebben minder dan zes buren en zijn dus altijd vrij).
• Een stapel moet na het zetten op een andere stapel eindigen (en dus niet op een leeg veld).

In het voorbeeld kan wit bijvoorbeeld I1J2 spelen. Daarna kan zwart E5D5 spelen, wat tot de volgende stelling leidt:

Tenslotte is er nog een cruciale regel: alle stenen op het bord moeten direct of indirect verbonden blijven met de rode Dvonn stenen. Dat betekent dat er vanaf elke stapel een pad moet zijn van aangrenzende, niet-lege velden naar een stapel die een Dvonn-steen bevat (die hoeft in die stapel niet bovenaan te liggen). Alle stapels die na een zet niet meer verbonden zijn met één van de drie Dvonn-stenen, worden van het bord verwijderd.

Als het spel bijvoorbeeld vervolgd wordt tot:
Dan kan zwart de stenen in het midden wegspelen door de verbindende steen op C2 weg te halen, bijvoorbeeld door C2B2 te spelen:
Het spel gaat door zolang spelers kunnen zetten. Passen is alleen toegestaan wanneer een speler geen enkele geldige zet meer heeft. Wanneer beide spelers moeten passen is het spel afgelopen. Een eindstelling is bijvoorbeeld:

Nu zet elke speler de stapels waarbij een steen van zijn kleur bovenop ligt op elkaar, en wie de hoogste stapel heeft (met andere woorden: wie de meeste stenen onder controle heeft) heeft gewonnen. In dit voorbeeld wint zwart dus met 15 tegen 7 punten!

De spelregels worden ook uitgelegd op de GIPF site en op de CodeCup website.

Wie kan er meedoen?

De competitie is open voor iedereen die een speler wil inzenden in één van de ondersteunde programmeertalen: Pascal, C, C++, Java, Python, Haskell en JavaScript. Je programma draait op de CodeCup server en heeft per spel 5 cpu-seconden en niet meer dan 64 MB werkgeheugen beschikbaar. Zie voor details de technische regels op de CodeCup site.

Hoe kan ik oefenen?

Als je wat spelervaring wil opdoen voordat je begint met programmeren, kun je op Little Golem het spel online spelen. (Let op: dit is niet realtime, dus een spel kan enkele dagen tot weken duren!) Verder zijn er enkele computerprogramma's om Dvonn tegen te spelen. Holtz is een grafische applicatie waarmee Dvonn gespeeld kan worden over het netwerk en tegen de AI. Dvonner biedt een moeilijkere (maar gelukkig configureerbare) tegenstander met een wat spartaanse text-based interface.

Als je je eigen Dvonn-speler hebt geschreven en die wil testen, dan kun je gebruik maken van de jurysoftware (Caia) die door de CodeCup-organisatie beschikbaar wordt gesteld. De Caia distributie bevat ook enkele programma's van verschillend niveau die als tegenstander dienen om mee te oefenen. Daarmee kun je een idee krijgen van de speelsterkte van je eigen programma.

Tenslotte wordt er vóór de finale competitie op 22 januari 2011 elke drie weken een testcompetitie georganiseerd. Door je programma daarvoor in te zenden kun je zien hoe je programma het doet tegen echte echte tegenstanders. De eerstvolgende testcompetitie is op zaterdag 9 oktober 2010.

Waarom een topic op GoT?

Het blijkt dat er op GoT altijd wel interesse is in programmeercompetities, gezien het succes van het Programmeervuur en de Programming Contest, maar helaas worden zulke contests slechts sporadisch georganiseerd. Vandaar dat het me leuk lijkt om een topic over de CodeCup te starten, om de aandacht op deze interessante competitie te vestigen, en om deelnemers een plek te geven om in het Nederlands te discussiëren over het spel en de wedstrijd.

Dus: wie doet er mee, of is van plan mee te doen aan deze competitie? Zoek je tegenstanders om het spel uit te proberen? Heb je vragen over de manier waarop je een programma kunt inzenden? Dan is dit het topic de plek waar je moet zijn!

_{Voor dit topic is toestemming verleend door NMe.}

[Matis]

Vet topic en een vet idee

* Matis gaat eens kijken of hij wat tijd kan vrijmaken om voor 9 oktober ( ) iets kan maken

[creator1988]

Vraag wel: waarom geen Mono?

[mkromkamp]

creator1988 schreef op woensdag 22 september 2010 @ 10:17:
Vraag wel: waarom geen Mono?

Waarom wel? Er worden, in mijn ogen, genoeg talen ondersteund op dit moment.
Ik ga in iedergeval een poging wagen om wat in elkaar te zetten.

[Vaan Banaan]

Hmm, ik denk dat ik hier ook wel aan mee ga doen. Eerst maar eens kijken of ik lokaal een werkende speler in elkaar kan zetten. Ik heb nog geen idee wat voor tactieken je hier op los moet laten. Nou ja, 2 weekenden voor de eerste testronde moet wel iets opleveren denk ik. En door de weeks kan ik eens een uurtje online gaan spelen. Het wordt in ieder geval iets in C
^{@Soultaker: die plaoties generator is visueel erg aantrekkelijk, mag ik die voor mijn lokale player log misbruiken?}

[Soultaker]

mkromkamp schreef op woensdag 22 september 2010 @ 13:52:
Waarom wel? Er worden, in mijn ogen, genoeg talen ondersteund op dit moment.

Ik vind het niet zo'n gekke vraag. Ik heb die ook wel eens gesteld.

C# is momenteel een stuk populairder dan bijvoorbeeld Pascal, Haskell of JavaScript; die laatste taal is vanwege de strenge tijdlimiet ook niet bijzonder geschikt voor de CodeCup naar mijn mening (zeker aangezien ze momenteel de nogal trage Spidermonkey interpreter gebruiken). Ik denk dat er veel mensen zijn die C# nu als eerste of tweede taal leren, dus lijkt me dat een goede taal om nieuwe deelnemers mee aan te trekken.

Vanuit praktisch oogpunt begrijp ik het wel. De CodeCup servers draaien Linux (wat Microsoft's .NET omgeving uitsluit) en bovendien bestaat de organisatie deels uit vrijwilligers, dus waarschijnlijk worden talen toegevoegd omdat een ontwikkelaar er toevallig zin in had. Als je heel graag in C# wil ontwikkelen, stuur vooral een mailtje naar de organisatie; als ze een paar verzoeken krijgen lijkt de kans me groot dat ze overstag gaan, of tenminste de optie serieus gaan bekijken.

Vaan Banaan schreef op woensdag 22 september 2010 @ 17:20:
Die plaoties generator is visueel erg aantrekkelijk, mag ik die voor mijn lokale player log misbruiken?

Sure, leef je uit. Moet ik de codering van het bord nog specificeren of heb je 'm inmiddels wel reverse engineered? (Overigens zijn er legale stellingen die niet uit te uit te drukken zijn in deze codering maar die zijn zo zeldzaam dat je ze in de praktijk niet tegenkomt.)

[.oisyn]

Matis schreef op woensdag 22 september 2010 @ 10:11:
* Matis gaat eens kijken of hij wat tijd kan vrijmaken om voor 9 oktober ( ) iets kan maken

Dan is de eerste testronde pas, he . De finale is pas in januari.
Als je dit begrepen had dan snap ik je smileys niet

---

Vraag: het staat niet in de regels, maar aan de voorbeeldplaatjes is te zien dat een stapel ook op een rode steen te zetten is, die vervolgens weer te verplaatsen is. Klopt dit? En een stapel met een rode steen erin is gewoon als iedere andere (met als uitzondering dat de overige stapels aan die (of de andere stapels met rode steen) verbonden moeten blijven)?

.edit: oh wacht:

Dat betekent dat er vanaf elke stapel een pad moet zijn van aangrenzende, niet-lege velden naar een stapel die een Dvonn-steen bevat (die hoeft in die stapel niet bovenaan te liggen)

[ Voor 46% gewijzigd door .oisyn op 22-09-2010 17:46 ]

[CMG]

.oisyn schreef op woensdag 22 september 2010 @ 17:40:
[...]

Dan is de eerste testronde pas, he . De finale is pas in januari.
Als je dit begrepen had dan snap ik je smileys niet

---

Vraag: het staat niet in de regels, maar aan de voorbeeldplaatjes is te zien dat een stapel ook op een rode steen te zetten is, die vervolgens weer te verplaatsen is. Klopt dit? En een stapel met een rode steen erin is gewoon als iedere andere (met als uitzondering dat de overige stapels aan die (of de andere stapels met rode steen) verbonden moeten blijven)?

.edit: oh wacht:

[...]

Ik had 'm wel verkeerd begrepen; had zo iets van: 2 weken? Daar ga ik niet aan beginnen Wellicht toch leuk om eens te gaan proberen; nog nooit zo iets gedaan.

De game lijkt me wel funny; wellicht eerst maar eens beginnen om hem speelbaar te schrijven in Silverlight; tegen de tijd dat ik daar mee klaar ben zal ik vast wel wat ideen opdoen.

[CMG]

Soultaker schreef op woensdag 22 september 2010 @ 17:39:
[...]
Ik vind het niet zo'n gekke vraag. Ik heb die ook wel eens gesteld.

C# is momenteel een stuk populairder dan bijvoorbeeld Pascal, Haskell of JavaScript; die laatste taal is vanwege de strenge tijdlimiet ook niet bijzonder geschikt voor de CodeCup naar mijn mening (zeker aangezien ze momenteel de nogal trage Spidermonkey interpreter gebruiken). Ik denk dat er veel mensen zijn die C# nu als eerste of tweede taal leren, dus lijkt me dat een goede taal om nieuwe deelnemers mee aan te trekken.

Vanuit praktisch oogpunt begrijp ik het wel. De CodeCup servers draaien Linux (wat Microsoft's .NET omgeving uitsluit) en bovendien bestaat de organisatie deels uit vrijwilligers, dus waarschijnlijk worden talen toegevoegd omdat een ontwikkelaar er toevallig zin in had. Als je heel graag in C# wil ontwikkelen, stuur vooral een mailtje naar de organisatie; als ze een paar verzoeken krijgen lijkt de kans me groot dat ze overstag gaan, of tenminste de optie serieus gaan bekijken.
[...]

Ik moet zeggen dat ik het daarom wel aardig vind hoe de programmeervuur's hier op GoT gedaan worden; maakt het in welke taal je ook maar wilt, maar maak 'm speelbaar via http get/post commands.

[Soultaker]

.oisyn schreef op woensdag 22 september 2010 @ 17:40:
Vraag: het staat niet in de regels, maar aan de voorbeeldplaatjes is te zien dat een stapel ook op een rode steen te zetten is, die vervolgens weer te verplaatsen is. Klopt dit? En een stapel met een rode steen erin is gewoon als iedere andere (met als uitzondering dat de overige stapels aan die (of de andere stapels met rode steen) verbonden moeten blijven)?

Dit klopt precies. Rode stenen mogen gewoon meeverplaatst worden, maar je zal er eerst een eigen stapel op moeten zetten, omdat je niet mag zetten met stenen/stapels waarbij jouw kleur niet bovenop ligt.

[Dido]

Ik zie niet waarom de eindstelling in de TS een eindstelling is? Zowel zwart als wit kunnen toch nog legaal een zet doen aan de rechterkant van het bord? J2-I4 voor wit of I4-J2 voor wit (via K2). Wat zie ik niet?

[Gimmeabrake]

Heel tof dat dit gepost wordt, heb 2 jaar geleden aan de informatica olympiade deelgenomen in mijn laatste jaar op de middelbare school. De codecup is met afstand (het leukste) onderdeel van ronde 1 Als ik tijd heb doe ik zeker mee! Het is ook verbazingwekkend wat sommige middelbare scholieren voor elkaar krijgen, daar zitten echt een paar hele slimme jongens bij!

creator1988 schreef op woensdag 22 september 2010 @ 10:17:
Vraag wel: waarom geen Mono?

Ik heb zelf ook altijd .Net gebruikt en vond het vreselijk toen ik op mijn opleiding moest beginnen met Java, maar ik moet zeggen dat het echt heel makkelijk is. Vooral bij dit soort programmas, waar je geen GUI voor nodig hebt, is het verschil tussen C# en Java héél erg klein, het framework biedt je (voor dit soort doeleinden) ongeveer dezelfde mogelijkheden, het heet alleen allemaal net iets anders dan bij .Net. Gewoon Java leren dus, een extra taal beheersen kan nooit kwaad!

[ Voor 46% gewijzigd door Gimmeabrake op 22-09-2010 19:18 ]

[Soultaker]

gerrymeistah schreef op woensdag 22 september 2010 @ 19:11:
Het is ook verbazingwekkend wat sommige middelbare scholieren voor elkaar krijgen, daar zitten echt een paar hele slimme jongens bij!

Absoluut!

Dido schreef op woensdag 22 september 2010 @ 18:57:
Ik zie niet waarom de eindstelling in de TS een eindstelling is? Zowel zwart als wit kunnen toch nog legaal een zet doen aan de rechterkant van het bord? J2-I4 voor wit of I4-J2 voor wit (via K2). Wat zie ik niet?

Om mezelf te quoten:

• Een stapel moet in een rechte lijn in één van de zes richtingen verplaatst worden, en wel precies zoveel stappen als de stapel hoog is. (Het is niet toegestaan een deel van een stapel te verplaatsen.)

Een zet moet in een rechte lijn plaatsvinden langs één van de assen van het hexagonale grid. De stapel op I4 zou dus naar I1, F1 of F4 kunnen, maar dat zijn lege velden. Op dezelfde manier kan de stapel op J2 alleen naar F2 (vier stappen in een andere richting en je valt van het bord) maar ook dat veld is leeg. (Het vakje K2 bestaat überhaupt niet; misschien lees je het bord verkeerd?)

Is dit zo duidelijk? Of hoe zou ik dit beter kunnen verwoorden?

[ Voor 15% gewijzigd door Soultaker op 22-09-2010 19:32 ]

[Vaan Banaan]

Dido schreef op woensdag 22 september 2010 @ 18:57:
Ik zie niet waarom de eindstelling in de TS een eindstelling is? Zowel zwart als wit kunnen toch nog legaal een zet doen aan de rechterkant van het bord? J2-I4 voor wit of I4-J2 voor wit (via K2). Wat zie ik niet?

Nee, je mag niet 'bogglen' maar het moet een lijn zijn en dat kan niet 4 schuin naar beneden. K2 bestaat trouwens niet.

En 4 naar links is een leeg veld

Wat zwart betreft: Dit mag dus niet:

Je mag alleen in 1 richting over de lijntjes lopen.
^{-edit- Ja lekker Soultaker, voor spuit 11 had ik vroeger ook al een goed cijfer op mijn rapport}
Stel dat er op I1 een schijf lag (en zwart is aan de beurt), dan zou zwart nog wel een zet kunnen doen.

[ Voor 22% gewijzigd door Vaan Banaan op 23-09-2010 00:54 ]

[Dido]

Ok, het was me niet duidelijk dat de hele move in dezelfde richting moest plaatsvinden Duidelijk nu (en K2 moest K3 zijn )

[Tharulerz]

Foutje in OP: Link achter het woord CodeCup is fout.

Ontopic: Ik doe men best om mee te doen, alhoewel ik ook geen fan ben de programmeertalen die ondersteund worden! (hoogstwaarschijnlijk wordt het dan maar python)

[ReenL]

Vraagje, ben je verplicht om in fase 1 ook om de rooie heen te bouwen? Of mag je de witte/zwarte gewoon overal plaatsen?

Nu even bedenken hoe ik kan zien of een zwarte/witte "connected" is met een rode, sowieso nodig voor fase 2

[Soultaker]

Tharulerz schreef op donderdag 23 september 2010 @ 14:23:
Foutje in OP: Link achter het woord CodeCup is fout.

Bedankt, is nu gefixt!

ReenL schreef op donderdag 23 september 2010 @ 18:49:
Vraagje, ben je verplicht om in fase 1 ook om de rooie heen te bouwen? Of mag je de witte/zwarte gewoon overal plaatsen?

Je mag stenen plaatsen waar je maar wil; enige criterium is dat je je steen op een leeg veld neerzet. Je stenen hoeven in die fase dus niet verbonden te zijn met de Dvonn stenen.

[Devilly]

Dit klinkt toch wel heel erg leuk. Ik ga sowieso proberen een simpele implementatie te maken al is het maar voor de lol van het deelnemen. De komende dagen zal ik ook eens nadenken over een mogelijke strategie, want ik kom zo een, twee, drie niet op een briljant idee.

[__fred__]

Vooruit, ook maar eens begonnen in wat spare time. Heb besloten om eerst wat .NET versies te schrijven om snel geautomatiseerd verschillende tactieken te kunnen proberen, voordat ik me waag aan een snelle c++ versie onder linux, die ook nog eens via stdin, stderr en stdout moet gaan communiceren.

Wat heb ik al:

• Eigen manager / referee.
• Gui om een beetje te kunnen zien wat er gebeurt.
• Randomplayer die random (toegestane) zetten doet.

Nu maar minimax gaan implementeren en dan een paar goede evaluatiefuncties schrijven.

[.oisyn]

Je nummering klopt niet. Er bestaat geen A4 en A5 - dat zijn resp. B4 en C5.

[__fred__]

.oisyn schreef op dinsdag 28 september 2010 @ 14:11:
Je nummering klopt niet. Er bestaat geen A4 en A5 - dat zijn resp. B4 en C5.

Thanks. Inderdaad. Gelukkig is het een format functie. Intern is het gewoon een array.

[__fred__]

Minimax zit er in. Nog geen pruning, dus helaas komt ie niet verder dan een boomdiepte van 4 nodes, maar dit is toch al genoeg om in het eindspel altijd van de randomplayer te winnen. Morgen maar eens kijken of ik kan gaan prunen en de berekende scores en boards kan bewaren in de boom.

[ThomasClay]

Twee vraagjes over de regels waar ik niet echt duidelijkheid over kan krijgen:

1. Mogen er meerdere Dvonn stenen in een stapel belanden? Kun je bijvoorbeeld een stapel maken waar alle 3 de Dvonn stenen in zitten?
2. Tellen Dvonn stenen in een stapel mee voor de score?

Heb het vermoeden dat het antwoord op beiden vragen 'ja' is, maar wil het graag even checken.

[Soultaker]

Je vermoeden is juist.

[__fred__]

Hebben meer mensen het idee dat een transposition table niets gaat helpen? Omdat de stacks alleen maar groter kunnen worden zal een zelfde bordpositie nooit voorkomen. Of zit ik mis?

[Soultaker]

Zeker wel. Sterker nog, ik heb er al profijt van in mijn speler. Waarom denk je van niet?

Een transpositie is een positie die gelijk is aan een andere/eerdere positie, maar via een alternatieve serie van zetten bereikt is.

Om het voorbeeld uit de TS er nog eens bij te pakken:

De zetten G5F4, G1F1, A3A2 en E5F5 leiden tot de volgende stelling:

Maar de zetten A3A2, E5F5, G5F4 en G1F1 óók. Er zijn zelfs vier verschillende series van zetten die tot deze zelfde positie leiden.

Bij een minimaxalgoritme zonder transpositietabel zou deze positie opnieuw geëvalueerd worden voor elke reeks zetten waarmee hij te bereiken is. Met een transpositietabel kun je herkennen dat deze positie gelijk is aan een eerdere positie, en de eerder berekende waarde hergebruiken.

[Devilly]

Jullie praten hier over technieken waar ik nog nooit van gehoord heb. Ik ben benieuwd hoever ik kom zonder al die kennis.

[Vaan Banaan]

Met minimax maak je een boom waarbij je alle zetten een waarde geeft en daardoor de beste zet kan bepalen. Je rekent alle mogelijkheden met 1 zet. De eerste zet kan bijvoorbeeld met 15 stenen gespeeld worden in een aantal richtingen waardoor er bijvoorbeeld 40 mogeljikheden zijn. Dan kun je met die uitkomsten weer alle combinaties uitrekenen en dus 2 zetten vooruit 'denken'. Maar dat worden dan iets van 1200 combinaties, dus duurt een stuk langer. Uiteindelijk bepaalt de tijd hoe ver je dat kan doorrekenen. Daarom ga je prunen.
Met prunen wordt snoeien bedoeld. Net zoals je in de tuin een boom snoeit, probeer je dat hier ook: je gaat de boom snoeien, waarbij je de slechtste zetten wegmikt. Daardoor hou je minder combinaties over die je met een volgende zet hoeft door te rekenen.
Met transpositie kijk je of je een bepaalde stelling al niet eerder hebt gezien, zie uitleg van Soultaker. Als je via verschillende zetten op dezelfde stelling uitkomt, hoef je er met een aantal niet verder te rekenen.
Hoe meer stellingen je kan evalueren (meer zetten vooruit denken), des te zekerder ben je van een goede zet.

De kunst is nu: wat is een goede zet. Zo veel mogelijk eigen stenen om een dvonn steen? Het aantal lage stapels, het aantal hoge stapels, het aantal stenen van jezelf en de tegenstander enzovoort.
Dan maakt je tactiek en geeft een bepaalde zet een waarde en die frot je vervolgens in je transpositioned pruned minimax tree

[Soultaker]

Devilly schreef op vrijdag 01 oktober 2010 @ 16:27:
Jullie praten hier over technieken waar ik nog nooit van gehoord heb. Ik ben benieuwd hoever ik kom zonder al die kennis.

Dat is een groot deel van de lol ervan: dat je allerlei nieuwe technieken ontdekt die je kunt gebruiken om je programma te verbeteren.

Maar laat je niet gekmaken door discussies over geavanceerde algoritmes. Begin gewoon bij het begin, met een programma dat een speelveld kan representeren en geldige zetten kan doen. Als je een programma hebt dat een potje kan uitspelen zonder te crashen heb je een goed begin.

[Devilly]

@ Vaan Banaan: dat noem ik nou een informatieve reactie, bedankt! Mijn interesse is meteen gewekt.

@ Soultaker: ik weet het, maar het lot wil dat ik sinds kort 40 uur per week programmeer op mijn stage en daardoor is de motivatie om er daarbuiten veel tijd in te steken een beetje weg. Desondanks wil ik sowieso wel een werkende implementatie in elkaar zetten. Daar zal ik dus eerst maar eens aan gaan werken en daarna kijk ik wel in hoeverre ik er nog meer tijd in zal steken.

[__fred__]

Soultaker schreef op vrijdag 01 oktober 2010 @ 15:56:
Zeker wel. Sterker nog, ik heb er al profijt van in mijn speler. Waarom denk je van niet?

Een transpositie is een positie die gelijk is aan een andere/eerdere positie, maar via een alternatieve serie van zetten bereikt is.

Om het voorbeeld uit de TS er nog eens bij te pakken:
[afbeelding]
De zetten G5F4, G1F1, A3A2 en E5F5 leiden tot de volgende stelling:
[afbeelding]
Maar de zetten A3A2, E5F5, G5F4 en G1F1 óók. Er zijn zelfs vier verschillende series van zetten die tot deze zelfde positie leiden.

Bij een minimaxalgoritme zonder transpositietabel zou deze positie opnieuw geëvalueerd worden voor elke reeks zetten waarmee hij te bereiken is. Met een transpositietabel kun je herkennen dat deze positie gelijk is aan een eerdere positie, en de eerder berekende waarde hergebruiken.

Goh, zat ik ff te slapen, je hebt gelijk natuurlijk. Ik had dit zelf ook kunnen berederneren. Laat ik het eerst maar eens testen, dat heb ik met alpha-beta cut-offs ook gedaan. Nu ligt mijn focus eerst even op het implementeren van nega-scout na minimax met pruning.

[Soultaker]

Even een bumpje: de volgende testcompetitie begint morgen om 12 uur 's middags. Als je je programma wil testen, zorg dan dat je 'm vóór die tijd ingestuurd en geverifieerd hebt op de CodeCup website!

[Devilly]

Ik heb helaas niets meer gedaan aan mijn speler sinds vorige week. Misschien dat ik dit weekend wat tijd daarvoor inplan. Gelukkig zijn dit nog maar de testcompetities.

[Vaan Banaan]

Zo Soultaker, gefeliciteerd! 2 uit 2 testronden gewonnen!
Weet je ook de reden van de 5 crashes? hier ben je bijvoorbeeld lekker op dreef als het spel stopt.
Helaas ben ik nog niet eens begonnen en de komende 2 maanden zal ik veel tijd met het verbouwen van mijn huis kwijt zijn. Maar er zijn nog 4 testronden, dus ik zal hopelijk aan het eind van het jaar nog wel een testspeler kunnen inleveren. Goed voor kanonnen vlees.

[Soultaker]

Dank je, goed begin inderdaad. Vorige ronde eindigde Marcel Vlastuin's onofficiële inzending nog boven me qua punten maar die versloeg ik nu ook. Ik heb welgeteld één potje regulier verloren met een verschil van slechts één schijf.

De rest van de verliespartijen waren crashes. De omstandigheden lijken op een bug gerelateerd aan hoe ik het zoeken afkap als het te lang dreigt te duren (waar ik vlak voor de competitie ook al een bug in gefixt had) maar ik heb ze helaas nog niet lokaal kunnen reproduceren. Ik denk dat ik de verdere ontwikkeling even moet stopzetten tot ik dit opgelost heb.

In het potje dat je aanhaalt was mijn tegenstander trouwens al eerder gecrasht. In zo'n geval neemt de scheidsrechter het voor hem over door willekeurige zetten te doen. Dat is wel makkelijk scoren natuurlijk. Neemt niet weg dat ik daar dik gewonnen stond (net als in de andere partijen die crashten, voor zover ik kon zien) dus dat is toch jammer van de 90 punten.

edit:
Vijf van de zes crashes heb ik inmiddels naar dezelfde oorzaak herleid en opgelost. Dat zijn cases waarin een assertion triggerde (toch handig om die aan te laten staan in de officiële competitie!) en de zesde was een crash zonder verdere mededeling, dus die begrijp ik niet echt.

[ Voor 12% gewijzigd door Soultaker op 10-10-2010 21:54 ]

[Soultaker]

Bump! Morgen is de finale. Doen er nog andere Tweakers mee?

Zal ik volgend jaar 't topic maar achterwege laten? Er lijkt nogal weinig animo voor te zijn...

[Hydra]

Ik snap het niet helemaal geloof ik, is er nu weer een wedstrijd met hetzelfde spel als een jaar geleden?

[Soultaker]

Nee, morgen is de finale van de wedstrijd waarvoor je vier maanden de tijd had om een inzending te doen.

(Tenzij je doelt op de CodeCup 2010 waarvan de finale in Januari 2010 was, maar toen draaide 't om een heel ander spelletje.)

[Hydra]

Achso. Nou, als er een nieuwe wedstrijd komt (en eentje met een onderwerp dat me meer aanspreekt) vind ik dat zeker interessant. Dus open gerust een nieuwe

[Verwijderd]

Soultaker, zou je ergens (hier, codecup forum, blog, whatever) kunnen beschrijven hoe je een onverslaanbare Dvonn speler gemaakt hebt??

[Devilly]

Ik was aan een speler begonnen, maar kon me er niet toe zetten om hem af te maken. Daarentegen zou ook ik het boeiend vinden om iets te lezen over de manier waarop jouw programma in elkaar steekt.

[Soultaker]

Dat ging beter dan verwacht!

Natuurlijk heb ik wel op het laatste moment wat verbeteringen doorgevoerd, maar dat had ik ook van mijn tegenstanders verwacht, en hoe dichter je bij een optimale speler komt, des te moeilijker wordt het om consequent winst af te dwingen. Maar met uitsluitend gewonnen partijen spreekt het vanzelf dat ik uiterst tevreden ben met deze uitslag.

Verwijderd schreef op zaterdag 22 januari 2011 @ 14:15:
Soultaker, zou je ergens (hier, codecup forum, blog, whatever) kunnen beschrijven hoe je een onverslaanbare Dvonn speler gemaakt hebt??

Dat ben ik zeker van plan. Ik had het zelf ook altijd leuk gevonden om te lezen hoe winnende spelers tot stand zijn gekomen, en ik heb in het verleden (tevergeefs) winnaars wel eens om uitleg/code gevraagd, dus nu kan ik zelf niet in gebreke blijven.

Om te beginnen heb ik de code van mijn speler online gezet: via Gitweb of te clonen via git://hell.student.utwente.nl/PrimaDvonna.

Omdat de code op zichzelf misschien lastig te doorgronden is, ben ik van plan om er wat uitleg bij te schrijven, maar door chronisch gebrek aan tijd kan ik niet direct beloven wanneer dit gebeurt.

[Gimmeabrake]

Ah, een tweakert heeft gewonnen! Heel veel respect van mij! Ik wilde eigenlijk ook gaan meedoen met een Monte Carlo algoritme, maar heb de tijd niet kunnen vinden helaas, omdat ik de laatste maanden voor mijn studie al met een bordspel bezig was, en daar heel veel tijd in ging zitten. Volgend jaar probeer ik wel van de partij te zijn! Vanavond maar eens naar je code kijken, ik ben benieuwd hoe je AI is opgebouwd.

[ Voor 4% gewijzigd door Gimmeabrake op 22-01-2011 18:22 ]

[.oisyn]

Nice, gefeliciteerd!