Tree dumping

[Robert Pope]

I think the biggest thing holding back Beaches right now is the ridiculous number of nodes it is searching at each ply.

I finally have an ideal candidate to dig into why my node counts are so terrible: WAC 232. Both Crafty and Beaches find the critical move at depth 6. The big difference is that Crafty finishes depth 6 in 75,000 nodes, and Beaches finishes depth 6 in just over 4,000,000 nodes.

So now the hunt to find the culprit begins. Quiescence? Extensions? Null-move? Alpha-Beta itself? Time for some tree dumps...

I compiled a Crafty with the trace command enabled, but it looks like the output goes to the screen, but not to the log file, like I would have expected. How can I save the tree dump? It scrolls off the screen in an instant.

[bob]

I think the biggest thing holding back Beaches right now is the ridiculous number of nodes it is searching at each ply.

I finally have an ideal candidate to dig into why my node counts are so terrible: WAC 232. Both Crafty and Beaches find the critical move at depth 6. The big difference is that Crafty finishes depth 6 in 75,000 nodes, and Beaches finishes depth 6 in just over 4,000,000 nodes.

So now the hunt to find the culprit begins. Quiescence? Extensions? Null-move? Alpha-Beta itself? Time for some tree dumps...

I compiled a Crafty with the trace command enabled, but it looks like the output goes to the screen, but not to the log file, like I would have expected. How can I save the tree dump? It scrolls off the screen in an instant.

I usually just do "crafty >bad.log" or something similar to send the output to wherever stdout is redirected to.

You didn't mention which version of Crafty, if you are talking about the last 20.x versions, they did null-move + search reductions, which can greatly reduce the size of the tree... But you are on the right path, the trace output will "tell the tale".

[Robert Pope]

I did the first comparison with Crafty19_20, but I enabled trace on Crafty20_14. Is it worth digging out older source code for a fairer comparison? Beaches is pretty vanilla still (nullmove r=2 plus some extensions).

[bob]

I did the first comparison with Crafty19_20, but I enabled trace on Crafty20_14. Is it worth digging out older source code for a fairer comparison? Beaches is pretty vanilla still (nullmove r=2 plus some extensions).

The advantage to the 19.x is there are no "reductions"... if you are not yet doing them, the 19.x trace will be more representative...

[FrancoisK]

I think the biggest thing holding back Beaches right now is the ridiculous number of nodes it is searching at each ply.

I finally have an ideal candidate to dig into why my node counts are so terrible: WAC 232. Both Crafty and Beaches find the critical move at depth 6. The big difference is that Crafty finishes depth 6 in 75,000 nodes, and Beaches finishes depth 6 in just over 4,000,000 nodes.

So now the hunt to find the culprit begins. Quiescence? Extensions? Null-move? Alpha-Beta itself? Time for some tree dumps...

I compiled a Crafty with the trace command enabled, but it looks like the output goes to the screen, but not to the log file, like I would have expected. How can I save the tree dump? It scrolls off the screen in an instant.

Other very likely candidates in my experience :
- move ordering
- evaluation (the nastiest )

Cheers
François

[Ratta]

Hi, what do you mean exactly with "evaluation", that the evaluation itself is affecting the number of nodes require for a search at ply x?
Actually i have experienced some problem like this in Rattatechess, looks like that a bad evaluation function will make the search at ply (x-1) less effective for getting a good move ordering at ply x, and i think that this is a very difficult problem to solve in general.
Is there any standard technic to face this problem? i mean, better than tuning and tuning the evaluation function by hand?
Regards.

[FrancoisK]

>Hi, what do you mean exactly with "evaluation", that the evaluation itself is affecting the number of nodes require for a search at ply x?

Yes. Evaluation and move ordering are of course closely linked.
For instance, the more your evaluation at ply X is able to predict what will happen in you search at ply X+1, the less costly changes of mind your search will have.
If you have an evaluation that always returns 0, you will have a perfectly ordered tree whatever you move ordering (it might play questionable moves though )

>Actually i have experienced some problem like this in Rattatechess, looks like that a bad evaluation function will make the search at ply (x-1) less effective for getting a good move ordering at ply x, and i think that this is a very difficult problem to solve in general.
>Is there any standard technic to face this problem? i mean, better than tuning and tuning the evaluation function by hand?

I wish i knew one
The hard thing is to make your eval knowledgable enough but with clear cut views on how to make progress.
A very intereresting post by Tord Romstad : http://64.68.157.89/forum/viewtopic.php ... d1a11aec40

François

[Uri Blass]

Hi, what do you mean exactly with "evaluation", that the evaluation itself is affecting the number of nodes require for a search at ply x?
Actually i have experienced some problem like this in Rattatechess, looks like that a bad evaluation function will make the search at ply (x-1) less effective for getting a good move ordering at ply x, and i think that this is a very difficult problem to solve in general.
Is there any standard technic to face this problem? i mean, better than tuning and tuning the evaluation function by hand?
Regards.

Bad evaluation is not a reason for the problem that was described.

getting 4,000,000 nodes at depth 6 is because of search problems and not because of evaluation.

Even without null move pruning and with piece square table evaluation you should do better than it.

Uri

[Ratta]

@François: Thanks for your interesting answer, and for the link to Tord's post (Tord you rule, you are really one of the few people with the true interest of developing chess-programming knowledge rather than being jelous of a couple a of secret tricks, and i deeply admire you while trying to do the same).

@Uri: Yes of course you are right, i just took the opportunity to talk about this issue, even if it may be slightly offtopic. Maybe the discussion could be moved to a saparate thread (if it is worth).

[Robert Pope]

I expect the issue is in the search somewhere, like Uri said. I thought I had reasonable ordering rules, and I thought I had null-move working, but we'll see.

Qsearch doesn't seem to be the culprit -- I turned it off and only saved 50%, which doesn't look too unreasonable, but that still leaves 2M nodes too many.

I've already identified one improvement: when I fail high, I re-search with a wider window, but I didn't reorder to move the fail-high move to the front of the list.