Combining Code Generating Large Language Models and Self-Play to Iteratively Refine Strategies in Games

1. [Allis, 1994] Louis Victor Allis. Searching for solutions in games and artificial intelligence. 1994.
2. [Alsadat and Xu, 2024] Shayan Meshkat Alsadat and Zhe Xu. Multi-agent reinforcement learning in non- cooperative stochastic games using large language models. IEEE Control Systems Letters, 2024.
3. [Angelov et al., 2021] Plamen P Angelov, Eduardo A Soares, Richard Jiang, Nicholas I Arnold, and Peter M Atkinson. Explainable artificial intelligence: an analyti- cal review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 11(5):e1424, 2021.
4. [Antoniades et al., 2024] Antonis Antoniades, Albert Örwall, Kexun Zhang, Yuxi Xie, Anirudh Goyal, and William Wang. Swe-search: Enhancing software agents with monte carlo tree search and iterative refinement. arXiv preprint arXiv:2410.20285, 2024.
5. [Aung et al., 2022] Aye Phyu Phyu Aung, Xinrun Wang, Runsheng Yu, Bo An, Senthilnath Jayavelu, and Xiaoli Li. Do-gan: A double oracle framework for generative adver- sarial networks. In Proceedings of the IEEE/CVF confer- ence on computer vision and pattern recognition, pages 11275-11284, 2022.
6. [Bachrach and Porat, 2010] Yoram Bachrach and Ely Porat. Path disruption games. In Proceedings of the 9th Interna- tional Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 1123-1130, 2010.
7. [Bachrach et al., 2012] Yoram Bachrach, Reshef Meir, Michal Feldman, and Moshe Tennenholtz. Solving coop- erative reliability games. arXiv preprint arXiv:1202.3700, 2012.
8. [Bachrach et al., 2020] Yoram Bachrach, Richard Everett, Edward Hughes, Angeliki Lazaridou, Joel Z Leibo, Marc Lanctot, Michael Johanson, Wojciech M Czarnecki, and Thore Graepel. Negotiating team formation using deep re- inforcement learning. Artificial Intelligence, 288:103356, 2020.
9. [Bowling and Veloso, 2000] Michael Bowling and Manuela Veloso. An analysis of stochastic game theory for multia- gent reinforcement learning. Citeseer, 2000.
10. [Brown, 1951] George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951.
11. [Browne et al., 2012] Cameron B Browne, Edward Pow- ley, Daniel Whitehouse, Simon M Lucas, Peter I Cowl- ing, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1-43, 2012.
12. [Campbell et al., 2002] Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep blue. Artificial intelligence, 134(1-2):57-83, 2002.
13. [Coulom, 2006] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Interna- tional conference on computers and games, pages 72-83. Springer, 2006.
14. [Fan et al., 2023] Angela Fan, Beliz Gokkaya, Mark Har- man, Mitya Lyubarskiy, Shubho Sengupta, Shin Yoo, and Jie M Zhang. Large language models for software engi- neering: Survey and open problems. In 2023 IEEE/ACM International Conference on Software Engineering: Fu- ture of Software Engineering (ICSE-FoSE), pages 31-53. IEEE, 2023.
15. [Fan et al., 2024] Caoyun Fan, Jindou Chen, Yaohui Jin, and Hao He. Can large language models serve as rational play- ers in game theory? a systematic analysis. In Proceed- ings of the AAAI Conference on Artificial Intelligence, vol- ume 38, pages 17960-17967, 2024.
16. [Gemp et al., 2024] Ian Gemp, Yoram Bachrach, Marc Lanctot, Roma Patel, Vibhavari Dasagi, Luke Marris, Georgios Piliouras, Siqi Liu, and Karl Tuyls. States as strings as strategies: Steering language models with game- theoretic solvers. arXiv preprint arXiv:2402.01704, 2024.
17. [Griffith, 1974] Arnold K Griffith. A comparison and evalua- tion of three machine learning procedures as applied to the game of checkers. Artificial Intelligence, 5(2):137-148, 1974.
18. [Guo et al., 2024] Taicheng Guo, Xiuying Chen, Yaqi Wang, Ruidi Chang, Shichao Pei, Nitesh V Chawla, Olaf Wiest, and Xiangliang Zhang. Large language model based multi-agents: A survey of progress and challenges. arXiv preprint arXiv:2402.01680, 2024. IJCAI
19. [Hernandez-Leal et al., 2019] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E Taylor. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 33(6):750-797, 2019.
20. [Hofbauer and Sandholm, 2002] Josef Hofbauer and William H Sandholm. On the global convergence of stochastic fictitious play. Econometrica, 70(6):2265- 2294, 2002.
21. [Hou et al., 2024] Xinyi Hou, Yanjie Zhao, Yue Liu, Zhou Yang, Kailong Wang, Li Li, Xiapu Luo, David Lo, John Grundy, and Haoyu Wang. Large language models for software engineering: A systematic literature review. ACM Transactions on Software Engineering and Methodology, 33(8):1-79, 2024.
22. [Huang et al., 2024] Jen-tse Huang, Eric John Li, Man Ho Lam, Tian Liang, Wenxuan Wang, Youliang Yuan, Wenx- iang Jiao, Xing Wang, Zhaopeng Tu, and Michael R Lyu. How far are we on the decision-making of llms? evaluating llms' gaming ability in multi-agent environments. arXiv preprint arXiv:2403.11807, 2024.
23. [Knauer et al., 2020] Henning Knauer, Andrea Dederichs- Koch, and Daniel Schilberg. Developing a reinforcement learning agent for the game of checkers. In Advances in Human Factors in Training, Education, and Learning Sciences: Proceedings of the AHFE 2020 Virtual Con- ference on Human Factors in Training, Education, and Learning Sciences, July 16-20, 2020, USA, pages 164- 169. Springer, 2020.
24. [Knuth and Moore, 1975] Donald E Knuth and Ronald W Moore. An analysis of alpha-beta pruning. Artificial in- telligence, 6(4):293-326, 1975.
25. [Lanctot et al., 2017] Marc Lanctot, Vinicius Zambaldi, Au- drunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game- theoretic approach to multiagent reinforcement learning. Advances in neural information processing systems, 30, 2017.
26. [Li et al., 2022] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378(6624):1092-1097, 2022.
27. [Liu et al., 2024a] Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. Is your code generated by chatgpt really correct? rigorous evaluation of large lan- guage models for code generation. Advances in Neural Information Processing Systems, 36, 2024.
28. [Liu et al., 2024b] Junwei Liu, Kaixin Wang, Yixuan Chen, Xin Peng, Zhenpeng Chen, Lingming Zhang, and Yiling Lou. Large language model-based agents for software en- gineering: A survey. arXiv preprint arXiv:2409.02977, 2024.
29. [Mańdziuk et al., 2007] Jacek Mańdziuk, Magdalena Ku- siak, and Karol Waledzik. Evolutionary-based heuristic generators for checkers and give-away checkers. Expert Systems, 24(4):189-211, 2007.
30. [Nagarajan and Sošić, 2008] Mahesh Nagarajan and Greys Sošić. Game-theoretic analysis of cooperation among sup- ply chain agents: Review and extensions. European jour- nal of operational research, 187(3):719-745, 2008.
31. [Nathani et al., 2025] Deepak Nathani, Lovish Madaan, Nicholas Roberts, Nikolay Bashlykov, Ajay Menon, Vin- cent Moens, Amar Budhiraja, Despoina Magka, Vladislav Vorotilov, Gaurav Chaurasia, et al. Mlgym: A new frame- work and benchmark for advancing ai research agents. arXiv preprint arXiv:2502.14499, 2025.
32. [Perolat et al., 2022] Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623):990-996, 2022.
33. [Schaeffer et al., 2007] Jonathan Schaeffer, Neil Burch, Yn- gvi Bjornsson, Akihiro Kishimoto, Martin Muller, Robert Lake, Paul Lu, and Steve Sutphen. Checkers is solved. science, 317(5844):1518-1522, 2007.
34. [Sidji et al., 2024] Matthew Sidji, Wally Smith, and Melissa J Rogerson. Human-ai collaboration in cooper- ative games: A study of playing codenames with an llm assistant. Proceedings of the ACM on Human-Computer Interaction, 8(CHI PLAY):1-25, 2024.
35. [Silver et al., 2018] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self- play. Science, 362(6419):1140-1144, 2018.
36. [Tambe, 2011] Milind Tambe. Security and game theory: al- gorithms, deployed systems, lessons learned. Cambridge university press, 2011.
37. [Vinyals et al., 2019] Oriol Vinyals, Igor Babuschkin, Woj- ciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in star- craft ii using multi-agent reinforcement learning. nature, 575(7782):350-354, 2019.
38. [Xia et al., 2024] Chunqiu Steven Xia, Yinlin Deng, Soren Dunn, and Lingming Zhang. Agentless: Demystifying llm-based software engineering agents. arXiv preprint arXiv:2407.01489, 2024.
39. [Yang et al., 2024] John Yang, Carlos E Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. Swe-agent: Agent-computer interfaces enable automated software engineering. arXiv preprint arXiv:2405.15793, 2024.
40. [Zhang et al., 2021] Kaiqing Zhang, Zhuoran Yang, and Tamer Bas ¸ar. Multi-agent reinforcement learning: A se- lective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384, 2021.
41. [Zhang et al., 2024a] Ruize Zhang, Zelai Xu, Chengdong Ma, Chao Yu, Wei-Wei Tu, Shiyu Huang, Deheng Ye, Wenbo Ding, Yaodong Yang, and Yu Wang. A survey on self-play methods in reinforcement learning. arXiv preprint arXiv:2408.01072, 2024.
42. [Zhang et al., 2024b] Yadong Zhang, Shaoguang Mao, Tao Ge, Xun Wang, Adrian de Wynter, Yan Xia, Wenshan Wu, Ting Song, Man Lan, and Furu Wei. Llm as a mastermind: A survey of strategic reasoning with large language mod- els. arXiv preprint arXiv:2404.01230, 2024.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Introduction

The recent innovation wave on Large Language Models (LLMs) has uncovered exciting applications, from translation to code generation [Li et al., 2022; Fan et al., 2023; Liu et al., 2024a; Hou et al., 2024]. We focus on leveraging LLM code generation for playing in multi-player games. Traditional game AI techniques have achieved remarkable successes in many games, but many computationally intensive methods such as Minimax search algorithms [Allis, 1994], Monte Carlo Tree Search (MCTS) [Browne et al., 2012], or reinforcement learning (RL) [Silver et al., 2018; Zhang et al., 2021; Perolat et al., 2022] result in game playing policies that are not interpretable [Angelov et al., 2021]. LLMs offer a transformative approach through their ability to reason about strategy and generate code.

Our contribution: We propose a method for iteratively improving game-playing strategies using LLMs within a selfplay framework guided by game theory. We use the framework of Policy Space Response Oracles (PSRO) [Lanctot et al., 2017; Zhang et al., 2024a], which iteratively adds strategies to a population by responding to the Nash equilibrium over the current strategies. Our key innovation lies in using a self-play approach that considers strategies expressed in computer code. We use an LLM to generate candidate pieces of code, and engage these bots in tournaments where they play the game one against the other. The LLM prompt asks for it to generate code for playing the game so as to maximize its win-rate against an opponent whose code is given in the prompt and reflects the current population of opponents. Thus, we use the LLM to generate increasingly more sophisticated strategies. Figure 1 shows an overview of our approach.

Although the approach is general and can be applied to any multi-player game, we demonstrate it on the game of Checkers. Checkers possesses strategic depth and requires careful planning and adaptation [Griffith, 1974; Schaeffer et al., 2007; Ma´ndziuk et al., 2007; Knauer et al., 2020], making it a challenging testbed that allows us to rigorously evaluate the effectiveness of our approach in LLM-driven gameplay.

2 Methods

We now describe our approach, using Checkers as an example. To iteratively improve gameplay, we grow a population of a bots for playing the game. Here, each bot is represented as the source code in Python for playing Checkers (based on a shared Python Checkers game engine).

Initialization We start with an initial population of bots P0 = (b1, . . . , bh). We can either use hand-crafted bots, or query the LLM to generate a bot (code) for playing the game. We then proceed in multiple rounds of generating a new bot to add to the population. Each round r begins with payoff table construction, where for the current population of bots, we play all possible pairwise match-ups (bot bi vs. bot bj). We estimate the expected score si,j of bot bi playing against bot bj by running k = 1000 games between them and taking the mean score (in Checkers, -1 for a loss, 0 for a tie, and +1 for a win). This data forms a payoff matrix P r , where entry Pi,j is the estimate for si,j. The payoff table captures the relative strengths of the bots in the current population.

Next we approximate the Nash equilibrium distribution over the bots, by taking the the payoff table and applying the fictitious play (FP) [Brown, 1951] method. FP iteratively simulates bots playing against the average strategy of their opponents. This process converges to the Nash Equilibrium distribution, which represents the optimal mixed strategy for the current population. Hence the Nash approximation takes in the payoff matrix P r and returns an optimal mixture over the current bots - a probability xri for each bot bi (where ∑i xri = 1). We use the weights xri to construct the code for the Mixture Bot br for the round. The Mixture Bot code does not employ a single fixed strategy, but rather before playing each game it samples a bot bi from the current population according to the probability distribution (xr1 , xr2 , . . . , xrd ), where d is the size of the bot population in round r; it then uses the sampled bot's strategy to decide on moves in the game. The Mixture Bot embodies the optimal mixed strategy derived from the Nash Equilibrium.

We use the Mixture Bot for generating a new bot to add to the population. We generate a new bot by prompting the LLM to examine the code of the Mixture Bot (given in the prompt), and to generate a new bot code so as to best defeat the Mixture Bot. Our LLM prompt asks the LLM to generate a best response to the current Mixture Bot, and includes the full code of the Mixture Bot (including the code for each of the sub-strategies it employs, i.e. the previous generation bots). As generating a best response bot is a challenging task, we repeat the LLM query t times, each time generating a new candidate bot, c1, . . . , ct. The win-rate of each of these against the Mixture Bot br is estimated over k = 1000 games, and the best new bot is selected and added to the population.

By applying the above process m times, we obtain m additional bots in the population (and mMixture bots). These are stronger and stronger bots, as each of these is designed to perform well against all the previous generations. Hence the LLM queries generate increasingly more effective strategies in response to the evolving mixture bot, so the process gradually improves the overall playing strength. Our full algorithm, called LLM-PSRO, is given in Algorithm 1.

Algorithm 1 LLM-PSRO: LLM-based Population Self-play for Game Playing Strategy Improvement

Require: Game simulator (e.g., Checkers engine) Require: LLM for code generation Require: Initial population of bots P0 = (b1, . . . , bh) 1: for r = 1 to mdo 2: for i = 1 to |Pr-1| do ▷ Payoff table 3: for j = 1 to |Pr-1| do 4: Estimate si,j over k games. 5: P r i,j ← si,j 6: end for 7: end for 8: (xr1 , . . . , xr|Pr-1| ) ← FP(P r ) ▷ Nash Equilibrium 9: br ← MixtureBot(xr1 , . . . , xr|Pr-1| ) 10: for t = 1 to T do ▷ LLM Best Response 11: ct ← LLM Generate(br ) ▷ Prompt LLM with br 12: Estimate win rate(ct, br ) over k games 13: end for 14: bnew ← argmaxt win rate(ct, br ) 15: Pr ←Pr-1 ∪ {bnew} 16: end for 17: Return Pm

3 Results and Conclusions

We evaluate the ability of our procedure to identify increasingly strong strategies in the game. We run the LLM-PSRO procedure, using CodeLlama-7b-Instruct-hf as our LLM, for m = 5 rounds in n = 20 independent runs, each starting with an initial population of 3 bots (obtained by querying an LLM to produce code for playing in the game in the absence of additional instructions regarding an opponent). We examine the total probability mass placed by the Nash equilibrium on these initial bots, in each round (averaged over the n = 20 runs). We expect that as the new population bots grow in strength, less mass would be placed on the original bots, as they lose more and more to the newer generations.

The result of the analysis are shown in Figure 2. The blue line is the total probability mass on the original 3 bots (with the shaded area shown the standard deviation over the differnet LLM-PSRO runs). Even if the quality if the new bots is similar to the original bots, we would expect the mass on the original bots to diminish as mass would also be placed on the new bots; however, if their quality was the same as the bots, we'd expect their total mass to be proportional to their share of the population, which is plotted as a dashed red line in the figure ("Expected mass"). Figure 2 shows that the mass on the original bots diminishes more quickly than their share of the population, indicating the newly generated bots are of higher quality. In fact, after only 5 rounds, the original 3 bots obtain a mass of only about 14 , so the newer bots are mostly optimized against the previous generations of LLM-generated bots. This indicates that the LLM-PSRO method is generating increasingly stronger bots, and very quickly surpasses the quality of the initial population of bots. Our tool lets users select bots for the initial population (using pre-coded strategies, or by typing in strategies). It then runs the process, and allows inspecting the code for the bots added at each iteration. It displays the Nash equilibrium weights in each round, indicating the relative strengths of the bots in each generation.

4 RelatedWork

Game playing has been a foundational topic in AI since its early days, with classical algorithms such as Alpha-Beta pruning [Knuth and Moore, 1975] and MCTS [Coulom, 2006]. Combining these with deep reinforcement learning has allowed achieving super-human abilities in many games [Campbell et al., 2002; Silver et al., 2018; Perolat et al., 2022] However, these require extensive training and result in game playing policies which are not interpertable by humans [Hernandez-Leal et al., 2019; Angelov et al., 2021]. LLMs offer an alternative approach for gameplaying. Researchers used LLMs to model rational players in game theoretic and multi-agent settings [Zhang et al., 2024b; Fan et al., 2024; Guo et al., 2024; Huang et al., 2024]. Some work also uses game theoretic solutions to augment LLMs in strategic settings [Gemp et al., 2024].

In contrast to these approaches we do not ask the LLM to directly play in a game; Such a direct prompting approach can result in suboptimal or inconsistent strategies, highlighting the need for a more structured solution [Guo et al., 2024; Huang et al., 2024]. Rather, in our approach the role of the LLM is to generate a bot (an agent) for playing in the game. As we use the LLM to generate game playing code, our method is more akin to LLM software engineering agents (SWE-Agents), that produce piece of software for task [Liu et al., 2024b; Xia et al., 2024; Yang et al., 2024; Nathani et al., 2025]. Some such existing work also combines SWE-Agents with search techniques [Antoniades et al., 2024]. Although we use LLMs to write software, we differ from SWE-Agents in that we allow for competition between the codes based on a game theoretic recipe.

Researchers have employed many game theoretic methods for improving decision making. Classical recipes from game theory such as fictitious play [Hofbauer and Sandholm, 2002] are designed to select minimally exploitable mixed strategies. Recipes based on approximating equilibria have been used for many settings such as security games [Tambe, 2011] and generative models [Aung et al., 2022]. Some such game theory models have been used to optimize the performance of multi-agent reinforcement learning systems such the Stratego board game [Perolat et al., 2022] or the Starcraft video game Nash league [Vinyals et al., 2019]. We leverage the Policy Space Response Oracle framework [Lanctot et al., 2017; Zhang et al., 2024a] but adapt it for code generating LLMs, which is very different from the setting of reinforcement learning for which is has been previously applied.

5 Conclusions

We proposed an approach combining LLM code generation and self-play, that allows for generating bots to play in games. We follow the Policy Space Response Oracle [Lanctot et al., 2017] pattern, but operates in the space of programs where strategies are represented as computer code. By combining LLM bot generation with PSRO, we generate strong opponents whose code is fully readable and interpertable by humans. Hence, the produced bots can be edited and refined by humans, and their decision-making process is transparent.

There are several interesting directions for future work. First, are there alternative algorithms that could achieve a higher performance? Second, we leverage both the code generation ability of LLMs and their strategic reasoning. One might consider ways to strengthen strategic reasoning in LLMs. One option is leveraging synthetic data, such as the outcomes of previous tournaments. Further, we have observed that in many cases the code generation abilities of the LLM could also be improved. Synthetic data produced through the tournaments between the LLM generated programs can also be leveraged to improve the coding ability of the underlying LLMs. Finally, our demo focuses on the game of Checkers, where the agent interaction is competitive (zero-sum) and the environment is deterministic, and the entire state is observed by all the players. How should it be changed for cooperative domains [Nagarajan and Soˇsi´c, 2008; Bachrach et al., 2020; Bachrach and Porat, 2010; Sidji et al., 2024] or those with partial observability or increased stochasticity [Bowling and Veloso, 2000; Bachrach et al., 2012; Alsadat and Xu, 2024]?

Machine-readable versions of this paper, for tools and AI agents:

• Markdown — metadata, abstract, full text and references
• JSON — metadata and structured references
• BibTeX