{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/137607"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/137607","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Towards Better Turn-Based Strategy Planning Agents: Turn-Based Evolutionary Tree Search","abstract":"While AI agents surpass human performance in classical board games such as Chess, Go, and Shogi, many complex turn-based strategy (TBS) games, particularly those involving multiple actions per player turn, remain challenging due to their enormous branching factors and long planning horizons. Unlike single-action-per-turn games, TBS games like Civilization or TUBSTAP require sequencing multiple unit-level decisions per turn, resulting in state spaces where conventional algorithms like Monte Carlo Tree Search (MCTS) and Rolling Horizon Evolutionary Algorithms (RHEA) struggle to scale. First, we perform an investigation into state-of-the-art Deep Learning based models for game agents in TUBSTAP. Then, we propose Turn-Based Evolutionary Tree Search (TBETS), a novel hybrid algorithm that combines the depth-oriented selection of MCTS with the population-based variation of evolutionary algorithms. Unlike standard MCTS, TBETS treats each tree node as a turn-start state and each branch as a full multi-action sequence. To manage the wide but shallow tree, TBETS applies evolutionary operations, mutation and crossover, to choose child nodes to search, enabling adaptive exploration in high-dimensional action spaces. In experiments conducted on the TUBSTAP platform, TBETS outperformed state-of-the-art baselines, including M-UCT (i.e., MCTS-based Upper Confidence Bound applied to Trees), RHEA, and Flexible Horizon Evolutionary MCTS (FH-EMCTS). Notably, TBETS achieved a >20% higher winrate over RHEA on large 10-unit maps, and surpassed M-UCT by over 50% on 8-unit scenarios. These results demonstrate that TBETS is a scalable and effective approach for TBS games, particularly as complexity increases.","abstract_html":"While AI agents surpass human performance in classical board games such as Chess, Go, and Shogi, many complex turn-based strategy (TBS) games, particularly those involving multiple actions per player turn, remain challenging due to their enormous branching factors and long planning horizons. Unlike single-action-per-turn games, TBS games like Civilization or TUBSTAP require sequencing multiple unit-level decisions per turn, resulting in state spaces where conventional algorithms like Monte Carlo Tree Search (MCTS) and Rolling Horizon Evolutionary Algorithms (RHEA) struggle to scale. First, we perform an investigation into state-of-the-art Deep Learning based models for game agents in TUBSTAP. Then, we propose Turn-Based Evolutionary Tree Search (TBETS), a novel hybrid algorithm that combines the depth-oriented selection of MCTS with the population-based variation of evolutionary algorithms. Unlike standard MCTS, TBETS treats each tree node as a turn-start state and each branch as a full multi-action sequence. To manage the wide but shallow tree, TBETS applies evolutionary operations, mutation and crossover, to choose child nodes to search, enabling adaptive exploration in high-dimensional action spaces. In experiments conducted on the TUBSTAP platform, TBETS outperformed state-of-the-art baselines, including M-UCT (i.e., MCTS-based Upper Confidence Bound applied to Trees), RHEA, and Flexible Horizon Evolutionary MCTS (FH-EMCTS). Notably, TBETS achieved a >20% higher winrate over RHEA on large 10-unit maps, and surpassed M-UCT by over 50% on 8-unit scenarios. These results demonstrate that TBETS is a scalable and effective approach for TBS games, particularly as complexity increases.","abstract_has_math":false,"creators":["Neller, Taylor"],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Science & Applications","degree_department":"Computer Science and Applications","school":null,"contributors":[],"advisors":[],"committee_chairs":["Cho, Jin-Hee","Huang, Lifu"],"committee_members":["Zhou, Dawei"],"year":2025,"date_issued":"2025-08-28","date_published":"2025-08-28","updated_at":"2026-07-22T22:19:15Z","subjects":["Turn-Based Strategy","TUBSTAP","Game AI","MCTS","Evolutionary Algorithms"],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:44536"],"render_values":[{"text":"vt_gsexam:44536","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10919/137607","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Cho, Jin-Hee","Huang, Lifu"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Zhou, Dawei"]},{"key":"dc:contributor.department","label":"Department","values":["Computer Science and Applications"]},{"key":"dc:creator","label":"Author","values":["Neller, Taylor"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-08-29T08:00:33Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-08-29T08:00:33Z"]},{"key":"dc:date.issued","label":"Date","values":["2025-08-28"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science & Applications"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Turn-Based Strategy","TUBSTAP","Game AI","MCTS","Evolutionary Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:44536"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10919/137607"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["While AI agents surpass human performance in classical board games such as Chess, Go, and Shogi, many complex turn-based strategy (TBS) games, particularly those involving multiple actions per player turn, remain challenging due to their enormous branching factors and long planning horizons. Unlike single-action-per-turn games, TBS games like Civilization or TUBSTAP require sequencing multiple unit-level decisions per turn, resulting in state spaces where conventional algorithms like Monte Carlo Tree Search (MCTS) and Rolling Horizon Evolutionary Algorithms (RHEA) struggle to scale. First, we perform an investigation into state-of-the-art Deep Learning based models for game agents in TUBSTAP. Then, we propose Turn-Based Evolutionary Tree Search (TBETS), a novel hybrid algorithm that combines the depth-oriented selection of MCTS with the population-based variation of evolutionary algorithms. Unlike standard MCTS, TBETS treats each tree node as a turn-start state and each branch as a full multi-action sequence. To manage the wide but shallow tree, TBETS applies evolutionary operations, mutation and crossover, to choose child nodes to search, enabling adaptive exploration in high-dimensional action spaces. In experiments conducted on the TUBSTAP platform, TBETS outperformed state-of-the-art baselines, including M-UCT (i.e., MCTS-based Upper Confidence Bound applied to Trees), RHEA, and Flexible Horizon Evolutionary MCTS (FH-EMCTS). Notably, TBETS achieved a >20% higher winrate over RHEA on large 10-unit maps, and surpassed M-UCT by over 50% on 8-unit scenarios. These results demonstrate that TBETS is a scalable and effective approach for TBS games, particularly as complexity increases."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["Current methods of implementing game playing agents vary heavily on domain, but often share core principles. In games like Chess or Go, state-of-the-art computer algorithms use types of tree search to find strong moves, building a model of possible outcomes in a graph structure called a tree. Monte Carlo Tree Search (MCTS) is one such tree search algorithm and a core component of the first go engine that exceeded expert-level performance. However, MCTS and other algorithms fall far short of human-level play in many other domains, such as turn-based strategy (TBS) games like Civilization or the Turn-Based Strategy Academic Package (TUBSTAP) where a player sequences multiple moves per turn. Games like these confound MCTS and other tree search algorithms because of the large number of possible moves per turn. Rolling Horizon Evolutionary Algorithm (RHEA) is a method of evolutionarily finding strong sequences of actions to play, and is often strong in TBS scenarios. In our research, we develop Turn-Based Evolutionary Tree Search (TBETS) as a hybrid MCTS/RHEA algorithm to address weaknesses of both algorithms. We also investigate state-of-the-art neural network models for evaluating game state favorability. We perform our evaluation in a TBS game environment called TUBSTAP, evaluating agents head to head and collecting winrates. In experiments conducted on the TUBSTAP platform, TBETS outperformed state-of-the-art baselines, including MCTS, RHEA, and another hybrid algorithm named Flexible Horizon Evolutionary MCTS (FH-EMCTS). Notably, TBETS achieved a >20% higher winrate over RHEA on large 10-unit maps, and surpassed MCTS by over 50% on 8-unit scenarios. These results demonstrate that TBETS is a scalable and effective approach for TBS games, particularly as complexity increases."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Towards Better Turn-Based Strategy Planning Agents: Turn-Based Evolutionary Tree Search"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Cho, Jin-Hee","Huang, Lifu"],"dc:contributor.committeemember":["Zhou, Dawei"],"dc:contributor.department":["Computer Science and Applications"],"dc:creator":["Neller, Taylor"],"dc:date.accessioned":["2025-08-29T08:00:33Z"],"dc:date.available":["2025-08-29T08:00:33Z"],"dc:date.issued":["2025-08-28"],"dc:description.abstract":["While AI agents surpass human performance in classical board games such as Chess, Go, and Shogi, many complex turn-based strategy (TBS) games, particularly those involving multiple actions per player turn, remain challenging due to their enormous branching factors and long planning horizons. Unlike single-action-per-turn games, TBS games like Civilization or TUBSTAP require sequencing multiple unit-level decisions per turn, resulting in state spaces where conventional algorithms like Monte Carlo Tree Search (MCTS) and Rolling Horizon Evolutionary Algorithms (RHEA) struggle to scale. First, we perform an investigation into state-of-the-art Deep Learning based models for game agents in TUBSTAP. Then, we propose Turn-Based Evolutionary Tree Search (TBETS), a novel hybrid algorithm that combines the depth-oriented selection of MCTS with the population-based variation of evolutionary algorithms. Unlike standard MCTS, TBETS treats each tree node as a turn-start state and each branch as a full multi-action sequence. To manage the wide but shallow tree, TBETS applies evolutionary operations, mutation and crossover, to choose child nodes to search, enabling adaptive exploration in high-dimensional action spaces. In experiments conducted on the TUBSTAP platform, TBETS outperformed state-of-the-art baselines, including M-UCT (i.e., MCTS-based Upper Confidence Bound applied to Trees), RHEA, and Flexible Horizon Evolutionary MCTS (FH-EMCTS). Notably, TBETS achieved a >20% higher winrate over RHEA on large 10-unit maps, and surpassed M-UCT by over 50% on 8-unit scenarios. These results demonstrate that TBETS is a scalable and effective approach for TBS games, particularly as complexity increases."],"dc:description.abstractgeneral":["Current methods of implementing game playing agents vary heavily on domain, but often share core principles. In games like Chess or Go, state-of-the-art computer algorithms use types of tree search to find strong moves, building a model of possible outcomes in a graph structure called a tree. Monte Carlo Tree Search (MCTS) is one such tree search algorithm and a core component of the first go engine that exceeded expert-level performance. However, MCTS and other algorithms fall far short of human-level play in many other domains, such as turn-based strategy (TBS) games like Civilization or the Turn-Based Strategy Academic Package (TUBSTAP) where a player sequences multiple moves per turn. Games like these confound MCTS and other tree search algorithms because of the large number of possible moves per turn. Rolling Horizon Evolutionary Algorithm (RHEA) is a method of evolutionarily finding strong sequences of actions to play, and is often strong in TBS scenarios. In our research, we develop Turn-Based Evolutionary Tree Search (TBETS) as a hybrid MCTS/RHEA algorithm to address weaknesses of both algorithms. We also investigate state-of-the-art neural network models for evaluating game state favorability. We perform our evaluation in a TBS game environment called TUBSTAP, evaluating agents head to head and collecting winrates. In experiments conducted on the TUBSTAP platform, TBETS outperformed state-of-the-art baselines, including MCTS, RHEA, and another hybrid algorithm named Flexible Horizon Evolutionary MCTS (FH-EMCTS). Notably, TBETS achieved a >20% higher winrate over RHEA on large 10-unit maps, and surpassed MCTS by over 50% on 8-unit scenarios. These results demonstrate that TBETS is a scalable and effective approach for TBS games, particularly as complexity increases."],"dc:description.degree":["Master of Science"],"dc:format.medium":["ETD"],"dc:identifier.other":["vt_gsexam:44536"],"dc:identifier.uri":["https://hdl.handle.net/10919/137607"],"dc:language.iso":["en"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["Turn-Based Strategy","TUBSTAP","Game AI","MCTS","Evolutionary Algorithms"],"dc:title":["Towards Better Turn-Based Strategy Planning Agents: Turn-Based Evolutionary Tree Search"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Science & Applications"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:15Z"}