Artificiell intelligens har sett flera genombrott under de senaste åren, med spel som ofta tjänar som milstolpar. Ett gemensamt drag i dessa spel är att spelarna har perfekt information. Poker, det väsentliga spelet av ofullständig information, är en långvarig utmaning problem inom artificiell intelligens. Vi introducerar DeepStack, en algoritm för bristfälliga informationsinställningar. Den kombinerar rekursivt resonemang för att hantera informationsasymmetri, nedbrytning för att fokusera beräkningen på det relevanta beslutet, och en form av intuition som automatiskt lärs från självspel med hjälp av djupt lärande. I en studie med 44,000 händer poker, DeepStack besegrade, med statistisk betydelse, professionella pokerspelare i heads-up no-limit Texas hold'em. Tillvägagångssättet är teoretiskt sunt och visar sig producera strategier som är svårare att utnyttja än tidigare tillvägagångssätt. G ames har länge fungerat som riktmärken för framsteg inom artificiell intelligens (AI). Under de senaste två decennierna har datorprogram nått en prestanda som är högre än den som expertspelarna i partier som backgammon (1), pjäser (2), schack (3), Jeopardy! (4), Atari videospel (5), och gå (6). Dessa framgångar omfattar alla spel med informationssymmetri, där alla spelare har identisk information om det aktuella läget i spelet. Denna egenskap perfekt information är också i hjärtat av de algoritmer som aktiverade dessa framgångar, såsom lokal sökning under spel (7, 8). John von Neumann, grundare av modern spelteori och datapionjär, föreställde sig resonemang i spel utan perfekt information: " Det verkliga livet är inte så. Verkligt liv består av bluff, av lite bedrägeritaktik, av att fråga dig själv vad den andra mannen tror att jag tänker göra. Och det är vad spel handlar om i min teori" (9). Ett spel som fascinerade von Neumann var poker, där spelare delas ut privata kort och turas om att göra satsningar eller bluffa på att hålla den starkaste handen, ringa motståndarens satsningar, eller vika och ge upp på handen och de satsningar som redan lagts till potten. Poker är ett spel av ofullständig information, där spelarnas privata kort ger dem asymmetrisk information om läget i spelet. Heads-up no-limit Texas hold'em (HUNL) är en två-spelare version av poker där två kort först delas ut nedåt till varje spelare, och ytterligare kort delas ut face up i tre efterföljande rundor. Ingen gräns sätts på storleken på spelen, även om det finns en total gräns för det totala satsade beloppet i varje spel (10). AI-tekniker har tidigare visat framgång i det enklare spelet heads-up limit Texas hold'em, där alla satsningar är av en fast storlek, vilket resulterar i strax under 10 14 beslutspunkter (11). Som jämförelse, datorer har överskridit expert mänskliga prestanda i go (6), en perfekt information spel med cirka 10 170 beslutspunkter (12). Det bristfälliga informationsspelet HUNL är jämförbart i storlek och antalet beslutspunkter överstiger 10 160 (13). Ofullständig information spel kräver mer komplexa resonemang än liknande storlek perfekt information spel. Det korrekta beslutet vid en viss tidpunkt beror på sannolikheten fördelning över privat information som en motståndare innehar, vilket avslöjas genom motståndarens tidigare åtgärder. Det sätt på vilket denna information avslöjas beror dock på motståndarens kunskap om vår egen privata information och hur våra handlingar avslöjar den. Denna typ av rekursiva resonemang är varför man inte lätt kan resonera om spelsituationer i isolering, som i heuristiska sökmetoder som används i perfekt information spel. Konkurrenskraftiga AI-strategier i ofullständiga informationsspel resonerar vanligtvis om hela spelet och producerar en komplett strategi innan spelet börjar (14-16). Kontrafaktisk ångerminimering (CFR) (14, 17, 18 ) är en sådan teknik där ett program använder sig av självspel för att göra rekursiva resonemang genom att anpassa sin strategi mot sig själv över successiva iterationer. Om spelet är för stort för att lösas direkt, är det vanliga svaret att lösa ett mindre, abstrakt spel. För att spela det ursprungliga spelet, översätter man situationer och åtgärder från det ursprungliga spelet till det abstrakta spelet. Även om detta tillvägagångssätt gör det möjligt för program att resonera i ett spel som HUNL, det gör det genom att klämma HUNL 10 160 situationer ner till ordningen 10 14 abstrakta situationer. Sannolikt som ett resultat av denna förlust av information ligger sådana program bakom ett sakkunnigt mänskligt spel. Under 2015 förlorade datorprogrammet Claudico till ett team av professionella pokerspelare med en marginal på 91 milli-big blinds per match (mbb/g) (19), vilket är en "hög marginal för seger" (20). Dessutom visades det nyligen att abstraktionbaserade program från den årliga Computer Poker tävlingen har massiva brister (21). Fyra sådana program (inklusive toppprogram från 2016 tävlingen) utvärderades med hjälp av en lokal bästa svarsteknik som producerar en ungefärlig lägre gräns på hur mycket en strategi kan förlora. Alla fyra abstraktion-baserade program är beatable med mer än 3000 mbb/g, medan helt enkelt vik varje spel resulterar i 750 mbb/g. DeepStack har en helt annan inställning. Den fortsätter att använda CFR:s rekursiva resonemang för att hantera informationsasymmetri. Den beräknar dock inte och lagrar inte en fullständig strategi innan den spelas och har därför inget behov av explicit abstraktion. Den betraktar i stället varje enskild situation som den uppstår under leken, men inte isolerat. Den undviker resonemang om hela återstoden av spelet genom att ersätta beräkningen bortom ett visst djup med en snabb ungefärlig uppskattning. Denna uppskattning kan tänkas som DeepStack intuition: en magkänsla av värdet av att hålla eventuella privata kort i någon möjlig pokersituation. Slutligen måste DeepStacks intuition, ungefär som människans intuition, tränas. Vi tränar den med djupt lärande (22), med hjälp av exempel som genereras från slumpmässiga pokersituationer. Vi visar att DeepStack är teoretiskt sund, producerar strategier betydligt svårare att utnyttja än abstraktion-baserade tekniker, och besegrar professionella pokerspelare på HUNL med statistisk betydelse. DeepStack är en allmän algoritm för en stor klass av sekventiella imperfekta-informationsspel. För tydlighetens skull beskriver vi dess funktion i HUNL-spelet. Tillståndet i ett pokerspel kan delas upp i spelarnas privata informations-hands av två kort som delas ut nedåt-och det offentliga tillståndet, som består av korten som ligger ansikte upp på bordet och sekvensen av vadslagning åtgärder som görs av spelarna. Möjliga sekvenser av offentliga stater i spelet bildar ett offentligt träd, med varje offentlig stat har ett tillhörande offentligt underträd (Fig. 1).................................................................. En spelares strategi definierar en sannolikhetsfördelning över giltiga åtgärder för varje beslutspunkt, där en beslutspunkt är kombinationen av den offentliga staten och handen för den verkande spelaren. Med tanke på en spelares strategi, för varje offentlig stat kan man beräkna spelarens räckvidd, vilket är sannolikheten fördelning över spelarens möjliga händer med tanke på att den offentliga staten nås. Med tanke på strategier för båda spelarna, är nyttan för en av spelarna vid en terminal offentlig stat, där spelet har avslutats, en bilinjär funktion av båda spelarnas intervall med hjälp av en payoff matris som bestäms av reglerna i spelet. Den förväntade nyttan för en spelare i någon annan offentlig stat, inklusive den ursprungliga staten, är den förväntade nyttan över nåbar
Till exempel i Ref författare anser heads-up no-limit poker som ett exempel på ett spel med dold information.
DeepStack: Expert-level artificial intelligence in heads-up no-limit poker
{'venue': None, 'journal': 'Science', 'mag_field_of_study': ['Computer Science', 'Medicine']}