Att utveckla skalbara lösningsalgoritmer är ett av de centrala problemen i beräkningsteorin. Vi presenterar en iterativ algoritm för att beräkna en exakt Nash jämvikt för två spelare nollsummor omfattande-form spel med ofullständig information. Vår strategi kombinerar två nyckelelement: (1) den kompakta sekvensform representation av extensiveform spel och (2) den algoritmiska ramen för dubbel-orakel metoder. Huvudidén med vår algoritm är att begränsa spelet genom att låta spelarna spela endast utvalda sekvenser av tillgängliga åtgärder. Efter att ha löst det begränsade spelet läggs nya sekvenser till genom att hitta de bästa svaren på den nuvarande lösningen med hjälp av snabba algoritmer. Vi utvärderar vår algoritm experimentellt på en uppsättning spel inspirerade av patrulleringsscenarier, brädspel och kortspel. Resultaten visar betydande runtime förbättringar i spel som medger en jämvikt med litet stöd, och betydande förbättring av minnesanvändning även på spel med stort stöd. Förbättringen i minnesanvändning är särskilt viktig eftersom det gör det möjligt för vår algoritm att lösa mycket större spel instanser än befintliga linjära programmeringsmetoder. Våra huvudsakliga bidrag inkluderar (1) en generisk sekvens-form dubbel-orrakle algoritm för att lösa nollsumma omfattande-form spel; (2) snabba metoder för att upprätthålla en giltig begränsad spelmodell när du lägger till nya sekvenser; (3) en sökalgoritm och beskärning metoder för att beräkna bäst-respons sekvenser; (4) teoretiska garantier om konvergens av algoritmen till en Nash jämvikt; (5) experimentell analys av vår algoritm på flera spel, inklusive en ungefärlig version av algoritmen.
Slutligen utvecklar REF en iterativ dubbelorkelalgoritm för exakt jämviktsberäkning.
An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information
{'venue': 'J. Artif. Intell. Res.', 'journal': 'J. Artif. Intell. Res.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}