Proceedings

Modeling Precomputation In Games Played Under Computational Constraints

Thomas Orton

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 2005-2011.

https://doi.org/10.24963/ijcai.2021/276

Keywords

  • Agent-based and Multi-agent Systems: Resource Allocation
  • Knowledge Representation and Reasoning: Computational Complexity of Reasoning
  • Heuristic Search and Game Playing: Meta-Reasoning and Meta-Heuristics

Abstract

Understanding the properties of games played under computational constraints remains challenging. For example, how do we expect rational (but computationally bounded) players to play games with a prohibitively large number of states, such as chess? This paper presents a novel model for the precomputation (preparing moves in advance) aspect of computationally constrained games. A fundamental trade-off is shown between randomness of play, and susceptibility to precomputation, suggesting that randomization is necessary in games with computational constraints. We present efficient algorithms for computing how susceptible a strategy is to precomputation, and computing an $\epsilon$-Nash equilibrium of our model. Numerical experiments measuring the trade-off between randomness and precomputation are provided for Stockfish (a well-known chess playing algorithm).

Thomas Orton. 2021. Modeling Precomputation In Games Played Under Computational Constraints. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 2005–2011. https://doi.org/10.24963/ijcai.2021/276
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards