What algorithms can be applied to Duchess (a board game like Chess)
I've been looking for algorithms/methods for the game called Duchess http://www.cse.unsw.edu.au/~blair/duchess/rules.html
I'm considering alpha beta pruning but I don't know if it is applicable for a game of more than two players.
The team vs team version can be played using alpha-beta pruning and similar game tree search techniques because it is a zero-sum two-player game. You just need to think of the teams as players.
The version with tree players is not amenable to standard alpha-beta like game tree search methods because it is not a two-player zero-sum game.
The problem is that in a two-player game you can use an "evaluation function" to evaluate how good a given board configuration is for player 1, and eg try to interpret this as "probability" that player 1 wins from the given configuration assuming "good" play. If the winning probability for player 1 is P then for player 2 it is 1 - P, obviously, so P is enough to represent the evaluation of a board configuration. Alpha-beta pruning uses this evaluation values at the core of the algorithm.
When you have three players, this is no longer well-defined, because the probability that a player 1 wins from a given configuration assuming "good" play depends on whether player 2 and player 3 will conspire together against player 1 or not. Also, there are scenarios known as "king making" where player 1 can't win, but player 1 can still decide whether player 2 or player 3 wins.
For three players, you basically have to resort to a scheme where a board configuration is evaluated to three values, P1, P2 and P3, each representing the relative preference of a given player to reach that configuration. After that, you can have a game three search where every player is trying to maximize the player's preference value at the search frontier. But you need for example to be able to answer to the question if it is more preferable to player X to lose by getting checkmated or to lose by not being the winner, and if so, how much.
I guess mini-max algorithm can be applied with taking max ((no. of players) - 1) times for each opponents turn and min just once for one's turn. So for one round of trees you will have tree depth equal to number of players In this case you gotta consider the cumulative max(maximum Sum of all the oponents). the working of algorithm will highly depend on how you do the scoring.
链接地址: http://www.djcxy.com/p/56412.html上一篇: Alpha Beta修剪假设