Deep analysis can it be improved

  

Back to forum


Attila Ba    (2013-05-15)
Deep analysis - can it be improved?

The idea behind deep analysis is to store engine evaluations of chess positions in a permanent way and build an analysis tree out of them. Deep analysis is an improvement over simple engine analysis in two ways:

1) Permanent storage of analysis results makes them reusable. You don't have to analyse the same position from scratch over and over again (which is a waste of valuable CPU resources) rather you can build and improve upon your earlier results.

2) The search is configurable. You have control over which positions are examined and in what way. This gives you freedom to tailor the analyis to your own needs not having to rely on the defaults provided by your engine.

This idea is presented in a revolutionary way in the Deep Rybka Aquarium GUI. However using this framework I have encountered some problems. The lesser one and non lethal one is that draws by repetition are not handled correctly. This is for a reason: moves in the transposition table should be valued in an absolute way (regardless of the line which lead to them) in order to preserve the integrity of the tree. Since Aquarium has no means to incorporate lines, it simply ignores them

My other problem is that though the search is configurable I'm not absolutely certain about what is going on. It is not entirely clear to me exactly which nodes are selected for analysis.

These problems made me to try to come up with a deep analyis program of my own. After several failed attempts finally I have on my hand a solution which is not only capable of performing deep analysis but overcomes some of the difficulties of Interactive Deep Analyis (IDeA) provided by the Aquarium framework.

First I introduced a mechanism that can handle repetitions. In order to achieve this I attribute not one but two scores to each move and re-define the concept of root position already present in IdeA. The first score which I call 'idea' score is the same as presented in IdeA. The second is what I call 'alpha' score is calculated by minimaxing the tree from the root position taking into account repetitions.

Consider the following game:

1. Nf3 Nf6 2. Ng1 Nf8

The value of move 2. ... Nf8 at depth 18 by Houdini 3.0 is -19 centipawns. So the idea score of this move at depth 0 should be -19. Yet 2. ... Nf8 repeats the starting position. Therefore its alpha score with respect to a root equaling the starting position should be 0 centipawn which is exactly what my program calculates for it. ( For the sake of simplicity I don't require threefold repetition, since you would never allow your opponent to repeat a position if you have better ideas. )

So when my programs lists the tree it will present both scores for every move (which in most of the cases are equal of course - therefore this is mostly an aesthetic improvement rather than being a substantial one).

The improvement which I'm most interested in is that having full control of node selection now I have freedom to shape the tree search.

In order to keeps things simple I have only three parameters characterising the search:

1) engine depth
2) move distance (centipawns)
3) search depth

Engine depth means a fixed depth at which each move is analyzed. After long experimenting I have arrived at depth 18 as a good default for Houdini 3.0.

Move distance is a tolerance up to which moves are allowed into the analyis. For each position first the best move is determined. The search for alternative moves is continued until a move is found that has a valuation less than the valuation of the best move by 'move distance' centipawns (it is this 'distance' away from being the best move). The tree is then expanded for moves within 'move distance'.

To compensate for exponential growth of analyzed nodes I use a simple technique: at each ply after ply 1 the move distance is halved. So if the move distance at ply 0 and ply 1 is 20 centipawns, it will be 10 centipawns for ply 2, 5 centipawns for ply 3 and so on. This means that at greater depth less and less moves are allowed per position. So the analysis with greater depth slowly evolves into 'autoplay' rather than 'tree search'.

The other method to reduce exponential growth is the well known beta cut provided by alphabeta search. In order that all candidate moves in the root position and all candidate responses to them get proper values, I only allow beta cuts with ply 2 and deeper.

Once an alphabeta search of certain depth is carried out, the whole tree is mimimaxed out for the root. Now the initial evaluations of the root moves may change. This may make moves which initially fall out of the 'move distance' to become viable. So the search has to be repeated for those moves as well. This has to be done at every ply level.

My iterative search at a certain depth only ends when no new nodes are added by the alphabeta search (the tree is 'settled' for this depth). Only then the program is allowed to deepen the search (this I call 'refined' search).

With engine depth of 18 and move distance of 10 centipawns an average position can be analyzed to depth 10 within a matter of hours. This means a couple of hundred (possibly a couple of thousand) positions are analyzed to depth 18. Depth 10 deep analyis means an ultimate depth of 28 if you take into account that the engine depth is 18.

Whether this method has added ELO value over simple engine search is yet to be tested.