14 December 1998

Hi, does anybody know about min-max and alpha-beta search extended to three or more players?

I'm often reading it's far less simple because of psychological matters, like temporary cooperations and sensibility to others' blunders. But psychology was already a part of the game with two player games like chess, for which you could heavily rely on assumptions about the opponent's psychology, and AI and nice human players often choose to assume 1) the others are as good and fair as they are -- with the same meaning for those adjectives -- and 2) the others are assuming the same about them and no more. I bet you the same choice can be made with more players, resulting in a smart, solid, and still sensitive play style. I've played like that multi-player versions for Pente and Hexbo and am very happy with it.

A natural way to extend the min-max search then -- classically used by
computer players in two player games -- to three (or more) players is
to go on evaluating the board with a kind of additive measure from the
point of view of each player. Let's say a position gets the triplet
(*x*, *y*, *z*) where *x* measures how strong the first player is in some way
we would like to be as absolute as possible, *y* how strong the second
is, *z* how strong the third is. Then a better measure triplet for the
position compares each value with the strongest of the two others,
giving

( *x* - max(*y*, *z*), *y* - max(*x*, *z*), *z* - max(*x*, *y*) )

= ( min(*x*-*y*, *x*-*z*), min(*y*-*x*, *y*-*z*), min(*z*-*x*, *z*-*y*) )

and the first player for example must strive to maximize min(*x*-*y*, *x*-*z*).
Well, she must if she doesn't look further to her first move and
doesn't consider the other players' similar objective - and this can
be obviously criticized as it may well appear that ignoring the
weakest player choices would be fatal. But it's only how things look
like at one ply deep in the search. With a deeper min-max search in
the game tree, things get far more interesting, and the weakest
player's moves are automatically taken into account, resulting into
tight and subtle temporary implicit cooperations among the players.

Sorry if this is well-known. I tend to think programmers are blind to it when I see how badly the computer plays so far at classic multi- player games as Worms, Hearts, Chinese Checkers, Starcraft, while it's so good at Chess and others.

Now we can even extend the alpha-beta pruning technics to save time and not explore useless branches. Here is the evaluation function. See how close it is to the classical alpha-beta two-player case. You can bet it goes on like that with four or more players.

The parameters in the first call must get initial values as follows:functionFABC(Position,a,b,c,Depth) returns a triplet of reals; {ifDepth=0orgame overthen{ (x,y,z) := some static additive evaluation ofPosition,xmeasuring how good isPositionfor the Player to moveymeasuring how good isPositionfor the next Playerzmeasuring how good isPositionfor the further next Player;return( min(x-y,x-z), min(y-x,y-z), min(z-x,z-y) ); }Bestu:= -infinite;forevery valid moveMonPositiondo{ (v,w,u) := FABC(M(Position), -c, -a,b,Depth-1 );ifu>Bestuthen{BestValue:= (Bestu,Best1,Best2) := (u,v,w);ifu>=boru>=cthenreturn(BestValue);ifu>athena:=u; } }return(BestValue); }

FABC(Now here are some typical situations to show how pruning works with 3 players. It's a good start to show thatPositionToAnalyze, -infinite, +infinite, +infinite,WantedDepth);

`FABC()`

above is sound and
optimal in general.
Let's imagine Player 0 found a first move valued (r,s,t). Player 0 now tries a second move and Player 1 finds a first answer valued (u,v,w). Under which conditions doesn't Player 1 need to look for better answers because Player 0 is already sure to prefer his first move, seeing this first answer from Player 1? Under the following equivalent conditions:

- for all x,y,z, whenever (x,y,z) is a better value for Player 1 than (u,v,w),

then (x,y,z) is worse for Player 0 than (r,s,t)

- for all x,y,z, whenever min(y-x,y-z) > min(v-u,v-w) then

min(x-y,x-z) < min(r-s,r-t)

- for all a,b, whenever min(a,b) > min(v-u,v-w) then

min(-a,b-a) < min(r-s,r-t)

- for all a,b, whenever a and b > min(v-u,v-w) then

-a or b-a < min(r-s,r-t)

- -min(v-u,v-w) <= min(r-s,r-t) (1)

- for any (u,v,w) better than (i,j,k) for Player 2, (1) holds

- for all u,v,w, whenever min(w-u,w-v) > min(k-i,k-j) then

-min(v-u,v-w) <= min(r-s,r-t)

- for all a,b, whenever min(a,b) > min(k-i,k-j) then

-min(a-b,-b) <= min(r-s,r-t)

- for all a,b, whenever a and b > min(k-i,k-j) then

b-a and b <= min(r-s,r-t)

- for all x,y,z, whenever min(z-x,z-y) > min(k-i,k-j) and

min(y-x,y-z) > min(v-u,v-w) then min(x-y,x-z) < min(r-s,r-t)

- for all a,b, whenever (a and b > min(k-i,k-j)) and

(b-a and b < -min(v-u,v-w)) then b-a or -a < min(r-s,r-t)

- -min(k-i,k-j) <= min(r-s,r-t) . (2)

That's all for now. Does it rings a bell somewhere?

From: "Claude Chaunier" <chaunier@handy.univ-lyon1.fr> Newsgroups: comp.ai.games,rec.games.abstract,rec.games.diplomacy