Spelteoretiskt optimalt vs allmänspråkligt optimalt

[Klyka]

När man talar om spelteori används ofta begreppet "optimal". Användningen av detta ord är lite förvirrande, och denna text är ett försök att reda ut begreppen.

 

Inom spelteori talas ofta om optimal contra exploativ strategi. En exploativ strategi är en strategi som går ut på att utnyttja motståndarens misstag. Om han till exempel synar för ofta så bör man värdebetta mer och bluffa mindre mot honom för att exploatera detta misstag.

 

Optimal strategi går istället ut på att inte kunna exploateras själv. En optimal strategi är en oexploaterbar strategi. Man kan också uttrycka det så att en spelteoretiskt optimal strategi maximalt exploaterar motståndaren om han också spelar spelteoretiskt optimalt. (1)

 

Vad innebär då detta? Jo, om båda spelar spelteoretiskt optimalt, så kan inte den ena av dem öka sitt EV genom att ändra sin strategi. Med andra ord: Han kan inte ytterligare exploatera sin motståndare. Vidare så innebär detta att om du spelar spelteoretiskt optimalt mot en spelare som inte spelar spelteoretiskt optimalt så kommer ditt EV att vara positivt (Edit: I stort sett, se dock diskussionen nedan). Du kan inte ha negativt EV med en optimal strategi (detta gäller under förutsättning att det inte tas någon rake).

 

Men här kommer kruxet: Den spelteoretiskt optimala strategin är sällan optimal i allmänspråklig bemärkelse. Om din motståndare spelar för löst så är det ofta bättre att värdebetta mer än den optimala strategin förespråkar. Att göra avsteg från den optimala strategin innebär mot denna motståndare att du ökar ditt EV, så hur optimal var den optimala strategin egentligen?

 

Här är det viktigt att komma ihåg att "optimal" bara innebär att den är optimal mot en spelare som också spelar optimalt. Att det kallas optimalt är olyckligt, iom att det skapar en sådan språklig förvirring. Strategin som innebär att du värdebettar mer mot denna spelare är en exploativ strategi snarare än spelteoretiskt optimal, men den kan mycket väl vara optimal i allmänspråklig betydelse...

 

I många diskussioner är det en som diskuterar optimal strategi i spelteoretisk betydelse och hans diskussionspartner diskuterar vad som är optimalt i allmänspråklig betydelse. De talar förbi varandra och kan av den anledningen inte komma överens.

 

Jag hoppas att denna ganska röriga text kan kasta något litet ljus över diskussionerna om spelteori här på forumet. Länka gärna hit om begreppsförvirring uppstår i nån tråd.

 

___

 

(1) Edit 100401: "Man kan också uttrycka det så att en spelteoretiskt optimal strategi maximalt exploaterar motståndaren om han också spelar spelteoretiskt optimalt". Detta är inte riktigt sant. Det implicerar att den spelteoretiskt optimala strategin är en strategi vars syfte är att exploatera sin systerstrategi, vilket är missledande. Iom att den optimala strategin är just oexploaterbar så är den citerade meningen rappakalja.

 

Vad som däremot är sant är att den spelteoretiskt optimala strategin är bättre eller lika bra som alla andra strategier när den ställs mot sin systerstrategi. Det finns med största sannolikhet suboptimala strategier som klarar sig lika bra mot den optimala strategin, men problemet med dem är att iom deras avsteg från det optimala så öppnar de upp för att exploateras.

[KimHartman]

Bra sammanfattning!

[heltok]

spelat optimalt behöver inte vara lönsammast i alla lägen.

 

det är dock hyfsat sannolikt att en optimal spelstil skulle ha sjuk edge mot samtliga spelare i dagsläget. +10PTBB/100händer på samtliga NLT 6maxbord på nätet nu är inte alls orimligt. så långt från en lösning är vi idagsläget.

[Klyka]

spelat optimalt behöver inte vara lönsammast i alla lägen.

 

Precis, iom att alla ens motståndare spelar så pass långt ifrån den optimala strategin, så finns det massor av saker att exploatera i deras spelstil. Den optimala strategin missar det extra värde som man kan få genom att exploatera dem.

 

Annorlunda uttryckt: Genom att motståndarna avviker från optimal strategi så får du positivt EV om du spelar optimal strategi. Genom att själv "följa efter" och exploatera de misstag motståndarna gör så kan du öka detta extra värde ännu mer.

 

Detta sker dock till priset av att du själv helt plötsligt blir exploaterbar.

 

Fake edit: Heltok, detta svar är egentligen inte riktat till dig, iom att jag vet att du redan kan det här.

 

Bra sammanfattning!

 

Ty!

[KimHartman]

Drar upp denna igen:

 

http://www.cs.ualberta.ca/~darse/Papers/billings-phd.pdf

 

från s. 111

 

In a simple game like RoShamBo (also known as Rock-Paper-Scissors), playing

the equilibrium strategy ensures a break-even result, regardless of what the opponent

does, and is therefore insufcient to defeat weak opponents, or to win a tournament

([2, 1]). Poker is more complex, and in theory an equilibrium player can

win, but only if the opponent makes dominated errors. Any time a player makes

any choice that is part of a randomized mixed strategy of any game-theoretic equilibrium

policy, that decision is not dominated. In other words, it is possible to play

in a highly sub-optimal manner, but still break even against an equilibrium player,

because those choices are not strictly dominated.

Since the pseudo-optimal strategies do no opponent modeling, there is no guarantee

that they will be especially effective against very bad or highly predictable

players. They must rely only on these fundamental strategic errors, and the margin

of victory might be relatively modest as a result.

The critical question is whether such errors are common in practice. There is no

denitive answer to this question yet, but preliminary evidence suggests that dominated

errors occur often enough to gain a measurable EV advantage over weaker

players, but may not be very common in the play of very good players.

[Klyka]

Vet inte riktigt hur säker den uppgiften är, men har för mig att det anses att optimal pokerstrategi inte innehåller så många mixade beslutspunkter, alltså att det ofta är ett beslut som är det rätta och alla andra är dominerade. Isf plockar den optimala strategin värde från varje avvikelse motspelaren gör från den optimala strategin.

 

Om jag har fel i detta så är ovanstående citat av större intresse. Notera dock att resonemanget i citatet ovan bara visar på att optimal strategi isf inte plockar värde av alla avsteg från optimal strategi. Den är fortfarande oexploaterbar och har minst EV +/0. Och som sagt, så fort fi fattar ett dominerat beslut så plockar vår optimala strategi värde från detta.

[KimHartman]

Vet inte riktigt hur säker den uppgiften är, men har för mig att det anses att optimal pokerstrategi inte innehåller så många mixade beslutspunkter, alltså att det ofta är ett beslut som är det rätta och alla andra är dominerade. Isf plockar den optimala strategin värde från varje avvikelse motspelaren gör från den optimala strategin.

 

Om jag har fel i detta så är ovanstående citat av större intresse. Notera dock att resonemanget i citatet ovan bara visar på att optimal strategi isf inte plockar värde av alla avsteg från optimal strategi. Den är fortfarande oexploaterbar och har minst EV +/0. Och som sagt, så fort fi fattar ett dominerat beslut så plockar vår optimala strategi värde från detta.

 

 

Absolut, men optimal strategi innehåller mixade/randomiserade beslut (eftersom poker är ett spel utan fullständig information). Det går att hitta på enkla fall där tex ett uppenbart drag sitter eller inte sitter på river, som kräver en mixad strategi för att inte släppa info. Just på grund av att den optimala strategin, eller en av de optimala strategierna, är mixad(e) kan en bra spelare unvika många dominerade fel.

[Klyka]

Absolut, men optimal strategi innehåller mixade/randomiserade beslut (eftersom poker är ett spel utan fullständig information). Det går att hitta på enkla fall där tex ett uppenbart drag sitter eller inte sitter på river, som kräver en mixad strategi för att inte släppa info. Just på grund av att den optimala strategin, eller en av de optimala strategierna, är mixad(e) kan en bra spelare unvika många dominerade fel.

 

Jag tror att detta gäller när din HD är väldigt snäv eller av annan anledning väldefinerad. När den består av många händer med olika styrka så liknar det mer ett [0,1]-spel där man har rena strategier i olika hand-intervaller. I dessa fall är det bara cutoff-händerna som spelas med mixade strategier.

 

Tror jag.

 

Visst förnekar jag inte att det förekommer mixade strategier (bland annat för dessa cutoff-händer), men jag tror de är i minoritet, och att det således är fler beslutspunkter där det finns dominerade alternativ än inte.

[Klyka]

Och sen vettefan om jag e galet ute, men det känns som den citerade texten gör gällande att så länge du väljer ett beslut som ingår i en mixad optimal strategi så tappar du inget värde. Sett till den enskilda handen är det ju ok, men om du i det långa loppet gör saker, som inte i sig är dominerade, med fel frekvens så tappar du ju värde mot en optimal strategi.

 

Tex är syn inte ett dominerat alternativ när fi antingen bluffar eller bettar stålet, men om du alltid synar så är du illa ute mot en balanserad strategi.

[FordPrefect]

Är du en pokerkändis i Uppsala Klyka? =)

[KimHartman]

Jag tror att detta gäller när din HD är väldigt snäv eller av annan anledning väldefinerad. När den består av många händer med olika styrka så liknar det mer ett [0,1]-spel där man har rena strategier i olika hand-intervaller. I dessa fall är det bara cutoff-händerna som spelas med mixade strategier.

 

Tror jag.

 

Visst förnekar jag inte att det förekommer mixade strategier (bland annat för dessa cutoff-händer), men jag tror de är i minoritet, och att det således är fler beslutspunkter där det finns dominerade alternativ än inte.

 

Jag är osäker på hur många beslut som är "rena" och hur många som är mixade, och det beror säkert på vilken form av poker man spelar. THFL FR eller extrem shortstack har säkert mindre andel mixade jämfört med djupstackad THNL (jag gissar bara). Hursomhelst påpekar författarna att på flera ställen att just mixade strategier är nödvändigt mot vad de kallar "advanced players" och när det granskar spelet mellan sina botar och duktiga människor är det tydligen just där det brister. Bottarna spelar fö THFL HU. Helt säkert är iaf att folk kommer begå misstag förr eller senare, "human master" eller inte..

[KimHartman]

Och sen vettefan om jag e galet ute, men det känns som den citerade texten gör gällande att så länge du väljer ett beslut som ingår i en mixad optimal strategi så tappar du inget värde. Sett till den enskilda handen är det ju ok, men om du i det långa loppet gör saker, som inte i sig är dominerade, med fel frekvens så tappar du ju värde mot en optimal strategi.

 

Tex är syn inte ett dominerat alternativ när fi antingen bluffar eller bettar stålet, men om du alltid synar så är du illa ute mot en balanserad strategi.

 

Tål definitivt att tänkas på. Jag köper att felet inte är lika allvarligt. Men som du säger, det står ju i pincip att man inte gör fel alls, vilket verkar märkligt.

[KimHartman]

Tål definitivt att tänkas på. Jag köper att felet inte är lika allvarligt. Men som du säger, det står ju i pincip att man inte gör fel alls, vilket verkar märkligt.

 

Eller så är det kanske logiskt. "Mixandet" är ju till för att dölja information, för att göra det omjöligt för sin motståndare att hitta ett alternativ som är bättre än något annat. Med en datormotståndare som ändå inte gör nån "opponent modeling" spelar det ju ändå ingen roll om man själv är förutsägbar.

[Klyka]

Eller så är det kanske logiskt. "Mixandet" är ju till för att dölja information, för att göra det omjöligt för sin motståndare att hitta ett alternativ som är bättre än något annat. Med en datormotståndare som ändå inte gör nån "opponent modeling" spelar det ju ändå ingen roll om man själv är förutsägbar.

 

Jo, du måste ju ändå mixa upp det hela även om du spelar mot en strategi som inte tar hänsyn till hur du spelar. Optimal strategi, tex, har ju inget utrymme för "opponent modeling", men du är ju ändå hajmat för den optimala strategin om du inte balanserar dina handlingar på ett bra sätt.

 

Visst, du blir inte ytterligare exploaterad av en spelare som inte gör "opponent modeling" (vilket ju bara är ett annat uttryck för exploativt spel - eller snarare den tankeprocess som föregår en exploativ justering av en strategi), men du ger fortfarande värde till honom.

[heltok]

eftersom antalet pokerhänder är ändligt så bör randomisering krävas om inte för att inte få avrundsningsfel.

[Ignatius]

Har läst en del spelteori.

 

"Optimal strategi" är inte helt väldefinierat, men ofta används det väl här på forumet som Klyka beskriver. Väldefinierade begrepp är:

 

"Best response": Bästa beslut givet motståndarens beslut.

 

"Nash equilibrium": En strategikombination sådan att ingen spelare tjänar på att avvika från sin strategi, givet de andras strategier. Kallas kanske bäst jämviktsstrategi i "normala" diskussioner.

[KimHartman]

Jo, du måste ju ändå mixa upp det hela även om du spelar mot en strategi som inte tar hänsyn till hur du spelar. Optimal strategi, tex, har ju inget utrymme för "opponent modeling", men du är ju ändå hajmat för den optimala strategin om du inte balanserar dina handlingar på ett bra sätt.

 

Visst, du blir inte ytterligare exploaterad av en spelare som inte gör "opponent modeling" (vilket ju bara är ett annat uttryck för exploativt spel - eller snarare den tankeprocess som föregår en exploativ justering av en strategi), men du ger fortfarande värde till honom.

 

Jag måste helt enkelt fundera på detta..

[KimHartman]

Jag måste helt enkelt fundera på detta..

 

Hitta ett paper till som håller med det första:

 

http://www.dudziak.com/dudziak-fictitious_play.pdf

 

Tyvärr är det inte så mycket "kött" på argumentationen, men det verkar tydligen som om det är stämmer. Notera att ref [2] är till den fösta avhandlingen.

 

från sid 2:

 

The key disadvantage of playing an optimal strategy is that the optimal play only accrues an advantage over opponents only when opponents make dominated errors. For example: if there are three choices facing a human player at a given decision node, and the optimal strategy states to play choice A 20% of the time, choice B 0% of the time, and choice C 80% of the time; if the human player were to choose action B, then that would be a dominated mistake, and the optimal opponent would gain an advantage. However, if the opponent were to choose A or C at any frequency (0%-100% of the time), this is a strategic error known as a non-dominated error; though this strategy may be suboptimal, an optimal player will be unable to gain any advantage from this behavior.

An Example to Illustrate the Properties of Nash Equilibria and Dominated/Non-Dominated Error:

The game Rock-Paper-Scissors (paper beats rock, rock beats scissors, scissors beats paper), has a remarkably simple optimal solution: play rock with 1/3 probability, paper with 1/3 probability, and scissors with 1/3 probability.

Using Rock-Paper-Scissors, it should be apparent that a strategy of ‘always play rock’, is not a preferred solution. However, if playing against an optimal opponent, the strategy will not incur any penalties since the player will continue to win 1/3 of the time, lose 1/3 and tie 1/3. This is an illustration of non-dominated error. The player is not playing by the rules of the optimal solution, however since the optimal solution involves non-zero probabilities of playing rock/paper/scissors, any strategy involving those elements will not sustain any penalty when playing against an optimal opponent.

A fourth element can be added to this game to demonstrate dominated error. We can call the game Rock-Paper-Scissors-Dynamite (the only change to the rules is that dynamite beats rock, and is beaten by paper or scissors). The optimal strategy given these rules is: play rock with 1/3 probability, paper with 1/3 probability, scissors with 1/3 probability, and dynamite with 0 probability. If playing against an optimal opponent and the decision is made to play dynamite, this incurs a dominated error, and the projected winnings from the game will decrease as result.

After this example, it seems that playing dominated errors should be a rare occurrence in games, since the decision seems so clear cut. However, testing has shown that in complicated games, especially games of imperfect information, dominated errors occur often enough (even among pseudo-optimal players), that if played over the long-term, weaknesses in strategy are evident [2].

[Klyka]

Ok, tror jag har förklaringen till vad de menar.. Satt o försökte räkna på ett exempel med optimal bluffrekvens för o se vad som händer när fi övergår till en strategi där han väljer ett av två eller flera icke dominerade alternativ 100% av gångerna i stället för att spela efter en viktad strategi. Men rätt vad det var så slog det mig:

 

Vad den optimala strategin gör är ju att se till att fi är likgiltig (indifferent) mellan två eller flera odominerade alternativ. Att han är likgiltig innebär att han har exakt samma EV oavsett vad han väljer. Exempelvis bluffar vi optimalt när han har samma EV på en syn som han har på en fold (dvs EV 0).

 

Alltså, när vi spelar optimalt så har han samma EV oavsett vilket av två odominerade alternativ han väljer. Detta även om han alltid väljer samma alternativ i ett visst läge, dvs precis som författarna säger.

 

Men varför ska fi isf öht bekymmra sig över att vikta sin motstrategi? Jo, detta gör ju han för att göra OSS likgiltiga inför att bluffa eller inte, dvs det är ett led i HANS strävan att vara oexploaterbar. Men detta är tämligen ointressant för honom att göra mot en motståndare som inte anpassar sig efter att han alltid väljer samma alternativ (dvs en motståndare som inte sysslar med "opponent modeling").

 

Edit: Men sten sax o påse känns spontant som ett sjukt dåligt exempel...

[KimHartman]

Ok, tror jag har förklaringen till vad de menar.. Satt o försökte räkna på ett exempel med optimal bluffrekvens för o se vad som händer när fi övergår till en strategi där han väljer ett av två eller flera icke dominerade alternativ 100% av gångerna i stället för att spela efter en viktad strategi. Men rätt vad det var så slog det mig:

 

Vad den optimala strategin gör är ju att se till att fi är likgiltig (indifferent) mellan två eller flera odominerade alternativ. Att han är likgiltig innebär att han har exakt samma EV oavsett vad han väljer. Exempelvis bluffar vi optimalt när han har samma EV på en syn som han har på en fold (dvs EV 0).

 

Alltså, när vi spelar optimalt så har han samma EV oavsett vilket av två odominerade alternativ han väljer. Detta även om han alltid väljer samma alternativ i ett visst läge, dvs precis som författarna säger.

 

Men varför ska fi isf öht bekymmra sig över att vikta sin motstrategi? Jo, detta gör ju han för att göra OSS likgiltiga inför att bluffa eller inte, dvs det är ett led i HANS strävan att vara oexploaterbar. Men detta är tämligen ointressant för honom att göra mot en motståndare som inte anpassar sig efter att han alltid väljer samma alternativ (dvs en motståndare som inte sysslar med "opponent modeling").

 

Edit: Men sten sax o påse känns spontant som ett sjukt dåligt exempel...

 

 

Ungefär så som jag tänkte. Han strategi är ju framtagen under förutsättningen att vi spelar med optimala frekvenser. Om vi struntar i att göra det riskerar vi inget eftersom han vägrar att frångå sin stil.

[KimHartman]

En annan intressant grej är att fundera över hur mixade strategier kan se ut i NL. Det känns ju spontant som om man kan "träffa rätt" ganska ofta om sånna strategier inte är diskreta.

[Klyka]

En annan intressant grej är att fundera över hur mixade strategier kan se ut i NL. Det känns ju spontant som om man kan "träffa rätt" ganska ofta om sånna strategier inte är diskreta.

 

Det där får du nog utveckla en smula...

[KimHartman]

Det där får du nog utveckla en smula...

 

I NL har man ju ofta oändligt många möjligheter. Om en bet på $10 ingår i en eq-strat., är det svårt att tänka sig att en bet på $10.1 inte gör det, osv. Så om det existerar mixade NL-strategier, bör dom ju innehålla nån sannolikhetsfördelning som man använder för att välja bet sizes. Om det finns stora intervall där sannolihetstäthetsfunktionen > 0, bör man ju kunna komma undan billigt i många fall som människa mot en eq.-strat.

[Klyka]

I NL har man ju ofta oändligt många möjligheter. Om en bet på $10 ingår i en eq-strat., är det svårt att tänka sig att en bet på $10.1 inte gör det, osv. Så om det existerar mixade NL-strategier, bör dom ju innehålla nån sannolikhetsfördelning som man använder för att välja bet sizes. Om det finns stora intervall där sannolihetstäthetsfunktionen > 0, bör man ju kunna komma undan billigt i många fall som människa mot en eq.-strat.

 

Ok nu är jag med, även om jag inte förstår det fetmarkerade ordet.

 

Sjukt intressant tanke! Intuitivt känns det fel att det skulle kunna vara så, men visst, i linje med de ovanstående resonemangen, så kanske...

 

Hur som helst så fick jag en tanke presenterad för mig på annat forum (vet inte om dess upphovsman motsätter sig name dropping så jag avstår). Kanske man inte ska se till varje beslutspunkt i sig, utan till de olika linjer som man kan använda sig av istället. Tex:

 

Istället för att se det som att pre flop kan vi folda, syna eller höja, varav bara ett alternativ är dominerat, och på floppen har vi samma alternativ, varav bara ett är dominerat, etc (ett synsätt som gör det rätt lätt att välja odominerade alternativ genom hela handen) så ska vi se det som att vi i början av handen har ett val mellan en stor uppsättning linjer. Tex:

 

Linje 1: Raisa pre flop och cappa om möjligt, om fi bara synat vår raise pre flop och inget A faller på floppen så bettar vi ut floppen och re-raisar vid eventuell raise, synar eventuell cap. Vid cap på floppen så check-synar vi ned hela vägen. Om potten blir cappad pre flop bettar vi ut alla floppar och trebettar vid raise men foldar för cap. Om pre cappas och han bara synar [också vidare, dvs en hel strategi för hur handen ska spelas genom alla möjliga förgreningar i spelträdet].

 

Linje 2: Limpa pre flop, re-raisa om blir raisad, syna eventuell cap. När floppen kommer så [också vidare...]

 

Linje 3: [...]

 

Linje 4: [...]

 

Linje n: [...]

 

Dvs vi har en sjuk massa linjer att välja mellan. Nu är det svårare att se hur vi ska kunna välja en odominerad linje särskilt många gånger, och nu får vi det svårare mot en optimal strategi om vi inte själva spelar optimalt.

 

Frågan är bara vilket synsätt som är det rätta.

[KimHartman]

Ok nu är jag med, även om jag inte förstår det fetmarkerade ordet.

 

Sjukt intressant tanke! Intuitivt känns det fel att det skulle kunna vara så, men visst, i linje med de ovanstående resonemangen, så kanske...

 

Hur som helst så fick jag en tanke presenterad för mig på annat forum (vet inte om dess upphovsman motsätter sig name dropping så jag avstår). Kanske man inte ska se till varje beslutspunkt i sig, utan till de olika linjer som man kan använda sig av istället. Tex:

 

Istället för att se det som att pre flop kan vi folda, syna eller höja, varav bara ett alternativ är dominerat, och på floppen har vi samma alternativ, varav bara ett är dominerat, etc (ett synsätt som gör det rätt lätt att välja odominerade alternativ genom hela handen) så ska vi se det som att vi i början av handen har ett val mellan en stor uppsättning linjer. Tex:

 

Linje 1: Raisa pre flop och cappa om möjligt, om fi bara synat vår raise pre flop och inget A faller på floppen så bettar vi ut floppen och re-raisar vid eventuell raise, synar eventuell cap. Vid cap på floppen så check-synar vi ned hela vägen. Om potten blir cappad pre flop bettar vi ut alla floppar och trebettar vid raise men foldar för cap. Om pre cappas och han bara synar [också vidare, dvs en hel strategi för hur handen ska spelas genom alla möjliga förgreningar i spelträdet].

 

Linje 2: Limpa pre flop, re-raisa om blir raisad, syna eventuell cap. När floppen kommer så [också vidare...]

 

Linje 3: [...]

 

Linje 4: [...]

 

Linje n: [...]

 

Dvs vi har en sjuk massa linjer att välja mellan. Nu är det svårare att se hur vi ska kunna välja en odominerad linje särskilt många gånger, och nu får vi det svårare mot en optimal strategi om vi inte själva spelar optimalt.

 

Frågan är bara vilket synsätt som är det rätta.

 

 

Helt klart är det så man ska se det. Det är ju den typen av resonemang som "bakåtspolat" leder till vad som är optimalt preflop. Det är såklart också sant att ju fler beslut man ställs för i en hand, dessto större chans är det att man gör ett dominerat val. Jag kan tänka mej att "bra spelare" som ställs inför ett val som har "mixade lösningar" har en bra känsla för att välja den den av trädet som i fortsättningen av handen minskar risken för att begå dominerade val.