AI schrijven voor Yahtzee-spelletje

[jelmervos]

Ik probeer een computerspeler te maken die Yahtzee speelt (in C#). Opzich hoeft dit geen AI te zijn, dat is te complex. Maar hij moet wel goed spelen. Wat is nou een goede manier om de juiste keuzes te maken.

Zelf dacht ik om per worp te kijken wat de meeste kans geeft op een goede score. Dus bij elke worp de lege scores bij langs te gaan en per score het slagingspercentage te berekenen. Maar voor ik dit implementeer was ik benieuwd of er nog andere (betere?) methoden?

Alvast bedankt.

[NMe]

Veel eenvoudiger dan simpelweg een aantal punten toekennen aan elke mogelijk score voor een worp, en na het gooien daar het hoogste puntenaantal uit zoeken zal het niet worden.

Als je het zaakje trouwens netjes met een strategy pattern implementeert kun je er ook makkelijk een andere AI aan hangen als je later nieuwe ideeën hebt.

Verder hoort dit eerder in Software Engineering & Architecture, zie Waar hoort mijn topic?

PRG>>SEA

[jelmervos]

Bedankt voor het antwoord. Ik denk dat ik die methode ook ga kiezen.

Toch heb ik nog een vraag over de implementatie hier over. Ik probeer een methode te maken die de kans berekend dat een bepaalde worp wordt gegooit. Hier heb ik als input de huidige worp en een soort masker.

Voorbeeld, invoer:
worp = {3,5,3,2,2}
mask = {2,2,2} (=minimaal 3 tweeen, rest maakt niet uit)
uitvoer zou nu de kans moeten zijn dat ik minimaal 3 tweeen gooi met de worp. Natuurlijk moet de mask dynamisch zijn, dus de kans op full-house ({2,2,2,3,3}) wil ik ook kunnen berekenen.

Ik ben niet zo goed in kansberekening, dus zou iemand mij hier mee kunnen helpen?

[Boss]

De kans dat je met 1 dobbelsteen 3 gooit: 1/6
De kans dat je met 2 dobbelstenen 3 3 gooit: 1/6 * 1/6 = 1/36
De kans dat je met 3 dobbelstenen 3 3 3 gooit: 1/6 * 1/6 * 1/6 = 1/(216)

[jelmervos]

Dat helpt al een beetje, maar hoe zit het met de kans dat ik met 5 dobbelstenen 4 4 4 4 gooi (5e steen maakt niet uit). Hoe bereken je dat?

[ Voor 3% gewijzigd door jelmervos op 02-08-2006 10:56 ]

[BCC]

Een min max boom zou ook nog wel kunnen. Maar dan moet je wel oppassen dat het niet uit de hand loopt

Zoiets: http://www.math.tau.ac.il.../shachar/explanation.html

[ Voor 210% gewijzigd door BCC op 02-08-2006 11:09 ]

[mithras]

Kaassoevlee schreef op woensdag 02 augustus 2006 @ 10:56:
Dat helpt al een beetje, maar hoe zit het met de kans dat ik met 5 dobbelstenen 4 4 4 4 gooi (5e steen maakt niet uit). Hoe bereken je dat?

Eerste steen: 1/6
Tweede steen: 1/6
Derde steen: 1/6
Vierde steen: 1/6
Vijfde steen: 6/6
Mogelijke combinaties: (5 6) * 1/6 * 1/6 * 1/6 * 1/6 * 6/6

[4VAlien]

Kaassoevlee schreef op woensdag 02 augustus 2006 @ 10:56:
Dat helpt al een beetje, maar hoe zit het met de kans dat ik met 5 dobbelstenen 4 4 4 4 gooi (5e steen maakt niet uit). Hoe bereken je dat?

binomiaal: 5 boven 4 = 5! / 4!1! mogelijke volgordes = 5
kans: (1/6)^4 (vieren) * 1 (laatste steen)

dus 5 * (1/6)^4 in dit geval. Maar heb je niet gewoon kansrekening op school ofzo? Dat met die bionomiaal is niet super triviaal. Ik zou zeggen, boeken erbij.

[frickY]

Je hebt 5x 6 waardes; 30
Je bent maar geinterresseerd in 4 waardes; 30 / 4 = 7.5
Kans op vier maal 4 met 5 dobbelstenen; 1/7.5 * 1/7.5 * 1/7.5 * 1/7.5 = 1/3164... meen ik.

[ Voor 90% gewijzigd door frickY op 02-08-2006 11:16 ]

[BCC]

Dit is ook ZEER interessant leesvoer : http://svsoc1.win.tue.nl/...tzee/Yahtzee-talk-NWD.pdf

En een werkende demo van een kansberekenaar staat er ook:
http://svsoc1.win.tue.nl/~wstomv/misc/yahtzee/osyp.php3

[ Voor 36% gewijzigd door BCC op 02-08-2006 11:18 ]

[Verwijderd]

frickY schreef op woensdag 02 augustus 2006 @ 11:13:
Je hebt 5x 6 waardes; 30
Je bent maar geinterresseerd in 4 waardes; 30 / 4 = 7.5
Kans op vier maal 4 met 5 dobbelstenen; 1/7.5 * 1/7.5 * 1/7.5 * 1/7.5 = 1/3164... meen ik.

@4VAlien
Waarom vermenigvuldigen met 4? De kans op vier 4-en is toch net zo groot als op vier 1-en, als op vier 6-en, of op elke andere vooraf bepaalde combinatie van cijfers?

Jij gaat wel heel creatief om met kansrekenen.

[4VAlien]

frickY schreef op woensdag 02 augustus 2006 @ 11:13:
Je hebt 5x 6 waardes; 30
Je bent maar geinterresseerd in 4 waardes; 30 / 4 = 7.5
Kans op vier maal 4 met 5 dobbelstenen; 1/7.5 * 1/7.5 * 1/7.5 * 1/7.5 = 1/3164... meen ik.

stop posting

[Boss]

4VAlien schreef op woensdag 02 augustus 2006 @ 12:16:
[...]


stop posting

[Grijze Vos]

BCC schreef op woensdag 02 augustus 2006 @ 11:15:
Dit is ook ZEER interessant leesvoer : http://svsoc1.win.tue.nl/...tzee/Yahtzee-talk-NWD.pdf

En een werkende demo van een kansberekenaar staat er ook:
http://svsoc1.win.tue.nl/~wstomv/misc/yahtzee/osyp.php3

Waarom ben ik niet verbaasd dat het juist T. Verhoeff is die zich hiermee bezig heeft gehouden.

[jelmervos]

4VAlien schreef op woensdag 02 augustus 2006 @ 11:13:
[...]


binomiaal: 5 boven 4 = 5! / 4!1! mogelijke volgordes = 5
kans: (1/6)^4 (vieren) * 1 (laatste steen)

dus 5 * (1/6)^4 in dit geval. Maar heb je niet gewoon kansrekening op school ofzo? Dat met die bionomiaal is niet super triviaal. Ik zou zeggen, boeken erbij.

Ik ben net afgestudeerd voor de HIO, maar heb volgens mij nooit echt kansberekening gehad, of ik was er die dag niet.

Na het doorlezen van wikipedia heb ik de volgende implementatie gemaakt:

code:

double binomial = (Factorial(n) / (Factorial(k) * Factorial(n - k)));
double change = binomial * Math.Pow(p, k) * Math.Pow(1 - p, n - k);

Name van de variabelen heb ik gelijk gehouden aan wikipedia.

Ik neem dat het niet uitmaakt of je nou met 4 dobbelstenen 2x6 wil of 4 en 3 bijvoorbeeld. Beide keren k=2.

Bedankt voor de hulp.

[.oisyn]

Maakt wel uit. Je kunt namelijk op meerdere verschillende manieren een 4 en een 3 gooien (als je 2x gooit: eerst 4 dan 3, of eerst 3 dan 4).

Het gaat dan ook niet op de manier waarop je het nu doet. Eerst stelde je dat een keer een 6 gooien een succes is, en de kans daarop is natuurlijk 1/6. Met die formule bereken je simpelweg de kans op k successen met n keer gooien.

Maar als je met 4x gooien een 3 én een 4 wilt gooien, is er niet met een enkele worp al een succes of een mislukking.

[ Voor 82% gewijzigd door .oisyn op 02-08-2006 17:55 ]

[jelmervos]

Heb nu (inclusief strategy pattern) een simpele computer speler geimplementeerd, alles met kans berekening zoals hierboven beschreven.

Echter, nu wil ik proberen nog een computer speler te maken, welke meer AI is. Heb hier zelf weinig ervaring mee, maar zou een minimax algoritme kunnen werken, ondanks dat het hier niet om een 2 player spel gaat zoals schaak bijvoorbeeld?

[BCC]

Kaassoevlee schreef op zondag 06 augustus 2006 @ 14:21:
minimax algoritme

Minmax is hier niet handig, want:

- Je gaat steeds uit van een andere situatie (al opgeschreven aantallen).
- Min max is handig voor bomen, jouw boom gaat maar 2 of 3 diep zijn.

Je kan natuurlijk je complete spel als een boom zien, maar dan explodeert je boom. Heb je al naar neurale netwerken gekeken?

[ Voor 4% gewijzigd door BCC op 07-08-2006 11:48 ]

[jelmervos]

Neurale netwerken heb ik al eens naar gekeken, best complex. Zou dat makkelijk te gebruiken zijn voor dit probleem?

[Mithrandir]

Nee.

Neurale netwerken zijn zelden goed te gebruiken. Nu is het redelijk simpel te berekenen wat je zou moeten doen en is het dus totaal geen interessante oplossing.

Het maken van een neuraal netwerk is niet zo vreselijk moeilijk, het afstellen en tweaken kost je enorm veel tijd.

[ Voor 17% gewijzigd door Mithrandir op 07-08-2006 17:14 ]

[BCC]

Mithrandir schreef op maandag 07 augustus 2006 @ 17:13:
Nee.
Neurale netwerken zijn zelden goed te gebruiken. Nu is het redelijk simpel te berekenen wat je zou moeten doen en is het dus totaal geen interessante oplossing.
Het maken van een neuraal netwerk is niet zo vreselijk moeilijk, het afstellen en tweaken kost je enorm veel tijd.

Dit is wel heel kort door de bocht.

Een neuraal netwerk is misschien best leuk hierzo. Je kan bijvoorbeeld aan de hand van de state van je spel een bepaald neuraal netwerk gebruiken. Aan dit netwerk kun je dan bijvoorbeeld je huidige dobbelsteen worpen voeren en hem laten bepalen wat je moet doen.

Het afstellen en tweaken doe je natuurlijk door dat ook zelflerend te maken (bijvoorbeeld door middel van een genetisch algoritme.

Ik heb ooit een catan spel gemaakt waarbij de onder andere voor het voorspellen van de opbrengst van een huisje op een bepaalde plek een neuraal netwerk werd gebruikt. Dit werkte erg goed.

Het moeilijkste is om je Yathzee spel terug te brengen tot een beperkt aantal states.

[ Voor 14% gewijzigd door BCC op 07-08-2006 17:32 ]

[Mithrandir]

BCC schreef op maandag 07 augustus 2006 @ 17:30:
[...]

Dit is wel heel kort door de bocht.

Een neuraal netwerk is misschien best leuk hierzo. Je kan bijvoorbeeld aan de hand van de state van je spel een bepaald neuraal netwerk gebruiken. Aan dit netwerk kun je dan bijvoorbeeld je huidige dobbelsteen worpen voeren en hem laten bepalen wat je moet doen.

Het afstellen en tweaken doe je natuurlijk door dat ook zelflerend te maken (bijvoorbeeld door middel van een genetisch algoritme.

Ik heb ooit een catan spel gemaakt waarbij de onder andere voor het voorspellen van de opbrengst van een huisje op een bepaalde plek een neuraal netwerk werd gebruikt. Dit werkte erg goed.

Het moeilijkste is om je Yathzee spel terug te brengen tot een beperkt aantal states.

Ik denk dat jij juist een beetje te kort door de bocht gaat, BCC.

Denk er eens aan hoeveel verschillende states dit spel heeft. Je hebt zowel de dobbelstenen, het aantal beurten dat je nog mag gooien, de vakjes die je al ingevuld hebt... Dat zijn veel states. Daarbij kan een subtiel verschil in de states een redelijk groot verschil op het eind uitmaken, waardoor het lastig wordt om het neurale netwerk zo te trainen dat het geen vreemde keuzes maakt in ietwat gekke situaties.

Het voorspellen van opbrengst van een huisje bij Catan heeft lang niet zoveel parameters, en is dus beter te gebruiken, maar in veel gevallen is een rekenmethode makkelijker, beter debugbaar en betrouwbaarder dan een neuraal netwerk.

[BCC]

Mithrandir schreef op maandag 07 augustus 2006 @ 18:24:
[...]
Ik denk dat jij juist een beetje te kort door de bocht gaat, BCC.

Denk er eens aan hoeveel verschillende states dit spel heeft. Je hebt zowel de dobbelstenen, het aantal beurten dat je nog mag gooien, de vakjes die je al ingevuld hebt... Dat zijn veel states. Daarbij kan een subtiel verschil in de states een redelijk groot verschil op het eind uitmaken, waardoor het lastig wordt om het neurale netwerk zo te trainen dat het geen vreemde keuzes maakt in ietwat gekke situaties.

Nou, zoals ik al zei: Je moet op een slimme manier het aantal states drastisch verminderen, zodat je of maar een paar netwerken overhoudt of je versimpelde geschiedenis meeneemt als input voor je neuraal netwerk. Dat wordt inderdaad lastig, maar daarom niet minder interessant. Aangezien de TS meerdere vormen van AI wil gebruiken (schoolopdracht), lijkt het me een poging waard.

Je zou bijvoorbeeld heel simpel voor elke score categorie een netwerkje kunnen bouwen dat probeert te voorspellen wat de kans (gegeven de huidige dobbelstenen) gaat worden op veel punten in die categorie. Streep dan de dingen weg die je al gehaald heb en ga voor de hoogste. Kijk op het laatst wat je scoort -> feedbacken en hupsa. Hardstikke interessant Dan krijg je meestal ook een speler die wat "menselijker" speelt dan een speler die op keiharde logica functioneert.

[ Voor 22% gewijzigd door BCC op 07-08-2006 22:58 ]

[Mithrandir]

BCC schreef op maandag 07 augustus 2006 @ 22:52:
[...]


Nou, zoals ik al zei: Je moet op een slimme manier het aantal states drastisch verminderen, of je geschiedenis meenemen als input voor je neuraal netwerk. Dat wordt inderdaad lastig, maar daarom niet minder interessant. Aangezien de TS meerdere vormen van AI wil gebruiken (schoolopdracht), lijkt het me een poging waard.

'de geschiedenis meenemen als input'? Ik weet niet wat je daarmee precies bedoelt.

Juist het feit dat het lastig wordt om een neuraal netwerk te implementeren is wat ik probeer te onderstrepen. Als er véél slimmere methodes zijn, waarom zou je dan ervoor kiezen om een nn te bouwen?

[BCC]

Mithrandir schreef op maandag 07 augustus 2006 @ 22:58:
'de geschiedenis meenemen als input'? Ik weet niet wat je daarmee precies bedoelt.

En handige manier vinden om de score categorieën die je al ingevuld hebt te coderen en dit in je neurale netwerk stoppen als input.

Juist het feit dat het lastig wordt om een neuraal netwerk te implementeren is wat ik probeer te onderstrepen. Als er véél slimmere methodes zijn, waarom zou je dan ervoor kiezen om een nn te bouwen?

Nou, dat lijkt me wel duidelijk. Je kan nog zoveel kansrekening erop los laten, maar dat betekent niet automatisch dat je altijd wint. Geluk is nogal een groot onderdeel van Yathzee. En misschien zijn er wel hele rare goedwerkende strategiën waar je nog nooit aan gedacht hebt? Met een neuraal netwerk kun je dat soort dingen boven water krijgen. Daarnaast is het gewoon hardstikke leuk om zo'n ding te zien leren.
Daarnaast, letterlijk van de TS:

Heb nu (inclusief strategy pattern) een simpele computer speler geimplementeerd, alles met kans berekening zoals hierboven beschreven.

Echter, nu wil ik proberen nog een computer speler te maken, welke meer AI is. Heb hier zelf weinig ervaring mee, maar zou een minimax algoritme kunnen werken, ondanks dat het hier niet om een 2 player spel gaat zoals schaak bijvoorbeeld?

Dus ik zou zeggen, noem nog eens wat andere opties!

[ Voor 9% gewijzigd door BCC op 07-08-2006 23:06 ]

[Mithrandir]

BCC schreef op maandag 07 augustus 2006 @ 23:03:
[...]

En handige manier vinden om de score categorieën die je al ingevuld hebt te coderen en dit in je neurale netwerk stoppen als input.

Ok, tuurlijk, maar dat moet altijd. Het datamodel is een van de eerste dingen die je ontwerpt als je zoiets implementeert.

Nou, dat lijkt me wel duidelijk. Je kan nog zoveel kansrekening erop los laten, maar dat betekent niet automatisch dat je altijd wint. Geluk is nogal een groot onderdeel van Yathzee. En misschien zijn er wel hele rare goedwerkende strategiën waar je nog nooit aan gedacht hebt? Met een neuraal netwerk kun je dat soort dingen boven water krijgen.
Daarnaast, letterlijk van de TS:

Nu praat je onzin. Een NN kan ook geen geluk afdwingen. Het beste wat je kunt doen met Yahtzee is kansberekening; er zijn geen tactieken of geheimen die je kunt toepassen om het spel beter te doen.

Dus ik zou zeggen, noem nog eens wat andere opties!

Ga dus maar je wiskundeboeken weer oppakken en uitzoeken hoe het kansrekenen ook al weer zat

[BCC]

Mithrandir schreef op maandag 07 augustus 2006 @ 23:09:
[...]
BLAAT

ZUCHT!. Anders lees je het topic eens even voordat je wat post. Ik heb de TS eerst links naar papers over kansrekening gegeven. Daar was hij blij mee. Jammer genoeg vonden wat mensen daarna dat ze hun kansrekening skills moesten showen, wat nogal offtopic was. Daarna vroeg de TS om alternatieven. Ik geef deze, waarna jij vervolgens gaat lopen zeuren dat kansrekening beter is. Natuurlijk is dat statistisch gezien beter, maar daar gaat het helemaal niet om. Ik hoop dat de TS wat aan mijn ideeën heeft en zal verder niet off-topic gaan. Kom met iets productiefs!

[Mithrandir]

BCC schreef op maandag 07 augustus 2006 @ 23:15:
[...]
Ook blaat

Ik denk dat we het wel met elkaar eens zijn. Wat ik alleen probeer te zeggen is dat een NN lastiger zal worden dan je denkt. Ik probeer de TS ook te helpen, maar ben van mening dat een NN of andere AI technieken zoals een minimax boom of ander zoekalgoritme bijna altijd langzamer en minder precies zal zijn. Natuurlijk kan en mag hij het proberen, maar het resultaat zal, ben ik bang, tegenvallen.

Wat misschien wel handig kan zijn is Advice Language 0; daarmee kun je speelregels geven; wat moet onder welke condities gedaan worden door de speler?

[edit]
Ik kan weinig vinden op het internet over Advice Languages. In het kort komt het er op neer dat je een hele hoop if statements verschrijft. Denk aan:

code:

if( lotOfFives() ) {
 keepFives();
 throwAgain();
}

if( largeStreet() ) {
 keepStreet();
}

het is dus een soort van leesbare ifstatements maken door de expressies te groeperen in functies. Ik heb een implementatie in Prolog gebruikt wat er als volgt uit kwam te zien:

code:

edge_rule :: if not opp_king_in_squares
        then [ advancepawn ].

edge_rule :: if king_covers_all_front
        then [ advancepawn ].

edge_rule :: if king_covers_pawn_forefront and kings_oppose
        then [ advancepawn ].

edge_rule :: if not king_covers_pawn_front
        then [ movetopawn ].

edge_rule :: if king_covers_pawn_forefront and king_ison_pawn_front
        then [ movetonextideal ].

edge_rule :: if king_covers_pawn_front and not king_on_ideal_field
        then [ movetoideal ].

edge_rule :: if king_covers_pawn_front and opp_king_ison_pawn_front
        then [ opposeking ].
        
edge_rule :: if king_on_ideal_field and not kings_oppose
        then [ opposeking ].

else_rule :: if true
        then [ stupid_advance ].

Dit waren alle regels die nodig waren om een schaak eindspel tussen een pion en een koning vs een koning te spelen. Andere studenten hadden soms nog minder regels nodig om het zelfde te bereiken (denk aan 5 of 6).

[ Voor 53% gewijzigd door Mithrandir op 08-08-2006 09:47 ]

[MicroWhale]

ik zou 3 dingen berekenen na de worp:

per vakje dat nog open is:
1. de match (0..1) met de worp,
2. de kans dat met de overige dobbelstenen en worpen de match gemaakt kan worden,
3. mogelijke uitwegen met de stenen die 'vastgehouden worden' (om schade te beperken)

Aan de hand van die 3 gegevens kan een keuze gemaakt worden. (met evt. wegingsfactoren)

bovendien moet voor de 'bonus' het aantal stenen bijgehouden worden dat gegooid moet worden om de bonus alsnog te halen (bij invullen lagere worp herberekenen)