Klaverjas AI ?

[Verwijderd]

Hallo,

ik (eigenlijk we) zijn bezig een Klaverjas programma te schrijven in Java voor een Object Oriented Programming course. Nou werkt de interface en communicatie met de server etc al met al heel aardig en als je 4 man hebt kan je al een leuk potje doen.
MAAR: het zou natuurlijk leuk zijn als je ook in je uppie een (_leuk_) potje kan spelen. Daarom hebben we ook de mogelijkheid om bots aan je spelletje toe te voegen, maar goed die moeten wel ook daadwerkelijk werken. De zogenaamde 'easybot' die random kaarten opgooit zonder te verzaken is natuurlijk niet zo moeilijk. Maar de 'hardbot' of eventuele 'unfairbot' is natuurlijk een ander verhaal. Ik vroeg me of hier niet toevallig AI mensen zijn die bijvoorbeeld allang een klaverjas beslisboom hebben gemaakt of iets dergelijks.

Voor de duidelijkheid: We worden becijferd op het programmeer gedeelte en niet op het AI gedeelte, dus voor het cijfer boeit het nou niet of het bot nou een strategy heeft of niet. Maar het zou natuurlijk wel leuk zijn als het iets meer deed als random kaarten opgooien.

Dus zijn hier mensen die zoiets gemaakt hebben of die daar wel ideeen over hebben, persoonlijk kan ik wel een if-statement maken dat ongeveer zo'n 500 regels gaat beslaan en die 75% van de voor de hand liggende situaties aankan (of voor 80% aankan) maar goed klaverjas win je natuurlijk met precies die _andere_ 25%

<font size=1>Mod-break:
Discussies lopen gewoon via het forum. Het is niet de bedoeling dat dit via de mail wordt afgehandeld. Op deze manier hebben andere mensen er ook wat aan.</font>

ik ben benieuwd :-)

[Janoz]

Je kunt iig wel + punten krijgen waneer je in je ontwerp hier rekening mee houd. Laatste AI die ik geschreven had was voor pong, maar wat ik eigenlijk ff wilde vertellen is de manier waarop ik het in mijn programma had.

Ik heb namelijk gebruik gemaakt van een abstracte class player. Hierin heb ik verschillende methodes gezet die nodig zijn voor speler acties. Vervolgens heb ik twee kind klassen geschreven. HumanPlayer en SimpleAIPlayer. Door deze structuur te gebruiken hoef je in je Game onderdeel geen rekening te houden met wat voor spelers er meedoen.

Je geeft gewoon aan de speler door welke kaarten hij heeft, welke kaarten op tafel worden gegooid en andere relevante dingen (Wie past, wie speeld enz enz) Hierdoor kun je je AI compleet los ontwikkelen van je programma en kun je dus op een simpele manier allemaal verschillende types AI speler erin zetten. De gespeelde kaarten zul je dus gewoon net als bij menselijke spelers in je AI gedeelte bij moeten houden. Op deze manier voorkom je trouwens ook dat AI vals kan spelen, omdat deze precies hetzelfde weet als de menselijke speler.(En voor fun kun je zelfs de abstracte class verspreiden onder wat mede programmeurs en kun je wedstrijdjes houden tussen de AI's van verschillende mensen)

Een ander voordeel van deze benadering is dat je het UI gedeelte uit de Game en in de speler zet. Hierdoor kun je 1 'game engine' gebruiken voor het spelen via een netwerk, maar ook als applet op een webpagina. Je zou zelfs gerbuik kunnen maken van wat flash . In mijn Pong spel gebruikte ik ongeveer hetzelfde. Hiervoor had ik een mouse player en een keyboard player.

[ThePriest]

uiteindelijk kom je dan TOCH wel op een if then case else dinges structuur verwacht ik, zal vast wel meer dan 500 regels worden, wil je een beetje klaverjas-bot hebben...

[Janoz]

if then else? Mischien is het makkelijker om voor elke kaart een score te berekenen. Een kaart die je niet op mag gooien krijgt 0 en een kaart waarmee je de slag kan pakken krijgt heel veel. Als je vervolgens nog een set regels bedenkt die van invloed zijn bij het opgooien van een kaart (hmm, slag voor mijn maat en ik heb de aas? Nou, dan krijgt dit seintje x punten) kun je uiteindelijk adhv de scores bepalen welke kaart je opgooid.

[Verwijderd]

Janoz: dat is ook precies de manier waarop het nu geimplementeerd is: Met nog een heel klein tussenstapje.

Class BotXXXX extends Bot en Bot extends Player

in Bot heb ik 2 abstracte methods selectTrump( ) en cardToPlay( CardList[] memory, en CardList cardsOnTable ). En in bot zit nog een protected CardList hand wat dus de kaarten in je hand zijn. De class BotXXXX hoeft dus alleen die 2 abstracte methods te overschrijven en dan gaat alles goed. Dus in zoverre heb ik wel het 'ai' en het andere gedeelte gescheiden en ook eerlijk gehouden.
(memory zijn de opgegooide kaarten memory[Game.NORTH] is dus de lijst van kaarten die de player die NORTH zit heeft opgegooid in volgorde, maar goed dat zijn impl.details)

ik vroeg me dus meer af OF er al iemand was die zoiets ooit in een of andere programmeertaal of AI taal al in elkaar gedraaid had.. puur het toekennen van een waarde gegeven een aantal variabelen zoals in dit geval cardsOnTable, memory en hand.

Als dit niet het geval is zal ik zelf een waardensysteem moeten bedenken uiteraard, maar ik kan me niet voorstellen dat er niemand in de AI wereld dit ooit heeft gedaan.. het is toch een populair spel of niet :-) zeker onder studenten.

Auke

ps: dus als je zelf een bot wilt schrijven geef je maar een emailtje.. ik gooi hem er zo in, laten we ze 2000000 potjes tegen elkaar spelen :-)

<edit>
ik lees morgen verder, ik krijg een beetje RSI handen
</edit>

[BrammeS]

Ik heb eens een ai gebouwd voor boter kaas en eieren en dan niet zo eentje opgebouwd met een stel if statements die voor iedere move een standaart tegenmove had, maar eentje die daadwerkelijk vooruit probeerde te denken. Alleen de hoeveelheid code die ik hiervoor had bedacht was vele maalen langer als de code met de if statements. het ging mij dan ook puur om het maken van een stukje code dat de volgende set van de tegenspeler probeert te anticipeeren en daarop een beslissing probeert te nemen.

Vaak eindig je dan met een paar verschillende opties. En dan is de prioriteit van bepaalde opties weer moeilijk te bepalen. Dus eindig je in mijn geval nog met een random statement. Dat is ook het knelpunt zelfs bij iets mega simpels als boter kaas en eieren. Een computer laten denken als een mens. daar komen veel random statements bij kijken.

[Infinitive]

Voor boterkaas en eieren, dammen (zelfs schaken) kan je gebruik maken van alfa-beta heuristics (als ik het goede woordt te pakken heb). Of je dat voor klaverjassen kan gebruiken weet ik niet (heb wel eens gespeeld maar weet de regels al lang niet meer).

Maar goed, waar alfo-beta heuristics over gaan is dat je een boomstructuur maakt waarbij elke laag in je boom overeenkomt met een "beurt" (hetzij van jouw of van je tegenstander). Voor elke laag zijn het aantal knopen(nodes) de mogelijke zetten van die beurt. Je kan dan ook al in de toekomst gaan denken en voor elke beurt in de toekomst een laag aan je boom toevoegen. Op een gegeven moment kan je voor een pad in je boom geen beurten meer toevoegen, want er moet een beurt zijn die het spel beindigd (anders heb je een spel waarin een nooit win en nooit verlies situatie in zit).
Dus geheel aan de onderkant van de boom heb je een win of een verlies situatie.
Zo'n situatie kan je een score geven. Bijvoorbeeld 0 voor verlies en 1 voor win.
Nu kan je er vanuit gaan dat je tegenstander vreselijk slim is en jij ook. Je gaat er vanuit dat de tegenstander altijd de keuze neemt die voor jouw het slechtste uitkomt. Hetzelfde doe je zelf natuurlijk.
Je kan nu je boom terug naar boven lopen een score toekennen aan de hand van de score van de knopen onder je en aan de hand van het gegeven wie aan de beurt is. Bijvoorbeeld, als ik aan de beurt ben bij een zekere node, dan kies ik het kind met de hoogste score. Deze score kan ik dan ook toewijzen aan de huidige node. Als de tegenstander aan de beurt is dan kiest hij degene met de slechte score. Deze kan je wijs je toe aan de huidige node.
Dit proces kan je tot boven toe herhalen en geheel bovenaan de keuze met de hoogste score/meeste mogelijkheden nemen.
Je kunt je vast wel voorstellen dat je hier nogal op kan varieren.
Je kan je ook wel voorstellen dat dit best wel grote structuren worden, zelfs bij iets relatief simpels als boter, kaas en eiren (want dat is al iets van 9!). Vandaar dat men doorgaans de boom afkapt op een aantal niveaus en dat er aan de hand van wat beschikbare gegevens van die beurt (bijvoorbeeld het aantal stenen dat je nog hebt bij dammen ofzo) een ruwe score bedenkt. Daar is het heuristiek ook op gebaseerd: ik ben net zo slim als de tegenstander, maar ik kijk iets dieper en kan hem zo net te slim diep ( ) af zijn.

(dit is ongeveer hoe alfa-beta heuristiek in elkaar zit... ik weet het niet geheel, dus iemand die een AI studie gevolgt heeft... don't target your killer droids at me!)

Overigens denk ik niet dat je dit voor klaverjassen kan gebruiken. Daar zul je toch meer met statistiek te maken hebben (als je de computer eerlijk wil laten spelen natuurlijk). Maar je kan je misschien voorstellen dat je dan een soort van kansboom maakt.

[T.T.]

Ik heb wel eens een klaverjasspel met computertegenstanders gemaakt en het makkelijkst was het om een beslisboom te gebruiken. Ik heb toen samen met iemand anders die boom opgesteld en die werd best groot (tenminste dat vond ik ).

if then else? Mischien is het makkelijker om voor elke kaart een score te berekenen. Een kaart die je niet op mag gooien krijgt 0 en een kaart waarmee je de slag kan pakken krijgt heel veel. Als je vervolgens nog een set regels bedenkt die van invloed zijn bij het opgooien van een kaart (hmm, slag voor mijn maat en ik heb de aas? Nou, dan krijgt dit seintje x punten) kun je uiteindelijk adhv de scores bepalen welke kaart je opgooid.

Dat kan ook, maar het probleem bij klaverjassen is dus dat je niet weet wat je maat/tegenstanders hebben. Bovendien wil je er rekening houden dat je wilt seinen, dat maat speelt of juist tegenstander enz enz. Ben je als 2e aan de beurt met opgooien dan moet je de kans schatten dat je maat/jij die kan pakken en of het wel slim is om de kaart te pakken...

kortom: er zijn zo veel situaties dat je het best met een beslisboom kan werken volgens mij. Ik heb ook geprobeerd om een versie te maken die alles gaat uitrekenen (+schatten) op basis van kansen, maar dat was LASTIG.

Helaas heb ik de beslisboom niet meer, heb het programma nooit afgemaakt bovendien

alfa-beta heuristics...

Dat gaat volgens mij niet op voor klaverjassen omdat je niet weet wat de tegenstander kan doen enz.
Meer iets voor schaken.

[Dash2in1]

Wat ik me kan herinneren had een programmaatje AS klaver wel aardige computerspelers. Misschien dat je de maker "appiesoft" (als ik het me goed herinner) wat vragen over dit onderwerp..

[pjonk]

Ik heb vroeger een keer een AI gemaakt voor toepen in Quickbasic en ben er nog steeds trots op.
De AI was niet zo moeilijk te maken aangezien je maar met 4 kaarten speelt.

Klik hier voor een screenshot.
Helaas doen de links naar de download het niet meer.

[Verwijderd]

Die alpha-beta heurestiek heb ik inderdaad ook weleens gehad bij een van mijn zeer weinige (verplichte) AI colleges. Maar is inderdaad niet echt toepasbaar hier omdat je niet een duidelijk beeld hebt wat de bots voor kaarten in hun handen (Tuurlijk dat kan wel, maar dan is de lol er ook wel een beetje af, dan is het niet zo moeilijk) hebben en er zijn meerdere spelers (voor 2 spelers werkt het nog wel).

TT: eigenlijk had ik gehoopt op een reactie van jou, want ik ben volgens mij wel eens langs je 'parkeerbonnen' pagina gekomen. Beetje jammer dat je die boom kwijtbent maar goed.

Ik zal in ieder geval nog even die appiesoft vragen hoe hij het in elkaar geknoopt heeft, maar ik kan me niet voorstellen dat hij dat even gaat opsturen hij is al bij versie 5.2 van ASKlaver.

Bedankt in ieder geval, ik hoop nog steeds op de post van iemand die het wel eens heeft gedaan en deze nog _wel_ heeft

Auke