Multi-player game theory

5 Jan 2000

My motto might well be

Leave the weakest alone and face the strongest.
Invite others to do the same.
Think of keeping a low profile as part of a defense.
Develop and counter this on deeper levels.
I mean in life or society if you are ever fighting, as well as in games involving more than two players. My goal is to show this isn't an arbitrary fragile way, among other possible ways to behave -- assuming you wanna play the game.

On a more formal level, last year on some newsgroups I described a natural extension to the basic alpha-beta search algorithm used by most programs for two players. It's simple and based on the motto above, but if it were used, funny computer games like Worms would already be better at cooperating with human players. Have a look at my simple computer game Chap-Hexx. A less formal discussion followed about spoilers. An improvement was needed, at least when a game was close to be lost, as I understood recently thanks to dilemmas, a concrete case of spoilers. It's explained now.

Avoiding dilemmas

Mark Mammel mentioned to me that a player y may try to win in a risky way. There might be another player x threatening to win, and instead of blocking x safely, y may create a strong threat too, hoping the next player o will choose to block x rather than y and let y win rather than x.

Here's Mark's example on a three player game of Five-in-a-row:

    o x x x x .
    . . . . . .    y's turn, then o's, then x's
    . y y y . .
If y blocks x, the game will happily go on. If y extends its own row, the game will soon end up as
    o x-x-x-x-x
    . . . . . .    a win for x
    o y y y y .
or
    o x x x x o
    . . . . . .    a win for y.
    x y-y-y-y-y
It's more than risky from y to have created such a drastic dilemma for o. The player o might well assume both x and y are good enough to see their way to win. So o might rightly consider both loosing options to be equally bad and choose x's win indeed.

Most programs, mine included, would create a spoiling dilemma as y above, by seeing a difference between o's two defeats, however close they might be. They would assume o's move leading to y's win gives a tiny better chance to o because the game lasts longer -- leaves more room to blunders -- and the final position offers less opportunities for the other loosing player, x in that case, to win too if the game were to be continued kind of post-mortem.

On two player games, that way to see isn't bad. However a player chooses to loose, the other wins if he knows how. It doesn't create blunders or prevent a winning move to be played. It isn't needed either. On three and more player games, we have to forget it, at least until we work out a correct way to play. Thus,

It's the basic lesson I learnt from Mark's experience. In addition Mark further suggests to punish players like y by choosing the move he didn't want. Since there might be more than one punishment involved at a time, for now I'd prefer to choose randomly whenever facing equivalent moves. Here is the corrected alpha-beta-gamma algorithm.
function FABC( Position, a, b, c, Depth )
returns a triplet of signed numbers and possibly a move;
{  if Depth = 0 or the game is over then
   {  (x, y, z) := some static additive evaluation of Position,
      x measuring how good is Position for the Player to move,
      y measuring how good is Position for the next Player,
      z measuring how good is Position for the further next Player,
      the higher the better, -infinite for a defeat, +infinite for a win;

      if the game is over then
         return (x, y, z, "game over");
      else
         return ( min(x-y, x-z), min(y-x, y-z), min(z-x, z-y), "static" );
   }
   Bestx := -infinite;
   Worsty := Worstz := +infinite;
   n := 0;  (* will count equivalent moves *)
   for every valid move M on Position do
   {  (y, z, x, Trash) := FABC( M(Position), -c, -a, b, Depth-1 );
      if x = Bestx then  (* we've found an equivalent move *)
      {  n := n+1;
         if y < Worsty then Worsty := y;
         if z < Worstz then Worstz := z;
         if a random number from {1,...,n} = n then
            BestM := M;
      }
      else if x > Bestx then  (* we've found a better move *)
      {  BestM := M; 
         (Bestx, Worsty, Worstz) := (x, y, z);
         n := 1;
         if x > b or x > c then
         (* Watch out, this test may actually need more clauses *)
            return(Bestx, Worsty, Worstz, BestM);
         if x > a then
            a := x;
      }
   }
   return(Bestx, Worsty, Worstz, BestM);
}
All variables are local in the function. The function is first called as follows:
 FABC( PositionToAnalyze, -infinite, +infinite, +infinite, WantedDepth)
and it shall return three estimated values and a move.

That's it. Well, further improvements might be searched around the fact that almost equivalent moves aren't compared while our evaluation function isn't perfect enough to assure they wouldn't really be equivalent. Some consideration with probabilities and standard deviation might help.

Keep in touch!

a discussion about spoilers

Subject: Re: alpha beta... gamma
Newsgroups: comp.ai.games

14 Dec 1998

Claude Chaunier wrote:

"Hi, does anybody know about min-max and alpha-beta search extended to three or more players?"
You make some good points on this matter. Competitive games with more than 2 players can become quite complex. In a book on new rules for old games (I forget the exact title/author(s)), one difficulty in designing games for more than 2 players is the spoiler issue. In one sense, your 'classical' extension to the game tree (max/min/min) seems intuitive. From another perspective, though, the spoiler translates (in some sense) into playing against a single opponent who is twice as large (powerful, wealthy, etc.). I doubt there's an easy answer to your question.

--
Will Dwinnell
 

16 Dec 1998

Will Dwinnell wrote

> the spoiler translates (in some sense) into playing against a single opponent who is twice as large (powerful, wealthy, etc.).
If we play against a power twice as big as us, but half of it is devoted to playing against itself, the game is well balanced. So do you mean that our two opponents may fight more against us than against each other along all the game? They'll keep us on the loosing track to get something more like half a chance each to win than like one third?

Well, if they are determined to do it on every game we'll play, regardless of what we do, what can we do anyway? But if our opponents are taken from a pool of less static players who wouldn't join forces with too strong a player -- because they would end up with less than one third of a chance -- and so decide to join with the weakest against the strongest player for the time of a game, according to winning statistics for example, then we are back to the (max,min,min) tactics I started the thread with, played at depth 1 on the meta-game of improving one's winning statistics.

And doesn't it look better to do it even more dynamically at move level inside the game?

Claude Chaunier
 

19 Dec 1998

I (Will Dwinnell) wrote:

"...the spoiler translates (in some sense) into playing against a single opponent who is twice as large (powerful, wealthy, etc.)."
Claude Chaunier responded:
"If we play against a power twice as big as us, but half of it is devoted to playing against itself, the game is well balanced."
But the part about 'half of it is devoted to playing against itself' is a big assumption. How these two forces which both oppose us interact with one another is important. Obviously, from a simple 'summing' perspective, the best case scenario is that the two opponents simply concentrate on each other, making solution of the game for us (the 3rd player) trivial. At the other end of this spectrum is the case where they both concentrate on beating us. In some games, such as Empire, either situation (or anything in between) is a possibility. But getting past this 'summing' approach to things, we realize that even a tiny 3rd player may wreck the game (as evidenced by happenings in on-line games) for everyone else. If we play chess but include a tiny 3rd player, let's call him red, who can capture either of our pieces, we may say that the game is 'fair' since red may attack either white or black, but as the spoiler, he can make the difference between victory or loss without ever having the chance to win himself!

--
Will Dwinnell
 

20 Dec 1998

Will Dwinnell wrote

"...even a tiny 3rd player may wreck the game (as evidenced by happenings in on-line games) for everyone else."
I did it and had to face it a lot when I started. That's how we come to understand that our best chances to keep the game under control and to win according to our skill is to keep -- or give back -- everybody's chances to win till the very end, when our deeper view and better preparation may then lead us towards a more likely victory. That doesn't prevent us to set up subtle plans discreetly reinforcing our position all along the game, but right, it means we have to be very nice to the weakest player, especially when it's even the most stupid player we've ever met -- or so do we think. That doesn't make the game less interesting, but anyway that seems to be the best way.

If an idiot starts a game by overfighting me, I easily remember how Go beginners cannot help entering local fights while more experienced players would not loose a bit of their temper and even not sigh about such a weakness. Some on-line games must involve pretty old beginners who don't see the difference with two player games and see everything like made up of several binary components. I'd better show them something different and hope they shall evolve. I'm not going to maximize my responsability for the possible wreckage. I prefer to make something of it, however difficult it is.

In a pragmatic nutshell, if the possibilities for a game to be wrecked hurts you -- as it hurts me --, value them negatively while playing and act accordingly.

Well, I'm afraid you came to decline such games then!

Sure, if we can't even expect any wish to win from a player there is no way to avoid any wreckage. But in classic Chess too -- though we would surely win --, the game would still be wasted time and we wouldn't be able to avoid it. So that's not a new problem. And there are certainly enough people to play with who struggle to win. Now a common mistake is to expect how they'll struggle and then to get angry. Again, like in Chess, we also got to develop extravagance-proof playstyles. It's easier said than done!

Any other argument for leaving alone the weakest player? :-)

Claude Chaunier
 

[Up home]