Playing imperfect information games with information sets requires agents to find the current information set in the game tree and sample from the possible states. Conventional backtracking struggles to efficiently handle observed information. In the worst case, backtracking requires enumerating all histories. To efficiently solve computing information sets, we leveraged answer set programming (ASP). This work presents an efficient encoding method for computing information sets. The method is explained, demonstrated, and benchmarked on game description language with imperfect information (GDL-II) examples. The encoding performs efficiently in benchmarks. Depending on the game, our method achieved up to four orders of magnitude improvement for generated histories (within a fixed time limit) compared to the depth-first search (DFS) baseline. Furthermore, its declarative nature simplifies reasoning compared to procedural approaches. As a consequence, the encoding holds promise for autonomous game playing. Additionally, demonstrating the broader applicability of ASP. Generalizing the method beyond GDL-II remains the focus of future work. Moreover, we will explore further extensions and optimizations.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Leveraging Answer Set Programming for Information Set Computation in Imperfect Information Games

  • Lukas Grassauer

摘要

Playing imperfect information games with information sets requires agents to find the current information set in the game tree and sample from the possible states. Conventional backtracking struggles to efficiently handle observed information. In the worst case, backtracking requires enumerating all histories. To efficiently solve computing information sets, we leveraged answer set programming (ASP). This work presents an efficient encoding method for computing information sets. The method is explained, demonstrated, and benchmarked on game description language with imperfect information (GDL-II) examples. The encoding performs efficiently in benchmarks. Depending on the game, our method achieved up to four orders of magnitude improvement for generated histories (within a fixed time limit) compared to the depth-first search (DFS) baseline. Furthermore, its declarative nature simplifies reasoning compared to procedural approaches. As a consequence, the encoding holds promise for autonomous game playing. Additionally, demonstrating the broader applicability of ASP. Generalizing the method beyond GDL-II remains the focus of future work. Moreover, we will explore further extensions and optimizations.