Going crazy over Glaurung...

[Alessandro Scotti]

Yesterday I noticed Glaurung goes deep very quickly from the start position, here's a version I compiled without futility:

Code: Select all

info depth 2 score cp 11 time 5 nodes 46 nps 9200 pv g1f3 g8f6 
info depth 3 score cp 54 time 10 nodes 185 nps 18500 pv g1f3 g8f6 b1c3 
info depth 4 score cp 11 time 17 nodes 429 nps 25235 pv g1f3 g8f6 b1c3 b8c6 
info depth 5 score cp 15 time 35 nodes 979 nps 27971 pv g1f3 g8f6 b1c3 b8c6 d2d3 
info depth 6 score cp 11 time 74 nodes 2284 nps 30864 pv g1f3 g8f6 b1c3 b8c6 d2d3 d7d6 
info depth 7 score cp 25 time 170 nodes 5527 nps 32511 pv g1f3 g8f6 b1c3 b8c6 e2e3 d7d6 f1d3 
info depth 8 score cp 11 time 328 nodes 10832 nps 33024 pv g1f3 g8f6 b1c3 b8c6 e2e3 e7e6 f1d3 f8c5 
info depth 9 score cp 56 time 1465 nodes 48045 nps 32795 pv g1f3 g8f6 b1c3 e7e6 e2e3 f8d6 f1d3 e8g8 e1g1 
info depth 10 score cp 11 time 2416 nodes 80051 nps 33133 pv g1f3 g8f6 b1c3 e7e6 e2e3 f8d6 f1d3 e8g8 e1g1 b8c6 

So at depth 4 it has a score in ~430 nodes and terminates the search in ~750 nodes, it has a score at depth 10 after little more than 80K nodes.
Now normally I wouldn't show you something so horrible but I need your help so please resist and take a look at Hamsters:

Code: Select all

info time 30 depth 2 seldepth 3 score cp 16 nodes 48 pv g1f3 g8f6
info time 30 depth 3 seldepth 3 score cp 38 nodes 206 pv g1f3 g8f6 b1c3
info time 32 depth 4 seldepth 8 score cp 16 nodes 709 pv g1f3 g8f6 b1c3 b8c6
info time 36 depth 4 seldepth 12 nodes 1635
info time 38 depth 5 seldepth 12 score cp 21 nodes 2417 pv g1f3 g8f6 b1c3 b8c6 e2e4
info time 43 depth 5 seldepth 12 nodes 4205
info time 49 depth 6 seldepth 14 score cp 16 nodes 6202 pv g1f3 g8f6 b1c3 b8c6 e2e4 d7d5
info time 73 depth 6 seldepth 15 nodes 13416
info time 83 depth 7 seldepth 15 score cp 19 nodes 17062 pv g1f3 g8f6 b1c3 b8c6 d2d4 d7d5 c1f4
info time 117 depth 7 seldepth 15 nodes 28184
info time 147 depth 8 seldepth 17 score cp 16 nodes 37923 pv g1f3 g8f6 b1c3 b8c6 d2d4 d7d5 c1f4 c8f5
info time 305 depth 8 seldepth 20 nodes 87235
info time 363 depth 9 seldepth 20 score cp 12 nodes 106675 pv g1f3 g8f6 b1c3 b8c6 e2e3 d7d5 f1d3 c6b4 d3b5 c8d7
info time 618 depth 9 seldepth 22 nodes 189086
info time 973 depth 10 seldepth 22 score cp 16 nodes 266243 pv g1f3 b8c6 d2d4 d7d5 c1f4 c8f5 e2e3 e7e6 b1c3 g8f6
info time 1259 depth 10 seldepth 22 score cp 18 nodes 356951 nps 283519 pv d2d4 g8f6 b1c3 b8c6 g1f3 d7d5 c1f4 c8f5 c3b5 a8c8
info time 1444 depth 10 seldepth 22 nodes 417864 nps 289379

The difference is not just big, it is insane. At the end of iteration 8 I've already spent more nodes than Glaurung is using at iteration 10, and things get only worse as the search depth increases (please look only at the node count, time is meaningless here).

I've spent some time looking at the search tree at depth 4, which is small enough, and it seems to me that null move makes a big difference for Glaurung. This is the part that I would like you to comment and possibly test with your engine.

At this point:

Code: Select all

info depth 4 score cp 11 time 126 nodes 399 nps 3166 pv g1f3 g8f6 b1c3 b8c6 

Glaurung spends a few more nodes looking at some not-so-bad moves then comes to b3. Here it seems to me it just null moves after this move and prunes the entire subtree. Same thing after b4, c3, c4, f3, f4, g3, g4. This saves an enourmous amount of nodes, but how to get a null move cutoff after say c4? It doesn't look like a bad move that can be refused by null moving to me, so there must be something I don't understand, or maybe I did another mistake somewhere... what do you say?

P.S. Out of curiosity, I added +8 to the value returned by the null move search to simulate some additional cutoffs and indeed I get node counts comparable to those of Glaurung.

[Tord Romstad]

Glaurung spends a few more nodes looking at some not-so-bad moves then comes to b3. Here it seems to me it just null moves after this move and prunes the entire subtree. Same thing after b4, c3, c4, f3, f4, g3, g4. This saves an enourmous amount of nodes, but how to get a null move cutoff after say c4? It doesn't look like a bad move that can be refused by null moving to me, so there must be something I don't understand, or maybe I did another mistake somewhere... what do you say?

The secret is very simple: Glaurung's evaluation function is atrocious. The static evaluation gives black a slight advantage after 1. c4. It is no wonder that the move is refuted by a null move.

As an experiment, I ran Glaurung in MultiPV mode (not supported in 2 - ε/5, but implemented in recent development versions) from the opening position to see how it ranks the moves. As you can see, it thinks c4 is a quite bad move:

Code: Select all

Depth 2:
Nf3 (11) Nc3 (7) Nh3 (-23) Na3 (-27) d3 (-29) e3 (-29) d4 (-33) e4 (-33) 
h4 (-52) b3 (-58) g3 (-58) h3 (-58) a4 (-60) c4 (-60) a3 (-62) c3 (-62) 
b4 (-66) g4 (-66) f3 (-78) f4 (-84) 

Depth 3:
Nf3 (54) Nc3 (54) Nh3 (19) Na3 (19) d3 (19) e3 (15) d4 (13) e4 (9) h3 (-3) 
h4 (-5) g3 (-11) b3 (-11) a3 (-11) c4 (-13) a4 (-13) c3 (-15) f3 (-35)
f4 (-37) g4 (-72) b4 (-80) 

Depth 4:
Nf3 (11) Nc3 (11) d3 (-23) Na3 (-23) Nh3 (-23) e3 (-27) d4 (-29) e4 (-33)
h3 (-47) h4 (-49) a3 (-54) b3 (-54) g3 (-54) a4 (-56) c4 (-56) c3 (-58) 
f3 (-78) f4 (-80) b4 (-94) g4 (-98) 

Depth 5
Nf3 (15) Nc3 (15) d3 (15) e3 (15) d4 (7) e4 (7) Nh3 (1) Na3 (1) h3 (-3) 
h4 (-5) a3 (-7) g3 (-11) b3 (-11) c4 (-13) a4 (-13) f4 (-37) c3 (-39) 
f3 (-54) g4 (-68) b4 (-76) 

Depth 6
e3 (11) d3 (11) Nf3 (11) Nc3 (11) d4 (5) e4 (5) Na3 (-3) Nh3 (-3) h3 (-7)
 h4 (-9) a3 (-11) g3 (-15) b3 (-15) a4 (-17) c4 (-17) f4 (-41) c3 (-45) 
f3 (-60) b4 (-68) g4 (-84) 

Depth 7
e3 (25) Nf3 (25) Nc3 (25) d3 (21) d4 (19) e4 (19) Nh3 (1) Na3 (-1) 
c4 (-1) h3 (-3) h4 (-5) g3 (-5) a3 (-7) b3 (-9) a4 (-13) f4 (-25) 
c3 (-25) b4 (-39) f3 (-41) g4 (-62) 

Depth 8
e3 (11) Nf3 (11) Nc3 (11) d3 (7) e4 (5) d4 (5) Na3 (-9) Nh3 (-13) c4 (-17) 
h3 (-17) h4 (-19) g3 (-21) a3 (-21) b3 (-25) a4 (-27) g4 (-41) c3 (-50) 
f3 (-56) f4 (-72) b4 (-80) 

Depth 9
e3 (45) Nf3 (45) Nc3 (45) e4 (27) Nh3 (5) d4 (-1) h3 (-3) g3 (-5) d3 (-7) 
Na3 (-7) h4 (-7) a3 (-7) c4 (-9) b3 (-11) a4 (-13) f4 (-27) c3 (-39) 
g4 (-45) f3 (-52) b4 (-74) 

Depth 10
e3 (11) Nf3 (11) Nc3 (11) d4 (5) e4 (1) Na3 (-5) d3 (-7) Nh3 (-9) h4 (-23) 
h3 (-39) a3 (-41) g4 (-43) b3 (-47) g3 (-50) a4 (-54) c4 (-58) c3 (-60) 
f4 (-68) b4 (-76) f3 (-86) 

Depth 11
e3 (37) Nc3 (37) Nf3 (19) d4 (3) e4 (3) Nh3 (3) a3 (-7) b3 (-11) a4 (-13) 
Na3 (-17) d3 (-19) c4 (-23) h3 (-25) f4 (-25) g3 (-31) h4 (-39) g4 (-43) 
c3 (-43) f3 (-72) b4 (-84) 

Depth 12
e3 (21) Nc3 (21) Nf3 (21) e4 (19) d4 (17) Na3 (-7) Nh3 (-13) d3 (-15) 
b3 (-21) a4 (-23) g3 (-29) a3 (-33) f4 (-33) h3 (-33) h4 (-35) g4 (-45) 
c4 (-49) c3 (-50) b4 (-60) f3 (-80) 

Depth 13
Nc3 (21) Nf3 (21) e4 (21) e3 (11) d4 (7) Na3 (-13) Nh3 (-15) a3 (-15) 
d3 (-21) h3 (-21) g3 (-25) f4 (-29) b3 (-31) a4 (-31) h4 (-37) g4 (-39) 
c4 (-56) c3 (-56) f3 (-74) b4 (-82) 

Depth 14
e4 (25) Nc3 (25) Nf3 (25) d4 (25) e3 (11) a3 (-15) d3 (-15) c4 (-17) 
Na3 (-19) b3 (-19) g3 (-21) f4 (-23) a4 (-25) Nh3 (-27) h3 (-27) c3 (-35) 
h4 (-41) g4 (-43) f3 (-66) b4 (-66) 

Depth 15
d4 (27) e4 (25) Nf3 (25) Nc3 (23) e3 (23) d3 (-9) Na3 (-13) a3 (-19) 
g3 (-19) b3 (-23) a4 (-23) f4 (-27) Nh3 (-27) h3 (-27) c4 (-35) c3 (-35) 
g4 (-37) h4 (-43) b4 (-70) f3 (-80) 

Depth 16
e4 (41) d4 (25) Nf3 (25) e3 (25) Nc3 (13) Na3 (-11) g3 (-15) a3 (-15) 
b3 (-17) d3 (-21) a4 (-25) Nh3 (-27) c4 (-29) c3 (-31) h3 (-33) f4 (-33) 
h4 (-37) g4 (-41) b4 (-84) f3 (-90)

As you can see, the score for c4 is negative for all depths from 2 to 16, and even at depth 16, it is ranked below moves like Na3, a3, Nh3 and a4. It is painful to see just how bad my evaluation function is. On the plus side, there is a chance that my program will play quite good chess if I finally get around to fix the eval.

Tord

[Tony]

Looking at Tords output, it seems he gives minus points for Knights and Bishops on the backline, d and e pawn on there original square. In addition a bonus for d-e pawn in the centre, will make you reach 10 ply from opening very fast.

Any move not minimizing the disadvantages I mentioned will be pruned. (fe c4)

Cheers,

Tony

[Michael Sherwin]

I do not think that you can judge what you are trying to judge by just looking at one position. There are so many factors that come into play that determines how many nodes it takes to reach a certain depth that it all depends how they balance out in any given position. Fruit also does very well in the opening position, however, Fruit and Glaurung come down to earth (at least most of the way) as soon as a few key opening moves have been made. Both programs must be very opinionated about a few key opening moves that it allows their move ordering to be very good in the early stages of the game.

An idea to try, is to do some type of static eval to determine which moves look good in any given position and then bonusing the piece square tables for those moves. If the best move turns out to be one of the few that were bonused then the search was likely to be more efficient.

[Michael Sherwin]

A quick experiment in eval guided move ordering (I have no better terminology)!

First a note:

In move ordering, after the killers are tried, Romi shallow searches all remaining moves and captures using an open window for each move to get an accurate score. These nodes are counted and I have no idea what their contribution is to the overall number of nodes needed to reach depth.

RomiChess before the changes:

nodes to depth 10 503,057
time 0.359 seconds

nodes to depth 14 27,395,051
time 17.735 seconds

RomiChess after the changes:

nodes to depth 10 235,146
time 0.172 seconds

nodes to depth 14 10,295,131
time 6.657 seconds

And the changes were:

In the root search, just before making a move:

Code: Select all

if(computer == WHITE) 
  wEvalBonus = piece[id].tbl[ts] - piece[id].tbl[fs];
else
  bEvalBonus = piece[id].tbl[ts] - piece[id].tbl[fs];

In the regular search only at ply 1, just before making a move:

Code: Select all

if(computer == WHITE) 
  bEvalBonus = piece[id].tbl[ts] - piece[id].tbl[fs];
else
  wEvalBonus = piece[id].tbl[ts] - piece[id].tbl[fs];

In the eval just before returning a score:

Code: Select all

score += (wEvalBonus - bEvalBonus);

Okay, it plays like crap, but it is really fast. Maybe the begginnings of an idea here!

[Alessandro Scotti]

Thanks for the explanations guys, I think I understand this better now. Too bad I still don't have some "secret" ingrediente to add to Hamsters, the only practical suggestion was to write an "atrocious" evaluation and I already have it!

[FrancoisK]

Hi Alessandro,

Funny, I did the same kind of experiment about 1 month ago
I tried to understant why Glaurung, on the several positions taken from BugChess2 games went deeper by 2 to 4 sometimes more plies.
To be able to compare plies, and to see if the difference came from better pruning/Hash table scheme, I disabled Null move, LMR, Hash table, futility pruning in Glaurung (last version) and BugChess2.

The ply difference had narrowed a little but not really significantly. I finally came to the conclusion I feared most : apart from bugs in Bug (or unspot tricks in Glaurung !), all comes from the evaluation !

So i do not think Tom's evaluation is atrocious, it seems very well tuned (at least more than mine) for Glaurung's search and only have what it takes to play at a very good level. The challenge will be to improve it without losing too much depth...

I have no idea how to tune my evaluation so as to reduce the branch ratio except by trial and error. Is improving my evaluation at fixed depth linked in any way with improving its selectivity and how so ? Not an easy matter...

Cheers

François

[Alessandro Scotti]

Hi François,
next thing I want to try is to take Glaurung piece/square tables and material values and put them into Hamsters, then limit evaluation just to material + PST. This should make the search very comparable. If the two come out more or less the same I'll be fully convinced it's all in the evaluation!

[Eelco de Groot]

The ply difference had narrowed a little but not really significantly. I finally came to the conclusion I feared most : apart from bugs in Bug (or unspot tricks in Glaurung !), all comes from the evaluation !

Well, actually I think it is a hopeful conclusion because the evaluation function of a program is the part that has the most to do with chess, the most understandable part for non-programmers or just beginning programmers I supose too, and adding knowledge to it should hopefully improve play at all levels, not just by searching deeper in positions the program does not really understand. If good knowledge actually makes the pruning more efficient then I think there is room for improvement for many programs possible, no matter how the rest of their search-structure works. But that is all just in theory I suppose.

Regards, Eelco

So i do not think Tom's evaluation is atrocious, it seems very well tuned (at least more than mine) for Glaurung's search and only have what it takes to play at a very good level. The challenge will be to improve it without losing too much depth...

I have no idea how to tune my evaluation so as to reduce the branch ratio except by trial and error. Is improving my evaluation at fixed depth linked in any way with improving its selectivity and how so ? Not an easy matter...

Cheers

François

[brianr]

Also note that Glaurung does some potentially significant evaluation scaling right at the end. In particular, beyond the midgame and endgame phase scaling it finally does this:

Code: Select all

const int GrainSize = 4;
...
return Value(int(result) & ~(GrainSize - 1));

This may tend to minimize the "noise" of minor evaluation differences and score more positions equally, which should increase null-window cut-offs?