Deep Reinforcement Learning for International Diplomacy: Learning to Play Map Variants
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3089605Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Sammendrag
Brettspillet Diplomacy har fått mye oppmerksomhet de siste årene som en problemstilling for kunstig intelligens. Diplomacy har et enormt kombinatorisk aksjonsrom, en miks av samarbeid og konkurranse, forhandlinger i naturlig språk, deterministiske regler, og simultane aksjonsvalg. Disse egenskapene ugjør en interessant utfordring for forskning innen kunstig intelligens. Noen av egenskapene er også delt med utfordringer i det virkelige liv, som forhandling, taktikk, og samarbeid.
Nylig forskning innen kunstig intelligens for Diplomacy har benyttet dyp forsterkningslæring med "(generalized) policy iteration", ikke ulikt AlphaGo Zero fra Silver et al. [46]. "State-of-the-art" teknikker har oppnådd suksess i den originale formuleringen av det klassiske spillet. Suksessen vekker en interesse rundt hvorvidt teknikkene er nyttige i andre problemstillinger.
Populariten og det lange leveløpet til spillet har gitt oppspring til varianter av det klassiske spillet. Spillvariantene endrer regler, kart-topologi, og antall spillere for å skape nye utfordringer for spilleren. Som et steg mot generell anvendelighet av "state-of-the-art" teknikker, utforsker denne masteroppgaven deres anvendelse på varianter av det klassiske spillet.
Inspirert av "state-of-the-art" skapes en agent som i hver runde gjør et spillteoretisk søk over et subset av felles aksjonsrom med payoff definert via poeng-estimat av spilltilstander i følgende runde gitt av et nevralnett. Subsettet av aksjoner genereres av et nevralnett som dekomponerer aksjonsrommet som et sekvensielt valg av sub-aksjoner. Over tid forbedres kvaliteten i poeng-estimatene via "bootstrapping", og kvaliteten på subsettet av aksjoner ved å gjøre aksjoner regnet som gode av spillteoretisk søk mer sannsynlige for inkludering i subsettet i fremtiden. Nevralnettene trenes fra grunnen av uten hjelp av menneskelig data, og en "action exploration"-prosedyre hjelper med å oppdage fornuftige aksjoner.
Agenter trenes via self-spill på tre ikke-kommunikative (No-Press) Diplomacy kartvarianter, og blir evaluert via ferdighet i turneringer med referanseagenter. Arbeidet viser at "state-of-the-art" teknikker innen dyp forsterkningslæring som har oppnådd suksess på det klassiske Diplomacy-kartet kan anvendes med gode resultater på alternative kart-topologier. Dette resultatet hinter til den generelle anvendeligheten av teknikkene og utgjør et steg mot deres anvendelse i utfordringer fra det virkelige liv. The board game Diplomacy has received much attention in recent years as a benchmark problem for the field of artificial intelligence. Diplomacy features a massive combinatorial action space, a mix of cooperation and competition, negotiation in natural language, a deterministic ruleset, and simultaneous action selection. These traits pose a novel challenge to artificial intelligence research, and some are shared with real-life issues like negotiation, tactics, and coordination.
Recent research in artificial intelligence for Diplomacy has utilized deep reinforcement learning with (generalized) policy iteration, similar to AlphaGo Zero of Silver et al. [46]. State-of-the-art techniques have achieved success in the original formulation of the classic game. The success raises interest as to whether the techniques generalize to other problems.
The long lifespan and popularity of the game has spawned a culture of creating variants of the classic game. Game variants modify the ruleset, map topology, and player count to create new challenges for the player. As a step towards general applicability of state-of-the-art techniques, this thesis investigates their application in variants of the classic game.
Inspired by state-of-the-art, an agent is implemented that at each turn performs game-theoretic search over a subset of the joint action space, with payoff given by next-state end-game score prediction from a neural network. Action subsets are generated by a neural network that decomposes the action space as a sequential selection of sub-actions. Over time, the accuracy of end-game score prediction is improved via bootstrapped score estimates, and the quality of the generated action subset is improved by making actions valued by search more likely for inclusion in the future. The neural networks train from scratch with no human data, and an action exploration procedure helps discover reasonable actions.
Agents are trained through self-play on three non-communicative (No-Press) Diplomacy map variants, and evaluated through skill in tournaments with baseline opponent agents. The work shows that state-of-the-art deep reinforcement learning techniques that have seen success on the classic Diplomacy map can be applied successfully in alternative map topologies, which hints at the generality of the techniques and acts as a step toward their application in real-life issues.