[PROG][AI] Dammen Ai - min max tree met alpha beta cutoffs probleemke

[joyrider]

Ik weet ni of iemand iets weet van min max search trees (met alpha beta cutoffs) maar ik zit met een probleemke voor een dam spel.

Het zit zo: een van de regels van dammen is dat je verplicht bent te nemen wanneer je kunt en indien je dan nog is kunt nemen je dit ook moet doen tot wanneer je niet meer kan nemen. (lijkt me vrij duidelijk).

Nu wat ik tot nu toe heb is dat ik als je 2x achter elkaar kunt nemen ik dit bekijk als 2 aparte moves van dezelfde speler.

maar min max baseert zich op het feit dat elke speler om beurten speelt. Nu zit ik dus met een probleem want als je 2 stukken kunt nemen speelt dezelfde speler feitelijk 2x. Moet ik dan bijvoorbeeld als de computer de maximimzing speler is, en hij kan 2 stukken nemen nog eens de max functie oproepen zodat hij het volgende stuk gaat pakken ? indien zo geeft dit geen probleem bij de min max tree ? ik kan het moeilijk visueel voorstellen wat effect dit heeft. en ik weet niet of dit correct is, iemand dat dit weet ?

[kwitters]

Als de speler 2x achter elkaar kan nemen dan mag je dit maar beschouwen als 1 move. Het belangrijkste aan een min-max tree is dat die volgorde van min/max/min/... effectief behouden wordt op elk nivau van de tree.

De nodes van min-max trees zijn eigelijk game states na het einde van een "move" of turn (beurt) van een speler. Je kan bijvoorbeeld ook een turn-based strategiespel met min-max implementeren, waar de speler eigelijk meerdere pionnen tegelijk kan verplaatsen in 1 beurt. Maar toch zal deze verplaatsing van verschillende pionnen als 1 move worden beschoud in min-max.

Concreet doe je dit als volgt: als je in je tree een niveau naar beneden gaat, dan doe je dit met de mogelijke "moves" van een speler te gereneren. Dit genereren van stappen moet dus in het geval van dammen ook rekening houden dat de speler soms 2x springt met zijn pion.

Hopelijk snap je een beetje wat ik bedoel, en anders vraag je nog maar wat meer uitleg

[killgore]

Je moet gewoon zien dat in uw tree waarop je de minmaxing doet de 2 stukken nemen als 1 node worden gezien (uw nodes zijn eigenlijk beurten, onafhankelijk van #stappen die je doet).

edit: ffs, voorafgegaan door kwitters ^^

[joyrider]

jup snap het, zal wa aanpassingen moet maken dan zodat die moves als 1 move bezien worden. Ik had ze elk apart. ben ervoor aant probrere van op 1 punt een vector van moves te generen nu da lukt me wel maar zit met het probleem dat als je bvb bij de eerste zet 1 stuk kan pakken en dan op een plek komt waar je 2 stukken kunt pakken dat ik feitelijk een nieuwe vector moet beginnen met de stappen van de vorige er al in. Zal effe foefelen worden om da goe te krijge

[killgore]

Zo moeilijk is het niet denk ik?

Als je je tree opbouwt zal je sowieso toch eerst kijken of er een slag mogelijk is? Dit while je nu en ipv 1 slag/node toe te voegen voeg je nu een lijst van slagen per node toe (of een iets minder geheugenslorpende oplossing ).

[[BAT] Hydra]

Interessant, wat is de diepte van je boom? Om de hoeveel beurten update je je boom met nieuwe nodes? Ik neem aan dat je niet alle mogelijke spelbordsituaties totdat iemand wint in je boom probeert op te nemen?

[joyrider]

momenteel ben ik feitelijk alles nog aan het testen, had om die min max uit te testen een onverslaanbare tic tac toe speler gemaakt, maar daar kun je gewoon helemaal tot op het einde van een spel gaan. Hier moet ik nog testen hoe snel het feitelijk is en ik update mijn boom bij elke zet maar ik ga de diepte beperken per zet bvb maximaal 2 of 3 diepte (zetten verder kijken). Maar dat hangt af van de snelheid waarmee het werkt (en heb een vermoeden dat het ni snel zal zijn).Ik moet de bord evaluatie functie ook nog altijd maken maar Momenteel lukt het me nog altijd niet om die moves te genereren wat ik wil bekomen is een vector van vectoren van SMove. waarbij de hoofdvector alle zette bevat en de subvector alle zetten in 1 turn bevat.

Ik probreer het via recursie maar het lukt niet echt goed. maar ik geef het nog ni op heb nog een ander iedeetje hoe ik die vector kan bekomen. Moest het me echt ni lukken post ik de (immens slechte) code die ik tot nu toe heb

[joyrider]

ok ik heb het gevonden en ondertussen alles aangepast zodat die zetten als 1 turn beschouwd worden en het lijkt goed te werken.

Ik weet ni goed waar ik allemaal moet naar kijken in mijn bord evuluatie functie (die gebruikt wordt voor min max). Momenteel kijk ik naar het volgende:
kan computer winnen : voeg een hoge waarde toe aan de score
kan speler winnen: trek een zelfde hoge waarde af van de score
Voor elk normaal stuk van computer : voeg een waarde toe
voor elk normaal stuk van de speler : trek een waarde af
voor elk gekroond stuk van de computer : voeg een waarde toe (hoger als die van een normaal stuk)
voor elk gekroond stuk van de speler : trek een waarde af (lager als die van een normaal stuk).
das wat ik momenteel heb, maar das belange ni genoeg, ik ga wsl ook nog een waarde geven voor de positie van de stukken: bvb stukken die in het midde staan een hogere score geven dan die dat aan de zijkant staan aangezien die meer bewegingsvrijheid hebben. en die waarde verhogen naarmate men meer kans heeft om een gekroond stuk te bekomen.

naar wat kan ik nog kijken in men bord evaluatie functie?, ik weet ni of het aantal mogelijke "jumps" intresant zijn aangezien dat min of meer bij zit in het aantal stukken op het bord, als men een stap verder kijkt zit dit bij in de score verwerkt. verder heb ik geen idee meer.

Ook vroeg ik me af of er bij dammen ooit een mogelijkheid is waarbij 2 of meer stukken van dezelfde speler elk een ander stuk van de tegenspeler kunnen nemen. Ik denk het niet maar ben er niet zeker van. (edit: kan dus wel gebeuren, net voor gehad in een matchke, waar ik verloren ben trouwens ook al zet hij stomme zetten in het begin van het spel)

Ik ben ook van plan 2 computers tegen elkaar te laten spelen, met de waarden een beetje aangepast (zoals diepte, de score die berekent wordt in de bord evaluatie functie) om zo tot een goeie computer speler te komen.

ah ja heb is de diepte getest, kan tot 5 diep gaan, moet draaien op een arm 200 mhz cpu kweetni of da goed is of ni. kan mss nog eentje verder gaan want de cpu zet zijn move nog vrij rap duurd mss een halve second a 1 second maar moet nog alles verder uittesten daarvoor