question about tablebases(number of positions in a tree)

[Uri Blass]

Define for every tablebase position P function F(P) that is the number of possible legal positions that can be achieved in a game against some perfect player when the perfect player play with white(perfect player can be a program that use tablebases).

Is there a program to calculate F(P)?
Note that we already have a perfect player based on tablebases.

Note that it is possible to build a program that can calculate F(P)

play all the possible games of 1 ply from position P(1 if it is white to move).
You get list of positions P(1) all of them are new .
save all the new positions in the hash.

play all the possible game of 1 ply from P(1)
You get a list of positions P(2) all of them are new because there cannot be repetition in 2 plies
save the new positions in P(2) in the hash.

Generally play all the possible games of 1 ply from P(N)
You get list of positions
part of them may be old.
Denote P(N+1) as only the new positions that you get and save them in the hash.

You stop the process only when P(N) is empty.

Now the question is how many positions you practically get?

If we know how many position we need to prove the result of some 6 piece tablebases then we maybe can use it to get an idea how many positions we need to solve chess.

It is clear that not all positions are relevant because if you start from white king a1 rook b2 black king c3 then common sense tell me that you will never get a position when the white king is at e1 and the black king at e8 but I also believe that the number of positions is bigger than the square root of the number of legal tablebases positions.

The question is interesting because of some discussion in the rybka forum for the question how many positions are needed to solve chess.

I think that we can start with the question how many positions are needed to prove solution of specific tablebases positions.

Uri

[hgm]

Basically you are asking for the size of a refutation tree with hashing, so that any transpositions are only counted as one position. It is the latter requirement that makes it difficult to answer. Without hashing, F(P) could be defined recursively as the sum or the minimum (depending on if the all-side or cut-side has the move) of the size of the successor F(P)s, and you could easily build it together with the DTM through the normal retrograde algorithm, for all possible positions.

Note that with hashing the desire to achieve 'perfect play' (i.e. go for fastest mate) might be conflicting with the desire to have a minimal number of positions in the refutation tree. A deviation of the opponent that leads to a faster win, might add an entirely new set of positions to the tree for that quicker path, while you might have the alternative to force him back on the original, longer path.

[jwes]

The problem is with tablebases that are drawn or mostly drawn. Almost all of the drawn positions could occur. The same thing applies to the opening position. If it is drawn, it will be much harder to solve chess.