---
title: "Modeling Precomputation In Games Played Under Computational Constraints"
authors:
  - "Thomas Orton"
doi: "10.24963/ijcai.2021/276"
url: "https://ijcai.org/proceedings/2021/276"
pdf: "https://ijcai.org/proceedings/2021/0276.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "2005-2011"
track: "Main Track"
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"
---

# Modeling Precomputation In Games Played Under Computational Constraints

Thomas Orton

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 2005-2011. DOI: [10.24963/ijcai.2021/276](https://doi.org/10.24963/ijcai.2021/276)

## 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).