A hyperheuristic methodology to generate adaptive strategies for games

Li, Jiawei; Kendall, G.

Abstract

Hyperheuristics have been successfully applied in solving a variety of computational search problems. In this study, we investigate a hyper-heuristic methodology to generate adaptive strategies for games. Based on a set of low-level heuristics (or strategies), a hyper-heuristic game player can generate strategies which adapt to both the behaviour of the co-players and the game dynamics. By using a simple heuristic selection mechanism, a number of existing heuristics for specialised games can be integrated into an automated game player. As examples, we develop hyperheuristic game players for three games: iterated prisoner's dilemma, repeated Goofspiel and the competitive traveling salesmen problem. The results demonstrate that a hyperheuristic game player outperforms the low-level heuristics, when used individually in game playing and it can generate adaptive strategies even if the low-level heuristics are deterministic. This methodology provides an efficient way to develop new strategies for games based on existing strategies.

Citation

Li, J., & Kendall, G. (2017). A hyperheuristic methodology to generate adaptive strategies for games. IEEE Transactions on Computational Intelligence and AI in Games, 9(1), https://doi.org/10.1109/TCIAIG.2015.2394780

• Journal Article Type: Article
• Acceptance Date: Jan 3, 2015
• Online Publication Date: Jan 21, 2015
• Publication Date: Mar 1, 2017
• Deposit Date: Feb 6, 2018
• Publicly Available Date: Feb 6, 2018
• Journal: IEEE Transactions on Computational Intelligence and AI in Games
• Print ISSN: 1943-068X
• Electronic ISSN: 1943-0698
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 9
• Issue: 1
• DOI: https://doi.org/10.1109/TCIAIG.2015.2394780
• Keywords: Competitive traveling salesmen problem; game;; Goofspiel; hyperheuristic; iterated prisoner's dilemma (IPD)
• Public URL: https://nottingham-repository.worktribe.com/output/970353
• Publisher URL: http://ieeexplore.ieee.org/document/7017583/