Hello. I'm in the process of designing your standard AI for a 2-player board game. I plan on using x-ply minmax and zero-sum because all the information is available to both players, and there are no random factors. The designer has recently been talking about incorporating a 3-player and 4-player version. Although minmax implies 2 players, i was hoping to find and reuse a set of algorithms for all variants (2 / 3 / 4). A number of PHDs were cut on applying minmax theory to 3-player games, but i can't find any of the source code. Has anyone out there had any experience with this? I'm also toying with GA, but i would hesitate to use it for the 2-player variant since minmax does a really good job of it Any help or advice you can offer is greatly appreciated. Silver

Minimax works with more than two players without that much difficulty (at each level of the recursion, each player uses the results of the evaluation functions to pick the move that maximizes their chance to win, you just might need to evaluate the leaf nodes for each player separately). It's the pruning strategies that become a lot more difficult. Humans tend to have more difficulty when there are more than 2 players too, since the game is no longer zero sum in that sometimes if one player is winning both the other players may act against him while ignoring each other.

Edit: Actually on second thought, I think a multiplayer minimax algorithm would just assume that all the non-max players were min, and it would choose a paranoid strategy in which in assumes the goal of all other players is to make it lose. I'm not sure what the more general algorithm I describe above would be called.

[Edited by - Vorpy on January 17, 2008 12:39:38 PM]

Your edit is correct in that, as a player, the only thing that matters is whether YOU win or lose. There is no "partial wins" or "almost wins". It's completely binary. In that sense a 4-player game IS a zero sum game.

As for the minimax algorithm, you are still performing the same summation by rolling up the tree from the leaf nodes (presumably end-game nodes of +1/-1) to the immediate decision layer and determining what the highest ranking choice is. Therefore, it operates the same from the mathematical sense. The major difference is in the recursion loop. You can't simply alternate him/me/him/me. This is changed simply by having an n value rather than a binary one to represent which player we are considering on that layer.

I have never implemented AI for a multi-player (>2) game, but I have been thinking about it recently, and there is a Monte Carlo method called UCT that will probably do a decent job. This algorithm is the base of the most successful computer go players we currently have, but there is nothing in its description that makes it work exclusively for 2-player games. One can even use it in games that involve dice, as long as there is no hidden information.

I don't I agree with the statement that "there are no partial wins". In the endgame of Puerto Rico, for instance, your victory sometimes depends on what a player that has no chance of winning will do. Minimax will assume that that player will pick the first move that you explore; UCT will assume that that player will play a random move. Although I like UCT's behavior better in this case, both assumptions are probably wrong: A player will often play the move that gets him a score as close as possible to the winner, even if he doesn't get there. Well, at least in games with victory-point counts, like Puerto Rico. You can tweak UCT to not score the game as simply "a win for player B, everyone else loses", but something that gives a small reward to players for getting close to B's score.

If you don't know Puerto Rico, you can think of Scrabble instead, and I think everything I said applies.

Here is an interesting thing: The number of players changes the game itself. The number of players actually specifies new properties of the game. The properties may be present in a sub-surface sense within all player counts, but they become explicit expressions at certain points.


1P - Discovery, Learning & Optimization.
- How best to apply level-up points, economic optimization, etc.
2P - Competition and Cooperation.
- It becomes possible to offer an opponant choices,
- and influence his/her decisions with your offerings.
3P - Alliances
- It becomes possible to team up against an enemy,
- and so it also becomes possible to switch sides,
- or to use one enemy against another.

And so I wonder: What new properties does a 4-Player game introduce?

Thanks for the replies everyone. Some additional research has revealed that, although minmax is suitable for 2-player, it really does not address 3+ players effectively. I'll have to chase down CTU and a few others for 3+, but i'm reconciled to the fact that i'll keep minmax for 2 players.

In the case of a 4 player game where 1 player wins, and the remaining 3 lose, i can accept the zero summness of it. However, when trying to calculate the objective function at the leaf plie, there is no way to modify your decision based on non-zero sum behaviour - alliances shifting back and forth between players. As soon as a player begins to weaken their position for the sake of their federation, minmax will lose its effectiveness, and the player will consider their victory 'partial'. Kingmaking is possible in the game i'm programming. Besides, having to execute minmax n times will reduce the number of plies i can use, and further reduce the AI's effectiveness.

Is their anything else i should consider. Some yummy AI perhaps?

Cheers,

Silverbeard

Minimiax works the same as it does in 2 player, it just makes the player extremely cautious. You run minimax the same amount with any number of players. Min just gets a lot more moves with more than 2 players.

My original suggestion involving running an evaluation for each player is not minimax, nor would it necessarily produce the same cautious behavior as minimax. It is more general than minimax because once you have an evaluation for each player you can then estimate how each player will play based on their goals. Assuming that every other player is trying to minimize your score is what minimax does, and it does not require the other evaluations. If you assume each player is trying to get the highest score, then maybe you can predict that each player will choose the move that brings them closest to having the highest score or increases the score the most, or maybe the player who is winning will try to keep his advantage to a minimum to prevent alliances, I dunno. It's a lot messier than minimax but it allows for more flexibility.

Quote:

Original post by Vorpy Minimiax works the same as it does in 2 player, it just makes the player extremely cautious. You run minimax the same amount with any number of players. Min just gets a lot more moves with more than 2 players.

But that means that all other players are out to get you, which is usually not the case. One of the important skills in Puerto Rico is to place yourself in a situation in which the moves that opponents take (to help themselves) end up helping you too. If all the opponents gang up against you, you'll probably lose. It seems more reasonable to assume that other players want to win.

I would agree. Minimax takes into account possibilities. All you are trying to do is raise the score of your moves - which, by definition, does what was said above... puts you in a place where there is the least possibility for damage. Cautious? Yes. Paranoid? Not necessarily.