Mixing Search Strategies for Multi-Player Games
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 646-651.
Abstract
There are two basic approaches to generalize the propagation mechanism of the two-player Minimax search algorithm to multi-player (3 or more) games: the MaxN algorithm and the Paranoid algorithm. The main shortcoming of these approaches is that their strategy is fixed. In this paper we suggest a new approach (called MP-Mix) that dynamically changes the propagation strategy based on the players' relative strengths between MaxN, Paranoid and a newly presented offensive strategy. In addition, we introduce the Opponent Impact factor for multi-player games, which measures the players' ability to impact their opponents' score, and show its relation to the relative performance of our new MP-Mix strategy. Experimental results show that MP-Mix outperforms all other approaches under most circumstances.Inon Zuckerman, Ariel Felner, Sarit Kraus
@inproceedings{ijcai2009p113,
title = {Mixing Search Strategies for Multi-Player Games},
author = {Zuckerman, Inon and Felner, Ariel and Kraus, Sarit},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {646--651},
year = {2009},
url = {https://ijcai.org/proceedings/2009/113},
}
TY - CPAPER TI - Mixing Search Strategies for Multi-Player Games AU - Zuckerman, Inon AU - Felner, Ariel AU - Kraus, Sarit T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 646 EP - 651 UR - https://ijcai.org/proceedings/2009/113 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
