Strategi för spel där man satsar/lägger sig

Hej!

Jag tänkte göra ett nytt försök att få ordning på AI:n i mitt eggdrop-spel. Allt annat i spelet har varit färdigt länge. Det är, liksom poker, ett spel där man kan höja, syna, passa eller lägga sig, men med bara två spelare (spelaren och datorn) och med bara ett kort var. En summa ligger i potten redan innan någon börjar agera, och för att förenkla går det inte att satsa valfritt belopp utan bara att dubbla. Högst kort vinner om inte den andre lägger sig, precis som i poker. Om båda har samma kort vinner datorn; detta är fördelen som ska göra att datorn (jag) tjänar på det i längden.

Jag har kommit en bit på vägen, men har inte lyckats knyta ihop det till en eller flera formler eller algoritmer.

Först och främst konstaterar jag något självklart: att det alltid finns ett (eller flera lika bra) sätt att spela på när det är min (datorns) tur, som är bättre än alla andra sätt. Det är det jag är ute efter - att hitta det bästa sättet att spela utifrån en specifik informationskombination, t.ex. "potten startar på 10:-", "jag har knekt" och "motståndaren passar". Om jag alltid spelar perfekt, spelet är rättvist (datorn och spelaren turas om att börja) och jag har den lilla fördelen av att vinna när korten är lika, kan jag inte förlora i längden. Plus bonusen jag får när spelaren avviker från sin perfekta strategi, t.ex. dubblar för ofta när han har damer för att han gillar dem, eller blir skrämd för mycket eller för lite av mina satsningar.

För det andra: att spela perfekt är inte samma sak som att spela statiskt. Jag kan t.ex. inte dubbla varje gång jag har 10 och motståndaren passar. Då visar jag vad jag har för kort. Det perfekta sättet inkluderar att slumpa mellan olika val, och det är procenten för de olika valen som jag behöver finna för att spela perfekt. Jag slumpar ett tal mellan t.ex. 0 och 1. Blir det mellan 0 och x lägger jag mig, blir det mellan x och y synar jag och blir det mellan y och 1 dubblar jag (0 <= x <= y <= 1). Eller liknande.

För det tredje tror jag att det här är ett problem som bara kan lösas m.h.a. att introducera någon slags oändlighet, dvs han-tror-jag-tror-han-tror-osv... Antingen går det att räkna ut exakt med någon formel eller så måste jag hitta en bra approximations-algoritm som blir bättre och bättre ju fler gånger jag kör den, och sen välja hur mycket tid som är acceptabelt att datorn tänker under.

---

När det gäller mitt informationsinsamlande, så har jag ingen aning om jag måste komma ihåg alla tidigare givar som jag har spelat mot just den här spelaren och hur han/hon har agerat tidigare under den här handen, för att kunna spela rättvist... Eller om jag kan få ett rättvist spel utan att komma ihåg något av dem, dvs bara utgå från vad som ligger i potten, vad satsningen är emot mig och vad jag har för kort, och spela perfekt bara utifrån det. Den första gången jag möter en spelare och inte har några uppgifter om hur han spelar, så har jag bara två saker att utgå ifrån: hur mycket pengar han har totalt och hur mycket pengar jag, banken, har totalt. Sen lär jag väl balansera storleken på hans satsning emot sannolikheten att han ska bli bankrutt i längden jämfört med sannolikheten att jag ska bli bankrutt i längden. Och räkna in hur högt kort jag har, såklart. I det här låtsas-spelet har jag oändligt mycket pengar, så jag kanske måste jämföra med sannolikheten för att han ska _dubbla_ sina pengar jämfört med sannolikheten att han ska bli bankrutt?

Finns det någon information om det här på nätet?

Problemet är att motspelaren bidrar med falsk information. Han kanske gör något i bluffsyfte. Det finns inget perfekt spel av det skälet.
Jag tror du är inne på rätt spår när du är ute efter en sannolikhetsbaserad bot som bettar och synar med viss sannolikhet beroende på kort och pot. Det är det enklaste och borde gå att maximera så att du åtminstone vinner mot de flesta spelare.

Om du är ute efter att göra någon bot som tar spelarens strategi i beaktning så är det nog bara att "buckle up", känns spontant som att det är väldigt komplicerat. Jag föreslår neuralt nätverk för lagring av tidigare spel i såna fall och att sätta vikterna baserat på hur många likadana lägen som uppstått och lett till en viss sak; då får du snyggt med sannolikhetsperspektivet.

Alternativt kan du parametrisera botten med en jäkla massa parametrar och köra en heuristisk sökning efter parametrar som funkar bra. Typ låta två bottar spela 100 spel mot varandra, evaluera de båda och sen skapa en ny motståndare till den bättre botten. Jag föreslår i såna fall Harmony Search, stilig lösning som funkar bra och inte är speciellt svår att läsa in sig på.

Att botten behöver resonera stegvis är nog.... mja... Jag tror inte på det, att du behöver någon rekursiv process alltså. Ta med hur mycket spelaren förlorat i pengar eller nåt liknande som parameter så får du med lite förutspåelse implicit. Som sagt, massor med parametrar och en harmony search är något jag skulle vara intresserad av att se; har haft funderingar på att göra det i ett simulerat pokerspel men har aldrig fått tummen ur.

Vad tror du, är det något som låter vettigt?

Här är du inne på tankar som ligger väldigt nära spelteori, särskilt Nash-jämvikt, att spela optimalt mot en perfekt motståndare och att hitta den optimala strategin genom en slags indifferens-kalkyler.

Jag tycker absolut att du ska läsa relevanta delar av The Mathematics of Poker.
http://www.amazon.co.uk/The-Mathemat...1044850&sr=8-1

De använder i boken spelteori på ett mycket praktiskt sätt, med en överskådlig metod man lätt kan använda själv, genom att räkna ut optimalt spel i olika förenklade låtsasspel - vilka i sin tur ger indikationer på vad som kan vara optimalt i liknande spel, där deras fokus är på poker.

Med den metoden skulle du kunna ställa upp ditt spel och göra den form av indifferenskalkyl som Chen och Ankenman gör.

Sedan är nästan allt i boken mycket värdefullt. Dvs spelteorin är väldigt intressant, även om den är väl begränsad till att nå jämvikt mot en perfekt spelare, medan den typiske spelaren är inriktad mot att spela exploaterande mot en spelare med svagheter.

Suveränt... jag tror att jag har hört namnet på den boken tidigare. Den kommer att beställas och bli kvällsläsning.


Bara matematik, och inget om människors beteende, låter som något att börja med.

Du får det att låta som att motståndaren har en fördel för att han kan bluffa. Tänk på att jag också har (exakt samma) möjlighet att bluffa, och om reglerna för spelet är 100% rättvist är det bara mitt och motståndarens agerande som avgör vem som vinner. Man kan inte vinna i poker bara genom att bluffa mer än de andra (om man inte alltid har de bästa korten förstås, men nu antar jag en rättvis fördelning av korten), för de andra kan göra samma sak.


Visa mig ett sätt att spela på som jag inte kan slå, så spelar jag så istället. Eller snarare: om jag med en viss strategi vinner mer pengar från folk i medel, än med en annan, så använder jag den.

Givetvis, jag trodde du talade om en AI som skulle spela mot riktiga spelare däremot och från det perspektivet vill jag bara säga att det inte finns något perfekt spel just för att det aldrig finns perfekt information. Att simulera bluffspel är inte det enklaste heller, men givetvis möjligt. Bluff är bara ett exempel på falsk/bristande information, se mitt exempel nedan.

Jag förstår kanske inte premisserna. Det finns inget sånt sätt, så som jag tolkat dig. Blackjack är det spel jag tänker mig är närmast det du beskriver, men det vilar helt på statistik; spelarna kan inte spela mot den mänskliga faktorn hos motspelaren så att säga.

Skälet till att man inte har någon form av "hus-spel" i poker är just för att det går att spela både på korten och människorna, och då kan man vinna på annat än statistik; alltså kan huset förlora. Ditt spel är inte heller ett hus-spel, och du kan inte bygga en bot som spelar enbart på statistik och som vinner mot alla spelare. Det kanske finns en spelare som bara spelar på dam, kung och ess till exempel, och om din bot då har >0% sannolikhet att spela på knekt eller neråt så kommer den alltid förlora när den spelar på knekt eller neråt.

Däremot är jag övertygad om att det är det enklaste sättet att göra en bra bot (som oftast vinner); att göra en som spelar efter en sannolikhet som är baserad på storlek på pot och kort i hand - kanske på fler parametrar - och hoppas på att man inte stöter på "fel" spelare.

Alla ändliga spel har en Nash-jämvikt. Även detta.

Det går att spela detta spel perfekt, men en optimal strategin kommer att innefatta att slumpa mellan olika val, som nämndes ovan.

Ja, då vet jag inte om vi har olika syn på perfekt. Fast det är klart, i alla lägen finns ett bästa val, det kan jag hålla med om. Återigen, jag ser inte vilken modell som kan finna den optimala strategin trivialt. Sitter du möjligtvis på en vinnande pokerbot?

Edit: Alltså, under ideala förhållanden går det säkert att finna en strategi - även om jag inte ser hur man skulle göra det annat än med parametersökning eller dylikt - men mot spelare kan man sällan ens utgå från ideala förhållanden. Menar du att det saknar relevans?

Jag tror att det är lite begreppsförvirring här. Att spela optimalt, balanserat, perfekt o.s.v är begrepp som i denna kontext ofta används inom en gren av spelteorin. Där är man intresserad av att hitta indifferens gentemot en perfekt motståndare.

Vissa 'anhängare' av spelteorier av detta slag är så entusiastiska att de inte inser de teoretiska begränsningarna.

Mot denna spelteori kan vi ställa en exploaterande spelteori, som nog ligger ganska nära hur mannen-på-gatan eller 'sunda förnuftet' skulle tro att spelteoretiker gör för att hitta det perfekta spelet. Nämligen att utnyttja motståndarens svagheter.

Ett exempel på ett enkelt spel där skillnaden är tydlig är sten-sax-påse. De som är skickliga i detta spel kan vara fullständigt oslagbara mot de flesta människor, genom att utnyttja svagheter hos motståndarna. Det vanlig 'spelteori' har att bjuda på är att spela 'optimalt' och därmed inte förlora, utan gå jämt upp, gentemot en perfekt motståndare. Detta är ju oerhört ointressant och till och med tråkigt ur ett pragmatiskt perspektiv.

Fast nu använder du uttryck som "riktiga spelare" och "den mänskliga faktorn" som om den mänskliga hjärnan skulle vara magisk på något vis. Den information man har använder man. En "mänsklig" spelare gör likadant.


Jo, jag måste väl samla all information och komma ihåg den. Då spelar jag inte efter statistik längre, utan anpassar mig efter spelaren, och då kommer det aldrig att finnas någon "fel" spelare; bara spelare som jag inte vinner lika mycket av.

Den mänskliga hjärnan är allt annat än magisk i vissa fall, men ganska magisk i andra ^^ Nå, jag använder "mänskliga faktorn" just för att det finns en enorm skillnad i komplexitet på kod man sitter och skriver hemma och på hur en människa spelar ett spel; oavsett om det beror på magi eller något annat!

Precis, det är en intressant grej att experimentera med! Vilken metod hade du tänkt använda? Parametrar - typ aggressivitet osv - som styr botten? Hur ska du "komma ihåg" motspelaren? Går nog göra med parametrar också. Har du några funderingar?

Jo det var inte det här perspektivet jag talade från; det känns för idealt i sammanhanget.

Precis, det var från det perspektivet jag såg spelet i topic - exploaterande. Känns inte som att det är lösbart med enbart spelteorins; fast man kan säkert få bra funderingar därifrån ändå förstås!

Vet att forskningen i pokerspelande kod inte avancerar lika fort som schackspelande kod eller dylikt, men det går trots allt framåt (vill jag minnas) och det är säkert möjligt att hitta hyffsade approximationer; det här spelet i topic är nog ett betydligt enklare problem också. Perfekt utgångspunkt för att experimentera