odd-even effect

[Daniel Shawul]

It seems that this effect is a lot more pronounced in reversi and go than chess. For reversi since every move 'captures' opponent pieces the evaluation at ply P and P + 1 are always different. Also what moves to include in the qsearch ? All the legal moves except a pass flips opponent pieces and position would never ever get queiscent unless we search deep enough (64 plies on 8x8).

Same goes for 9x9 Go. I am doing material count , silly I know, neverthless Go still has this pronounced odd-even effect when a stone is added on each players turn which means +- 100cp flip of score.

I can post search output but I think the problem is clear. So what do you do ? I am thinking of making sure of the same side to move at the leaves. If in some part whites to move and in another it is black, this results in chaos. In short I plan to either evaluate the "odd" or "even" depth trees by incrementing wtih 2. But this has an unwanted sideeffect of weakeing Iterative deepening, and also extensions are gonna have to be aggressive (minimum is 2 plies), and there is also reductions. What do you think ?

Edit: Just in case. First one is reversi which has a very different score due to the flips which I think is impractical to do it like I am doing it here.

Code: Select all

feature done=0
ht 2097152 X 64 = 128MB
d

            a b c d e f g h
            * * * * * * * * * *
          8 . . . . . . . . * * 8
          7 . . . . . . . . * * 7
          6 . . . . . . . . * * 6
          5 . . . P p . . . * * 5
          4 . . . p P . . . * * 4
          3 . . . . . . . . * * 3
          2 . . . . . . . . * * 2
          1 . . . . . . . . * * 1
            * * * * * * * * * *
            a b c d e f g h

        8/8/8/3Pp3/3pP3/8/8/8 w - - 0 1

go
[st = 5557ms, mt = 29250ms , hply = 0 , moves_left 10]
2 0 0 8  e6
2 0 1 14  e6 f6
2 0 1 30  e6 f6
3 300 1 45  e6
3 300 1 65  e6 f6 g6
3 300 1 74  e6 f6 g6
4 0 1 96  e6
4 0 1 128  e6 f6 g6 g7
4 0 1 200  e6 f6 g6 g7
5 300 1 241  e6
5 300 1 337  e6 f6 g6 g7 g8
5 300 1 346  e6 f6 g6 g7 g8
6 0 1 386  e6
6 0 3 518  e6 f6 g6 g7 c4 h6
6 0 3 993  e6 f6 g6 g7 c4 h6
7 300 3 1064  e6
7 300 3 1255  e6 f6 g6 g7 c4 c3 g8
7 300 3 1284  e6 f6 g6 g7 c4 c3 g8
8 0 3 1342  e6
8 0 3 1563  e6 f6 g6 g7 g8 h8 c4 d6
8 0 3 4081  e6 f6 g6 g7 g8 h8 c4 d6
9 100 4 4230  e6
9 300 4 4289  e6
9 300 4 4690  e6 f6 g6 g7 c4 c3 c2 b2 g8
9 300 4 4790  e6 f6 g6 g7 c4 c3 c2 b2 g8
10 0 4 4932  e6
10 -200 4 20564  e6
10 -200 6 21463  e6 f4 f3 d6 c6 d7 c8 d8 e8 g2
10 400 6 58738  c4
10 0 7 60994  c4 c5 c6 e3 f6 e6 f7 e7 f4 g7
10 0 7 65010  c4 c5 c6 e3 f6 e6 f7 e7 f4 g7
11 50 7 65070  c4
11 250 7 65272  c4
11 450 7 67890  c4
11 500 7 68092  c4 c3 e6 c5 b2 e3 c6 e7 f6 b7 e8
11 500 7 68166  c4 c3 e6 c5 b2 e3 c6 e7 f6 b7 e8
12 450 9 68435  c4
12 250 9 68860  c4
12 50 9 70681  c4
12 0 9 79460  c4 c3 f5 c5 b4 e3 d6 d7 b2 b6 e7 a4
12 0 11 123607  c4 c3 f5 c5 b4 e3 d6 d7 b2 b6 e7 a4
13 50 11 124476  c4
13 250 12 131922  c4
13 -50 12 140396  c4
13 100 12 142744  c4 c3 f5 c5 b3 g5 e6 d7 e7 f7 g8 e3 h5
13 100 12 147212  c4 c3 f5 c5 b3 g5 e6 d7 e7 f7 g8 e3 h5
14 150 14 149344  c4
14 50 14 161975  c4
14 -150 14 172619  c4
14 -200 15 215098  c4 c3 e6 c5 b4 f6 g6 g7 g8 h8 d2 f8 d6 d7
14 0 26 541314  f5 f6 d3 f4 g7 d6 d7 h8 g3 c5 f7 h2 b5 f8
14 0 29 643147  f5 f6 d3 f4 g7 d6 d7 h8 g3 c5 f7 h2 b5 f8
15 50 31 649391  f5
15 250 32 687492  f5
15 300 39 884034  f5 f6 d3 f4 g7 d6 d7 h8 g3 c5 f7 h2 b5 f8 g6
15 300 39 885566  f5 f6 d3 f4 g7 d6 d7 h8 g3 c5 f7 h2 b5 f8 g6
16 250 39 887878  f5
16 50 39 889963  f5
16 -150 42 968813  f5
16 -200 46 1115713  f5 f6 d3 f4 g7 d6 e6 d2 c4 b5 d1 f7 e7 g8 c5 c7
16 0 64 1609839  c4 c3 f5 c5 b5 b6 b3 f6 f7 g7 h7 h8 b7 a7 d3 e3
16 0 76 1960671  c4 c3 f5 c5 b5 b6 b3 f6 f7 g7 h7 h8 b7 a7 d3 e3
17 50 76 1977997  c4
17 250 86 2245345  c4
17 -50 87 2285816  c4
17 300 90 2358103  c4 c3 f5 c5 b2 f4 c6 a1 g3 b7 e3 f6 a8 c7 b4 f3 d6
17 300 90 2361953  c4 c3 f5 c5 b2 f4 c6 a1 g3 b7 e3 f6 a8 c7 b4 f3 d6
18 250 90 2370406  c4
18 50 92 2386194  c4
18 -150 96 2533723  c4
18 0 98 2563347  c4 c3 f5 c5 b2 f4 b5 g6 g5 e6 h7 h5 d3 a5 e7 e2 c6 f6
18 0 162 4422881  c4 c3 f5 c5 b2 f4 b5 g6 g5 e6 h7 h5 d3 a5 e7 e2 c6 f6
19 -50 165 4499099  c4
19 50 167 4557207  c4
19 100 200 5526033  c4 c3 f5 c5 b5 f6 f7 a5 c6 g7 b4 f4 a4 a3 h8 f8 b3 d7 c7
19 100 201 5537802  c4 c3 f5 c5 b5 f6 f7 a5 c6 g7 b4 f4 a4 a3 h8 f8 b3 d7 c7
20 50 203 5589913  c4
20 150 228 6256418  c4
20 -150 367 10245071  c4
20 0 520 14697132  c4 c3 e6 c5 b3 f5 g4 f4 b5 a3 a2 e7 a4 a5 a6 h4 f7 d7 c7 c8
20 0 762 21558033  c4 c3 e6 c5 b3 f5 g4 f4 b5 a3 a2 e7 a4 a5 a6 h4 f7 d7 c7 c8
nodes = 21558033 <30 qnodes> time = 7625ms nps = 2827282
lazy_eval = 0 splits = 0 badsplits = 0
move c4   



            a b c d e f g h i
            * * * * * * * * * * *
          9 . . . . . . . . . * * 9
          8 . . . . . . . . . * * 8
          7 . . . . . . . . . * * 7
          6 . . . . . . . . . * * 6
          5 . . . . . . . . . * * 5
          4 . . . . . . . . . * * 4
          3 . . . . . . . . . * * 3
          2 . . . . . . . . . * * 2
          1 . . . . . . . . . * * 1
            * * * * * * * * * * *
            a b c d e f g h i

        9/9/9/9/9/9/9/9/9 w - - 0 1

go
[st = 5557ms, mt = 29250ms , hply = 0 , moves_left 10]
2 0 0 163  i9 h9
2 0 0 561  i9 h9
3 100 0 884  i9
3 100 0 1048  i9 h9 g9
3 100 0 1152  i9 h9 g9
4 0 0 1474  i9
4 0 0 1835  i9 h9 i8 g9
4 0 1 6886  i9 h9 i8 g9
5 100 1 7625  i9
5 100 1 7948  i9 h9 i8 g9 f9
5 100 1 8649  i9 h9 i8 g9 f9
6 0 1 9065  i9
6 0 1 10342  i9 h9 i8 g9 f9 e9
6 100 4 77710  h9 i9 i8 f6 h8 f9
6 100 4 77886  h9 i9 i8 f6 h8 f9
7 0 4 79589  h9
7 100 6 85173  h9 g9 i9 i8 h8 i7 g8
7 100 6 87589  h9 g9 i9 i8 h8 i7 g8
8 100 7 103083  h9 g9 f9 i8 h8 c9 g8 b9
8 100 14 173133  h9 g9 f9 i8 h8 c9 g8 b9
9 0 15 198351  h9
9 100 18 260376  h9 g9 f9 g8 e9 d6 i9 h8 d9
9 100 29 413594  h9 g9 f9 g8 e9 d6 i9 h8 d9
10 0 31 435259  h9
10 0 31 448515  h9 g9 f9 g8 e9 d6 h8 h7 d9 i9
10 100 46 679673  h8 g9 h9 i8 i9 i7 f9 c9 g8 d9
10 100 61 957462  h8 g9 h9 i8 i9 i7 f9 c9 g8 d9
11 100 75 1176012  h8 g9 h9 f9 g8 e9 c9 d9 i8 b9 i9
11 100 107 1668516  h8 g9 h9 f9 g8 e9 c9 d9 i8 b9 i9
12 0 139 2228522  h8
12 0 143 2294543  h8 g9 h9 f9 g8 e9 c9 d9 i8 b9 c8 a9
12 100 261 4241371  g8 h9 g9 h8 c9 i8 h7 f9 e9 b9 f8 d9
12 100 432 6577926  g8 h9 g9 h8 c9 i8 h7 f9 e9 b9 f8 d9
nodes = 6577926 <25 qnodes> time = 4328ms nps = 1519853
lazy_eval = 0 splits = 0 badsplits = 0
move g8

[UncombedCoconut]

These are my opinions about getting started with a reversi program. If you want to write a very strong one, ignore what I'm about to say! Instead see M. Buro's papers, look at Zebra's web page, and look at the source for GRhino.

Material count is a very weak evaluation function for reversi, and also leads to misleading ideas of quiescence. Reversi search seems to be simpler than chess search: strong techniques need not necessarily compare scores at different depths. Based on my experience: move ordering (including by ID) and pruning (by prob-cut) are crucial. Extensions mostly help a weak eval. Qsearch is basically nonexistent. Null move is a terrible idea, due to both frequent zugzwangs and the effect of "partiy" in the game's strategy.

A starting point is the idea of stable discs. These will actually count toward the eventual score, and can be used to launch attacks during the midgame. Unstable discs are basically worthless and, if on a frontier, are even often harmful. Corners are automatically stable.
Mobility is also a crucial eval term; if you're forced to make a bad move, you usually lose.

So as a starting point, I would recommend: either extend moves next to a corner, or include a big eval penalty for weak corners. Consider extending when a side is forced to pass -- this is the one situation when an extension will reduce the "odd/even" effect. However, it may be unhelpful: if a player has to pass in the midgame, he's probably already losing. Avoid a full qsearch phase, and don't judge a move's impact by the number of discs it flips.

The "midgame", BTW, means the part of the game when it's too early for a program to calculate until the end.

[Daniel Shawul]

Thanks a lot Justin. You certainly cleared up for me what the state-of-the art reversi programs do. It is good to know that mixing of "odd" and "even" plies is not a good idea. I also did not have a qsearch as I didn't think those games would ever quescent. Extensions and reductions mess up the depths one has to make sure the "odd/even" effect is absent. Null move seems generally a bad idea for checkers,reversi and go. Checkers is full of zugzwangs and removing it made my engine stronger.
I will try to look into some literature before I go on.

[frankp]

When i messed with othello a while ago, the number of moves available (mobility I guess) seemed a very important evaluation term.

Buro's evaluation function based on statistical analysis on 'endings' (see the papers mentioned in an earlier post) seems the key to an ultra strong program.

But you might be surprised by how much simple move count helps initially, compared to piece square tables.

[Mark]

Material count is a very weak evaluation function for reversi, and also leads to misleading ideas of quiescence.

I programmed an Othello engine a number of years ago, and material count actually turned out to be a pretty good evaluation factor. The engine would minimize its number of disks, until it could see to the end of the game, and then it would maximize its disks! (I guess minimizing disks is the same as maximizing possible moves.) I don't think I ever did beat it...