R e TA : Recursively Thinking Ahead to Improve the Strategic Reasoning of Large Language Models (2024)

Abstract: Current logical reasoning evaluations of Large Language Models (LLMs) primarily focus on single-turn and static environments, such as arithmetic problems. The crucial problem of multi-turn, strategic reasoning is under-explored. In this work, we analyze the multi-turn strategic reasoning of LLMs through text-driven complete- and incomplete-information gaming, e.g., board games (Tic-Tac-Toe, Connect-4) and poker games (Texas Hold’em Poker). Specifically, we consider two distinct scenarios: 1) Online Racing, featuring multiple LLMs/agents to facilitate direct competition and comparison; 2) Offline Probing, constructing targeted questions with verified ground truth to evaluate LLMs’ strategic behaviors. Experimental results demonstrate that existing state-of-the-art LLMs and reasoning schemes are largely ineffective for strategic reasoning tasks. To mitigate these limitations, we propose a simple yet effective Recursively Thinking-Ahead (ReTA) agent, incorporating a recursive prompting mechanism that automatically analyzes the opponents’ future moves/actions and assigns reward signals for these situations, to strengthen the strategic reasoning of LLMs. We hope our work could spur further research and exploration in the multi-turn strategic reasoning of LLMs. The code is available at https://github.com/jinhaoduan/ReTA.

## introduction large language models (llms) have witnessed remarkable advancements in logical reasoning. models such as chatgpt are proven to be effective in solving math problems @xcite , longterm task planning @xcite , etc. however, these evaluations are predominantly singleturn and static. although there are environments such as alfworld @xcite ) that provide interactive environments to evaluate the planning and reasoning capabilities of llms, these evaluations still focus on the linguistic capabilities of llms, e.g., reading understanding, without much strategic thinking. therefore, beneath the impressive linguistic capabilities of llms, a critical question that has piqued the curiosity of researchers and practitioners alike: "what lies beyond static logical reasoning for llms?" strategic multi-turn reasoning tasks, such as board and card games, are more reflective of realworld complexities and widely utilized in reinforcement learning @xcite , presenting an innovative approach to assessing the logical reasoning of llms. these environments simulate interactive and competitive scenarios, furnishing mathematically well-structured rules and controllable complexity, with explicit success criteria. each participant is prompted to strategically choose actions when facing well-defined states to defend against moves from opponents. in these environments, each competition can extend over dozens of hands, depending on the intricacy of the task, which effectively examines llms' abilities in maintaining multi-turn contexts and exhibiting strategic thinking. the presence of opponents in the game environment introduces additional dynamics and complexity, posing a significant challenge to the reasoning abilities of llms @xcite . to spur further research and exploration, we first analyze the behavior of llms under the multi-turn strategic reasoning scenarios. specifically, we encompass complete information gaming, such as tic-tac-toe 1 and connect-4 2 , as well as incomplete information games, such as texas hold'em poker 3 as the environments. these games have simple rules, clear criteria, limited action/state space, and controllable difficulties, making them suitable for current llm evaluations. we analyze the behavior of llms under two scenarios: online racing and offline probing. for online racing, we apply direct competitions among multiple llms, allowing for a straightforward comparison of their reasoning skills by pitting them against each other in a competition. for offline probing, we provide demographic analysis by constructing error-driven questions and verified ground truth, for a detailed analysis of llms' strategic behaviors. in terms of llm agents, we consider advanced reasoning methods, such as chain-of-thought (cot) @xcite , self-consistent chainof-thought (cot-sc) @xcite , treeof-thought (tot) @xcite , react @xcite . however, our experimental results indicate that most of these reasoning agents are largely ineffective in our strategic gaming scenarios. with detailed demographic analysis, we conclude the main reasons behind this failure model as two-fold: ➊ autonomous agents lack gaming intent, i.e., they cannot think ahead to defend the future moves from their opponents; ➋ llms suffer from severe hallucinations @xcite and factual errors @xcite @xcite , e.g., llms cannot recognize immediate win situations (whether two/three symbols are in a row for tic-tac-toe). to overcome these limitations, we propose a simple yet effective recursively thinking-ahead agent (reta). reta uses a recursive prompting mechanism that automatically analyzes the opponents' potential future moves/actions and assigns reward signals for these situations. then, the reward signal is backtracked to the current action and eventually dictates the action selection of reta. under comprehensive gaming settings, reta significantly outperforms state-of-the-art reasoning methods. our key contributions are summarized as follows: ## related work benchmarks for llms reasoning . recently, there has been a substantial amount of research focused on evaluating the reasoning capabilities of llms and llms-powered agents. alfworld @xcite and virtual-home @xcite are popular text-driven scenarios that simulate interactive house-holding environments, which have been widely utilized in evaluating the planning and reasoning @xcite of llms. hotpotqa @xcite is a challenging qa dataset, necessitating multihop reasoning skills such as retrieval and search from llms. there have been a lot of benchmarks aiming to evaluate tool utilization capabilities (e.g., web browsing), including mind2web @xcite , webarena @xcite , and webshop @xcite . agentbench @xcite and mint @xcite present comprehensive evaluations for llms-as-agents, from the perspective of code, web, and game. recently, gtbench @xcite has been proposed as a general framework for game-theoretic evaluations of llms. differently, this work focuses more on the advanced reasoning agent, i.e., reta, while gtbench aims at the evaluation of existing llms and reasoning agents. reasoning and planning with llms. llms have demonstrated reasoning and planning abilities by breaking down intricate questions into sequential intermediate steps, known as chain-of-thought (cot) @xcite , prior to generating the final response. building upon this concept, self-consistency @xcite samples multiple chains and selects the best answer via majority voting, tot @xcite ) models the llm reasoning process as a tree structure. in addition, llms have achieved successful results in planning and action generation @xcite , environment system prompt: you are a powerful gaming agent that who can make proper decisions to beat the user in gaming tasks. you are playing tic-tac-toe with me cot agent prompt agent observation prompt: currently, your opponent has finished moves c2r3. the legal moves are c1r1, c1r2, ...... step prompt: please first think about your situation, then choose one move from legal moves to set up an advantage. cot agent thought: my opponent has placed their symbol in c2r3 and i have placed mine in the middle row (c2r2). this means that i have a potential advantage in the game. i will choose to place my symbol in the top-right position to set up a potential winning move in the next turn. move: c3r1 observation prompt: your opponent has finished moves c2r2, c3r1. you have finished moves c2r3. the legal moves are c1r1, c1r2, ...... step prompt: please choose one move from legal moves to set up an advantage. cot agent wins! . . . . . . connect-4 observation prompt: you are the first to go. the legal moves are c1r6, c2r6, c3r6, c4r6, c5r6, c6r6, c7r6. step prompt: please first think about your situation, then choose one move from legal moves to set up an advantage. thought: by starting in the center, i should create opportunities to build sequences in multiple directions (vertically, horizontally, and diagonally). this central position gives me more flexibility in future moves and can potentially limit your options move: c4r6 c3r6 observation prompt: your opponent has finished moves c4r6. the legal moves are: c1r6, c2r6, c3r6, c4r5, c5r6, c6r6, c7r6. step prompt: please choose one move from legal moves to set up an advantage. system prompt: you are a powerful gaming agent who can make proper decisions to beat the user in gaming tasks. you are playing connect-4 with me cot agent prompt agent observation prompt: currently, your opponent has finished moves c3r6. the legal moves are c1r6, c2r6, c3r5, ...... step prompt: please first think about your situation, then choose one move from legal moves to set up an advantage. cot agent thought: i'll place my disc in c5r6. this positions my disc to the right of my initial disc in the center column, creating a potential line horizontally and keeping options open for vertical and diagonal connections as well. move: c5r6 observation prompt: your opponent has finished moves c4r6, c5r6. you have finished moves c3r6. the legal moves are c1r6, c2r6, ...... step prompt: please choose one move from legal moves to set up an advantage. cot agent wins! . . . . . . texas hold'em poker system prompt: you are playing texas holdem poker with the other 1 players. the aim of each player in texas hold'em poker is to win chips or money from other players by either having the best hand at showdown or by convincing other players to fold their hands. the small blind bet of this game is 1 and the big blind bet of this game is 2. observation prompt: here are the situations you are facing: you are in the preflop stage. you are in the small blind position. the current round pot is 3 and the community pot is 0. your card is 4h and ac. your remaining chip is 199. currently, your legal actions are fold, check, raise_3bb, ...... step prompt: it is your turn to take your action. given the current situation, first make a plan about how to make your decision regarding the current situation, then select one action from the action space to beat opponents thought: i would select raise_3bb. this move can help to take control of the pot early and gives a chance to gauge the reactions of the opponents. move: raise_3bb cot agent call prompt agent observation prompt: here are the situations you are facing: you are in the preflop stage. you are in the big blind position. the current round pot is 11 and the community pot is 0. your card is kd and as. your remaining chip is 198. currently, your legal actions are fold, check, raise_3bb, ...... in this round, prior players have made the following actions: player 1 (small blind): raise_3bb step prompt: please select one action from the action space to beat opponents. 2022b). @xcite proposes a multimodal language model for embodied reasoning tasks, visual-language tasks, and language tasks. beyond that, @xcite translates such intermediate steps into executable programming languages to conduct classical planning algorithms. also, autonomous agents have driven zero/fewshot llms to achieve complex reasoning and planning tasks through prompt engineering @xcite @xcite . @xcite endow agents with the capability to engage in introspection regarding the feedback provided by llms. ## preliminary analysis we first investigate the strategic reasoning capabilities of llms through online competitions. figure 1 presents the procedures of online llms racing and the demonstration of each environment. ## in-depth strategic reasoning analysis the limited success of state-of-the-art llms when against random agents as opponents raises a critical question: what specific vulnerabilities and limitations are being exposed? ## conclusion in this paper, we propose to evaluate the multiturn strategic reasoning capabilities of llms. we provide online agent competition and offline reasoning probing, offering an in-depth examination of strategic behaviors. our work introduces a new dimension to llms evaluation, and we hope it will inspire further research into the multi-turn strategic reasoning of llms.