All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Combining Incremental Strategy Generation and Branch and Bound Search for Computing Maxmin Strategies in Imperfect Recall Games

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00315397" target="_blank" >RIV/68407700:21230/17:00315397 - isvavai.cz</a>

  • Result on the web

    <a href="https://www.researchgate.net/publication/317095657_Combining_incremental_strategy_generation_and_branch_and_bound_search_for_computing_maxmin_strategies_in_imperfect_recall_games" target="_blank" >https://www.researchgate.net/publication/317095657_Combining_incremental_strategy_generation_and_branch_and_bound_search_for_computing_maxmin_strategies_in_imperfect_recall_games</a>

  • DOI - Digital Object Identifier

Alternative languages

  • Result language

    angličtina

  • Original language name

    Combining Incremental Strategy Generation and Branch and Bound Search for Computing Maxmin Strategies in Imperfect Recall Games

  • Original language description

    Extensive-form games with imperfect recall are an important model of dynamic games where the players are allowed to forget previously known information. Often, imperfect recall games are the result of an abstraction algorithm that simplifies a large game with perfect recall. Unfortunately, solving an imperfect recall game has fundamental problems since a Nash equilibrium does not have to exist. Alternatively, we can seek maxmin strategies that guarantee an expected outcome. The only existing algorithm computing maxmin strategies in two-player imperfect recall games without absentmindedness, however, requires approximating a bilinear mathematical program that is proportional to the size of the whole game and thus has a limited scalability. We propose a novel algorithm for computing maxmin strategies in this class of games that combines this approximate algorithm with an incremental strategy-generation technique designed previously for extensive-form games with perfect recall. Experimental evaluation shows that the novel algorithm builds only a fraction of the game tree and improves the scalability by several orders of magnitude. Finally, we demonstrate that our algorithm can solve an abstracted variant of a large game faster compared to the algorithms operating on the unabstracted perfect-recall variant.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

    <a href="/en/project/GA15-23235S" target="_blank" >GA15-23235S: Abstractions and Extensive-Form Games with Imperfect Recall</a><br>

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2017

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    Proceedings of the 31th AAAI Conference on Artificial Intelligence

  • ISBN

    978-1-57735-786-5

  • ISSN

  • e-ISSN

  • Number of pages

    9

  • Pages from-to

    902-910

  • Publisher name

    AAAI Press

  • Place of publication

    Menlo Park

  • Event location

    San Francisco

  • Event date

    Feb 4, 2017

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article