About: Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://aaai.org/ocs/index.php/WS/AAAIW14/paper/view/8820/8353
Description	Online search in games has always been a core interest of artificial intelligence. Advances made in search for perfect information games (such as Chess, Checkers, Go, and Backgammon) have led to AI capable of defeating the world's top human experts. Search in imperfect information games (such as Poker, Bridge, and Skat) is significantly more challenging due to the complexities introduced by hidden information. In this paper, we present Online Outcome Sampling (OOS), the first imperfect information search algorithm that is guaranteed to converge to an equilibrium strategy in two-player zero-sum games. We show that OOS avoids common problems encountered by existing search algorithms and we experimentally evaluate its convergence rate and practical performance against benchmark strategies in Liar's Dice and a variant of Goofspiel. We show that unlike with Information Set Monte Carlo Tree Search (ISMCTS) the exploitability of the strategies produced by OOS decreases as the amount of search time increases. In practice, OOS performs as well as ISMCTS in head-to-head play while producing strategies with lower exploitability given the same search time. Online search in games has always been a core interest of artificial intelligence. Advances made in search for perfect information games (such as Chess, Checkers, Go, and Backgammon) have led to AI capable of defeating the world's top human experts. Search in imperfect information games (such as Poker, Bridge, and Skat) is significantly more challenging due to the complexities introduced by hidden information. In this paper, we present Online Outcome Sampling (OOS), the first imperfect information search algorithm that is guaranteed to converge to an equilibrium strategy in two-player zero-sum games. We show that OOS avoids common problems encountered by existing search algorithms and we experimentally evaluate its convergence rate and practical performance against benchmark strategies in Liar's Dice and a variant of Goofspiel. We show that unlike with Information Set Monte Carlo Tree Search (ISMCTS) the exploitability of the strategies produced by OOS decreases as the amount of search time increases. In practice, OOS performs as well as ISMCTS in head-to-head play while producing strategies with lower exploitability given the same search time. (en)
Title	Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization (en)
skos:prefLabel	Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization Search in Imperfect Information Games Using Online Monte Carlo Counterfactual Regret Minimization (en)
skos:notation	RIV/68407700:21230/14:00225029!RIV15-GA0-21230___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GAP202/12/2054)
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Lisý, Viliam
http://linked.open.../riv/druhVysledku	O - Ostatní výsledky nezařaditelné do žádného z výše uvedených druhů výsledku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	České vysoké učení technické v Praze / Fakulta elektrotechnická
http://linked.open...dnocenehoVysledku	44087
http://linked.open...ai/riv/idVysledku	RIV/68407700:21230/14:00225029
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Monte Carlo Tree Search; imperfect information game; convergence (en)
http://linked.open.../riv/klicoveSlovo	Monte Carlo Tree Search convergence imperfect information game
http://linked.open...ontrolniKodProRIV	[4358D519C5CC]
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Bezpečnostní hry v extenzivní formě
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Lisý, Viliam Lanctot, M. Bowling, M.
http://localhost/t...ganizacniJednotka	21230

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software