AI voor kaartspel met meerdere spelers

[jelmervos]

Ik ben momenteel bezig met een simulatie van een kaartspel. Hier kunnen 3 tot 6 spelers aan meedoen. Ik heb de applicatie nu helemaal draaien met 4 computer spelers welke precies volgens de regels willekeurige kaarten opgooien. Er is altijd een winnaar.

Natuurlijk moeten de computer spelers beter worden, maar hoe geef ik ze wat meer intelligentie? Ik wil niet mijn eigen tactiek met allemaal if statements inbouwen maar ik wil ze min of meer zelf een tactiek laten maken, eventueel met wat optimalisaties.

Ik kan kiezen voor een neuraal netwerk, maar het is moeilijk te bepalen of een bepaalde zet goed was of niet aangezien pas aan het einde van elke ronde bekend is welke speler er gewonnen heeft.

Ook compleet door rekenen van alle mogelijkheden is te complex.

Ik heb zelf geen ervaring met AI, maar misschien kan iemand mij een goeie tip geven wat ik vervolgens kan uitzoeken en uitwerken.

[BCC]

Wat het beste werkt, hangt een beetje van je doel af:

Leuke spelers: if statements + een dosis randomness. Afhankelijk van de moeilijkheidsgraad betere if statements.

Perfecte spelers: alles doorrekenen. Dit is niet veel werk aangezien je per zet maar een beperkt aantal mogelijkheden hebt. Zerker als je de kaarten gaat tellen.

Lerende spelers: Icm iets van een Neuraalnetwerk wat je eerst intrained. Dit houd wel in dat je niets kan zeggen over het niveau van de speler tijdens het spel, alleen iets over het gemiddelde niveau. Op het moment dat je je feedback moment zet na 1 ronde rondspelen van kaarten lijkt mij dat een prima mogelijkheid.

[Janoz]

Neuraal netwerk is in deze fase nogal schieten met een kanon op een mug. Daarnaast zul je sowieso erg veel voorwerk moeten doen voordat je uberhaupt een neuraal netwerk in kunt gaan zetten.

Wat je het beste kunt doen is kijken of je, aan de hand van de gegevens die de speler heeft (eigen kaarten, al opgegooide kaarten, huidige punten aantal, etc.. Alles afhankelijk van het spel zelf) een soort waarde kunt berekenen die aangeeft hoe goed de speler er voor staat. Vervolgens kun je per zet kijken welke een hogere score geeft. Afhankelijk van het spel kun je ook enkele zetten vooruit kijken om te zien welke de hoogste score heeft.

[jelmervos]

Ik heb eerst geprobeerd alles door te rekenen, dus brute-force alle mogelijke combinaties bij langs. Helaas kost dit teveel geheugen en rekentijd. Ook is in het begin de enige bekende factor je eigen kaarten. De andere spelers kunnen dus alle combinaties van de rest van de kaarten hebben.

Ook heb ik een speler gemaakt welke punten toekent aan de kaarten die hij heeft. Dit werkt natuurlijk al veel sneller. Maar probleem is dat je dan toch weer je eigen tactiek aan het programmeren bent. Immers bepaal ik hoe de punten worden verdeeld over de kaarten.

Is er nog een andere oplossing om een beetje leuke tegenspeler te maken? Liefst iets wat zichzelf enigszins kan trainen en corrigeren.

[BCC]

De waardes van die kaarten is dan wel weer iets wat je heel goed kan intrainen/leren dmv een neuraal netwerkje.

[Sihaya]

Misschien kun je meerdere scoreberekeningen definiëren waaruit de computer aan het begin van het spel een random keuze maakt. De scoreberekening kan dan gebruikt worden als evaluatiefunctie bij een minimax algoritme, waarbij je de tree maar tot een bepaalde hoogte evalueert.

[Hydra]

Bij kaartspellen komt het bij AI vooral aan op kaarten tellen (dus welke zitten er in het spel / welke kunnen er nog komen), en dan statestiek loslaten op welke combinaties van kaarten de beste kansen opleveren. Kun je vertellen om welk kaartspel het gaat?

[PrisonerOfPain]

99% van de tijd kun je voor 'game AI' gewoon af met een hiërarchische finite state machine om simpele behaviour in elkaar te knopen, mits het natuurlijk state gebasseerd is.

Wat je in dit geval misschien eerder wil is per beurt je maximale verlieskansen verkleinen. Daar komt een minmax algoritme al snel om de hoek kijken.

Als je spel bestaat uit het behalven van bepaalde langetermijndoelen behaald kunnen worden herhaaldelijk verschillende kortetermijndoelen uit te voeren (denk Kolonisten van Catan, Risk, de gemiddelde RTS) dan kun je wellicht gaan denken aan een Planner om je AI aan te sturen, (heel) simpel gezegt probeer je iedere 'tick' de beste oplossing / pad door een graaf met mogelijkheden te vinden om zo je doel te bereiken. Als dan de kortetermijndoelen veranderen veranderd je pad ook, maar je langetermijndoel hoeft daarvoor niet te veranderen.

BCC schreef op dinsdag 24 februari 2009 @ 17:51:
De waardes van die kaarten is dan wel weer iets wat je heel goed kan intrainen/leren dmv een neuraal netwerkje.

't Kan een stuk makkelijker door een generic algorithm los te laten op die waardes. Als selectie methode gebruik je de winkansen van de speler, dat statestiek zou je aan kunnen passen op de moeilijkheidsgraad.

Dit met een neuraal netwerk bepalen lijkt me een minder goed idee vanwege de onvoorspelbaarheid van je netwerk en de afhankelijkheid van de speelmethoden van je "trainer". Ander idee is om gewoon een aantal mensen te laten test-spelen met verschillende weegfactoren.

[BCC]

Ik zou gewoon een aantal maken: random, genetisch, neuraal, logisch en dan tegen elkaar spelen maar