multi-player games thoughts

[Daniel Shawul]

I haven't yet implemented a way to handle when one player gets taken but that is definitely the incentive i.e upping your chance to 50%.

Ok I did some work now to take out the loosing player inside search.
First at the start position, I have scores of about 333 for win score of 1000.

Code: Select all

            a b c d e f g h i j k l m n
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
         11 R P . . . . . . . . . . p r * * * * * * * * * * 11
         10 N P . . . . . . . . . . p n * * * * * * * * * * 10
          9 B P . . . . . . . . . . p b * * * * * * * * * * 9
          8 Q P . . . . . . . . . . p q * * * * * * * * * * 8
          7 K P . . . . . . . . . . p k * * * * * * * * * * 7
          6 B P . . . . . . . . . . p b * * * * * * * * * * 6
          5 N P . . . . . . . . . . p n * * * * * * * * * * 5
          4 R P . . . . . . . . . . p r * * * * * * * * * * 4
          3 * * * . . . . . . . . * * * * * * * * * * * * * 3
          2 * * * h h h h h h h h * * * * * * * * * * * * * 2
          1 * * * l o m j i m o l * * * * * * * * * * * * * 1
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            a b c d e f g h i j k l m n

        RP10pr/NP10pn/BP10pb/QP10pq/KP10pk/BP10pb/NP10pn/RP10pr/***8***/***hhhhh
hhh***/***lomjimol*** w - - 0 1

go
[st = 5557ms, mt = 29250ms , moves_left 10]
3 330 0 982  a10c9  n5l6  d2d3  EBF=9.58
4 337 0 4250  b7c7  n10l9  j1i3  a8g2  EBF=7.80
5 337 1 7075  b7c7  n10l9  j1i3  a8g2  l9j8  EBF=5.66
5 337 1 12697  b7c7  n10l9  j1i3  a8g2  l9j8  EBF=6.40
6 322 1 22424  b7c7  m8l8  j1k3  a7b7  n9g2  EBF=5.12
6 323 3 31557  a10c9  m7l7  e1f3  a5c6  n8h2  EBF=5.43
6 328 4 70281  b5c5  m8l8  e1f3  a6e2  n9g2  EBF=6.24
6 329 6 109880  b4c4  n5l6  j1i3  a4b4  m11l11  h2h3  EBF=6.74
6 329 6 110798  b4c4  n5l6  j1i3  a4b4  m11l11  h2h3  EBF=6.75
7 322 7 125843  b4c4  m8l8  e1f3  a10c9  n9g2  EBF=5.19
7 330 11 228688  a5c6  m10k10  e1f3  a10c9  n5l6  j1i3  EBF=5.67
7 330 12 263644  a5c6  m10k10  e1f3  a10c9  n5l6  j1i3  EBF=5.79
8 330 14 306422  a5c6  n10l9  j1i3  a10c9  n5l6  e1f3  EBF=4.71
8 330 25 564271  a5c6  n10l9  j1i3  a10c9  n5l6  e1f3  EBF=5.09
9 330 31 731350  a5c6  n5l6  j1i3  b4c4  n10l9  k2k3  a4b4  EBF=4.35
9 330 62 1607255  a5c6  n5l6  j1i3  b4c4  n10l9  k2k3  a4b4  EBF=4.77
10 331 84 2211017  a5c6  n5l6  h2h3  a10c9  l6j5  i1b8  EBF=4.19
10 331 195 5403896  a5c6  n5l6  h2h3  a10c9  l6j5  i1b8  EBF=4.60
11 293 276 7730429  a5c6  m9l9  j2j3  b8c8  m5l5  i1n6  a9h2  n7n6  EBF=4.12
nodes = 15820704 <86 qnodes> time = 5578ms nps = 2836268
splits = 0 badsplits = 0
move a5c6
setup RP10pr/NP10pn/BP10pb/QP10pq/KP10pk/BPN9pb/1P10pn/RP10pr/***8***/***hhhhhhh
h***/***lomjimol*** b - - 1 1

Then I make some pawn moves so that the first player can capture the third player's king. (a8h1). So after it captured the king score jumped to 500.

Code: Select all

            a b c d e f g h i j k l m n
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
         11 R P . . . . . . . . . . p r * * * * * * * * * * 11
         10 N P . . . . . . . . . . p n * * * * * * * * * * 10
          9 B P . . . . . . . . . . p b * * * * * * * * * * 9
          8 Q P . . . . . . . . . . p q * * * * * * * * * * 8
          7 K . P . . . . . . . . p . k * * * * * * * * * * 7
          6 B P . . . . . . . . . . p b * * * * * * * * * * 6
          5 N P . . . . . . . . . . p n * * * * * * * * * * 5
          4 R P . . . . . . . . . . p r * * * * * * * * * * 4
          3 * * * . . . h . . . . * * * * * * * * * * * * * 3
          2 * * * h h h . h h h h * * * * * * * * * * * * * 2
          1 * * * l o m j i m o l * * * * * * * * * * * * * 1
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * *
            a b c d e f g h i j k l m n

        RP10pr/NP10pn/BP10pb/QP10pq/K1P8p1k/BP10pb/NP10pn/RP10pr/***3h4***/***hh
h1hhhh***/***lomjimol*** w - - 0 2

go
[st = 6175ms, mt = 29250ms , moves_left 9]
3 556 1 3541  a8h1  n8h2  h1i1  EBF=14.89
4 546 1 21525  a8h1  n8h2  h1h2  n10l9  EBF=11.85
5 555 3 34141  a8h1  m4l4  h1i1  n8h2  EBF=7.85
5 555 4 82776  a8h1  m4l4  h1i1  n8h2  EBF=9.42
6 554 7 163466  a8h1  n10l9  h1i1  n8h2  EBF=7.21
6 554 15 401594  a8h1  n10l9  h1i1  n8h2  EBF=8.41
7 609 29 794309  a8h1  EBF=6.81
7 609 32 904474  a8h1  n10l9  h1i1  m11l11  i1g1  n8h2  EBF=6.94
7 609 71 2039686  a8h1  n10l9  h1i1  m11l11  i1g1  n8h2  EBF=7.81
8 515 136 3977570  a8h1  n8h2  h1h2  n6m7  h2m7  n5m7  EBF=6.55
8 577 182 5385308  a8h1  n8h2  h1h2  n6m7  h2i1  m7g1  i1g1  n7m7  EBF=6.80
8 577 339 10021627  a8h1  n8h2  h1h2  n6m7  h2i1  m7g1  i1g1  n7m7  EBF=7.37
9 541 615 18260131  a8h1  n8i3  h1g1  i3i2  g1f1  i2i1  EBF=6.29
nodes = 18327143 <91 qnodes> time = 6188ms nps = 2961723
splits = 0 badsplits = 0
move a8h1

setup RP10pr/NP10pn/BP10pb/1P10pq/K1P8p1k/BP10pb/NP10pn/RP10pr/***3h4***/***hhh1
hhhh***/***lomjQmol*** b - - 0 2

[hgm]

What are the rules for losing? I have seen several in different variants of multi-player Chess. In some the game ends when one player is checkmated, and the player who did deliver the check is the winner. In another, you have to capture the King, and the remaining pieces of that color then become yours to move. Alternatives are to remove the pieces of the dead player, or leave them as 'dead wood'.

[Daniel Shawul]

What are the rules for losing? I have seen several in different variants of multi-player Chess. In some the game ends when one player is checkmated, and the player who did deliver the check is the winner. In another, you have to capture the King, and the remaining pieces of that color then become yours to move. Alternatives are to remove the pieces of the dead player, or leave them as 'dead wood'.

It is not very clear http://www.chessvariants.com/historic.d ... nelli.html

Pritchard writes: Checkmate and stalemate can only be given by the pieces of one colour. The forces of an eliminated player are static but may be captured, but not the king. A player must neutralise both opponents to win.

This still poses some questions: how can it be possible that only the pieces of one colour can give stalemate: when a player has two moves to its disposal, each putting his king into check from another player, then he effectively cannot move - something one should call a stalemate. If some reader has additional information on how this game was exactly played, please email me

I am not going to bother to implement a rule like "checkmate should be given by one player's pieces only. My rules are the player whose king gets captured gets dropped and the others fight it out, for all N player chessic games. The pieces of players that get dropped are left as dead wood. No bonus for capturing them.
I made some mistakes in updating piece square tables in the previous search. Now I get sane PVs

Code: Select all

[st = 6175ms, mt = 29250ms , moves_left 9]
3 548 0 3594  a8h1  n8m7  h1i1  EBF=14.97
4 543 1 23785  a8h1  n8m7  h1i1  m7h2  EBF=12.15
5 542 1 39716  a8h1  m10k10  h1i1  n8h2  EBF=8.10
5 542 4 95090  a8h1  m10k10  h1i1  n8h2  EBF=9.69
6 538 7 173783  a8h1  n8l6  h1i1  l6b6  EBF=7.29
6 538 15 431033  a8h1  n8l6  h1i1  l6b6  EBF=8.51
7 576 31 854199  a8h1  n8l6  h1i1  m5l5  i1j1  l6b6  EBF=6.88
7 576 75 2112878  a8h1  n8l6  h1i1  m5l5  i1j1  l6b6  EBF=7.85
8 505 157 4558307  a8h1  n8k5  h1i1  k5k2  i1i2  k2k1  EBF=6.66
8 538 201 5836886  a8h1  n8k5  h1i1  k5k2  b4c4  k2k1  i1j1  EBF=6.87
8 538 382 11149228  a8h1  n8k5  h1i1  k5k2  b4c4  k2k1  i1j1  EBF=7.47

[Daniel Shawul]

Ok more experiments with more than three player games. I tried 4-way chess and other mufti-player games. The paranoid algorithm seems to perform good in those games. I think this is due to the many many aggressive pruning algorithms that I already have besides alpha-beta such as null_move, LMR, futility, razoing etc. The decrease in performance of alpha-beta foretold by the following eqn doesn't seem to affect it that much.

Code: Select all

EBF = b^(k/n) + b^((n-k)/n) - 1  (judea pearl).

That is k vs (n - k) coalitions.If the collusion is always 1 vs n-1, then it may result in bad EBF. 2 vs 2 is better than 1 vs 3 f.i. EBF for the latter type = b^ ((n-1)/n) i.e approximately b^3/4 for 4-player games.

I have pretty much given up on shallow pruning ideas for maxn especially after good performances I get from LMR. What makes LMR unique from all the above methods is that it can be applied with out having bounds on the score (i.e alpha & beta). I think this is a very important property. It can be used with a progressive widening scheme combined with iterative deepening. So it can correct some of its mistakes with more and more depth. There is some more risk to be tolerated using LMR for multi-player games because we can not do researches. But I think this is something that can be tolerated compared to its gains. What I see in literature are attempts to do more direct shallow pruning and speculative deep pruning which usually perform so bad. People do not bother to add move ordering, iterative deepening for the above reasons but I do both just for LMR..

For 4-way chess, playing 4 paranoid nebiyus against each other gives funny games. Each will think the rest is against it and will make only the best defensive moves for some imagined attack and the games will be too long and boring... Making one or two of them to use the maxn strategy results in a better game overall.

Edit:
I also found a better* way of relative scoring. For material values of (a,b,c) the maxn scores are computed as
For 1st player: score = (a - b) + (a - c) = 2a - (b + c) instead of a - (b+c)
For 2nd player: 2b - (a + c)
For 3rd player: 2c - (a + b)
This results in a zero-sum game instead of constant sum game and the scores I get from searches are "normal" now without the need of factoring.

* It is NOT any better for shallow pruning (maybe even worse). Anyway the calculated bounds MAX_SCORE - a for shallow pruning is usually too big as too be impractical for games like chess ,where the maximum score is mate.

[Daniel Shawul]

EBF = b^(k/n) + b^((n-k)/n) - 1 (judea pearl).

That is k vs (n - k) coalitions.If the collusion is always 1 vs n-1, then it may result in bad EBF. 2 vs 2 is better than 1 vs 3 f.i. EBF for the latter type = b^ ((n-1)/n) i.e approximately b^3/4 for 4-player games.

Oops I was drunk when I wrote that formula. The description was correct though. The correct formula for the best case performance of paranoid (multi-player alpha beta) are:

Code: Select all

Nodes = b^ ((k/n) * d) + b^((n-k)/n) * d) - 1
EBF = b ^ ( max(k,n-k) / n )

The formulas are for the case where each player gets to play equal number of times across the depth of the tree (what is considered as "even" tree in the 2-player version). The root is MAX and leaves are the last of the MIN players..

But anyway paranoid for 4-way chess still gives EBF close to 2-3 that is same as 2 player chess.

Code: Select all

d

            a b c d e f g h i j k l m n
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
         14 * * * l o m j i m o l * * * * * * * * * * * * * * * * * 14
         13 * * * h h h h h h h h * * * * * * * * * * * * * * * * * 13
         12 * * * . . . . . . . . * * * * * * * * * * * * * * * * * 12
         11 R P . . . . . . . . . . p r * * * * * * * * * * * * * * 11
         10 N P . . . . . . . . . . p n * * * * * * * * * * * * * * 10
          9 B P . . . . . . . . . . p b * * * * * * * * * * * * * * 9
          8 Q P . . . . . . . . . . p q * * * * * * * * * * * * * * 8
          7 K P . . . . . . . . . . p k * * * * * * * * * * * * * * 7
          6 B P . . . . . . . . . . p b * * * * * * * * * * * * * * 6
          5 N P . . . . . . . . . . p n * * * * * * * * * * * * * * 5
          4 R P . . . . . . . . . . p r * * * * * * * * * * * * * * 4
          3 * * * . . . . . . . . * * * * * * * * * * * * * * * * * 3
          2 * * * H H H H H H H H * * * * * * * * * * * * * * * * * 2
          1 * * * L O M J I M O L * * * * * * * * * * * * * * * * * 1
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
            * * * * * * * * * * * * * * * * * * * * * * * * * * * *
            a b c d e f g h i j k l m n

                [Material: 5160 5160 5160 5160 ]
***lomjimol***/***hhhhhhhh***/***8***/RP10pr/NP10pn/BP10pb/QP10pq/KP10pk/BP10pb/
NP10pn/RP10pr/***8***/***HHHHHHHH***/***LOMJIMOL*** w - - 0 1

go
[st = 5557ms, mt = 29250ms , moves_left 10]
2 50 3 51  a5c6  n10l9  EBF=6.59
3 25 3 312  a5c6  n10l9  j1i3  EBF=6.41
4 0 4 680  a5c6  n10l9  j1i3  j14i12  EBF=4.82
5 75 4 8959  a5c6  n10l9  j1i3  j14i12  a10c9  EBF=5.95
5 75 4 8981  a5c6  n10l9  j1i3  j14i12  a10c9  EBF=5.95
6 50 6 10198  a5c6  n10l9  j1i3  j14i12  a10c9  n5l6  EBF=4.46
6 50 6 10224  a5c6  n10l9  j1i3  j14i12  a10c9  n5l6  EBF=4.47
7 25 6 12151  a5c6  n10l9  j1i3  j14i12  a10c9  n5l6  e1f3  EBF=3.66
7 25 6 12197  a5c6  n10l9  j1i3  j14i12  a10c9  n5l6  e1f3  EBF=3.66
8 0 7 15432  a5c6  n10l9  j1i3  j14i12  a10c9  n5l6  e1f3  e14f12  EBF=3.18
8 0 7 26309  a5c6  n10l9  j1i3  j14i12  a10c9  n5l6  e1f3  e14f12  EBF=3.42
9 -150 12 84804  a5c6  EBF=3.39
9 -575 14 112666  a5c6  EBF=3.51
9 -175 14 113347  a5c6  n10l9  e2e3  h13h12  a10c9  l9n10  f1b5  i14b7  a6b7  EB
F=3.51
9 -175 20 202682  a5c6  n10l9  e2e3  h13h12  a10c9  l9n10  f1b5  i14b7  a6b7  EB
F=3.76
10 -325 20 203890  a5c6  EBF=3.27
10 -280 21 214851  a5c6  n10l9  e2e3  h13h12  c6e5  l9k11  f1b5  i14b7  a6b7  n5
l6  EBF=3.29
10 -15 21 226519  a10c9  EBF=3.31
10 -265 25 260548  a10c9  n10l9  e2e3  h13h12  b11c11  l9k11  f1b5  i14b7  a5b7
 n5l6  EBF=3.36
10 -265 28 340049  a10c9  n10l9  e2e3  h13h12  b11c11  l9k11  f1b5  i14b7  a5b7
 n5l6  EBF=3.45
11 -415 29 340595  a10c9  EBF=3.07
11 -615 29 340923  a10c9  EBF=3.07
11 -165 29 344690  a10c9  n10l9  e2e3  h13h12  a5c6  m5l5  f1b5  i14b7  a6b5  n6
j2  e1f3  EBF=3.08
11 -115 31 357076  b8c8  EBF=3.09
11 -165 45 620975  b8c8  m4l4  e1f3  e13e12  a10c9  m8l8  e2e3  f14b10  a9b10  n
9g2  f1b5  EBF=3.25
11 -165 53 776194  b8c8  m4l4  e1f3  e13e12  a10c9  m8l8  e2e3  f14b10  a9b10  n
9g2  f1b5  EBF=3.32
12 -190 54 804320  b8c8  m4l4  e1f3  e13e12  a10c9  m8l8  e2e3  f14b10  a9b10  n
9g2  f1b5  j14i12  EBF=3.00
12 -190 59 866966  b8c8  m4l4  e1f3  e13e12  a10c9  m8l8  e2e3  f14b10  a9b10  n
9g2  f1b5  j14i12  EBF=3.02
13 -340 90 1390730  b8c8  EBF=2.87
13 -540 106 1692880  b8c8  EBF=2.92
13 -305 106 1712202  b8c8  m4l4  e2e3  h13h12  a9e5  m7l7  f1b5  i14c8  a6b5  n5
l6  j1i3  c8b9  a8b9  EBF=2.92
13 -305 123 1941399  b8c8  m4l4  e2e3  h13h12  a9e5  m7l7  f1b5  i14c8  a6b5  n5
l6  j1i3  c8b9  a8b9  EBF=2.95
14 -455 207 3574773  b8c8  EBF=2.85
14 -655 212 3656380  b8c8  EBF=2.85
14 -655 217 3716061  b8c8  m4l4  h2h3  h13h12  a9i1  n10l11  h1i1  i14c8  b9c8
m10l10  j1i3  j14i12  a8f13  n5l6  EBF=2.86
14 -155 220 3740460  a5c6  EBF=2.86
14 -320 337 6064086  a5c6  m4l4  h2h3  h13h12  a10c11  l4k4  j1i3  e14f12  b5c5
 m5l5  i1b8  i14b7  a6b7  n10l9  EBF=2.96
14 -320 373 6554583  a5c6  m4l4  h2h3  h13h12  a10c11  l4k4  j1i3  e14f12  b5c5
 m5l5  i1b8  i14b7  a6b7  n10l9  EBF=2.98
15 -295 407 7087344  a5c6  m4l4  h2h3  e13e12  b11c11  n5l6  e2e3  f14c11  a11c1
1  n10l9  f1b5  j14i12  a6b5  m5l5  i1b8  EBF=2.78
15 -295 420 7221371  a5c6  m4l4  h2h3  e13e12  b11c11  n5l6  e2e3  f14c11  a11c1
1  n10l9  f1b5  j14i12  a6b5  m5l5  i1b8  EBF=2.78
nodes = 7221371 <44 qnodes> time = 4219ms nps = 1711630
splits = 0 badsplits = 0
move a5c6

setup ***lomjimol***/***hhhhhhhh***/***8***/RP10pr/NP10pn/BP10pb/QP10pq/KP10pk/B
PN9pb/1P10pn/RP10pr/***8***/***HHHHHHHH***/***LOMJIMOL*** b - - 1 1