move transposition question

[Fguy64]

greetings, I am considering various ways to improve the efficiency of my chess engine, such as it is.

OK, consider all the possible positions end points of a 3-ply move tree from the standard start of the game.

According to my calculations, 3,540 of those end points are duplicate positions that can be eliminated.

Does this sound right? intuitively it seems a little high to me.

[Gerd Isenberg]

greetings, I am considering various ways to improve the efficiency of my chess engine, such as it is.

OK, consider all the possible positions end points of a 3-ply move tree from the standard start of the game.

According to my calculations, 3,540 of those end points are duplicate positions that can be eliminated.

Does this sound right? intuitively it seems a little high to me.

The majority of two white moves may be exchanged after three plies from the initial opening position. Only if white moved twice with the same piece, or moves are dependent (f.i. c4 Nc3, d4 Nd2, e4 Bf1-any), they can't transpose. If all white moves would be exchangeable, the number of transpositions would be perft(3)/2. Since perft 3 == 8,902, your 3,540 that is ~40% sounds very reasonable, but I don't have my hash-perft handy to exactly confirm that number.

[Fguy64]

noted. thanks.

[Gerd Isenberg]

noted. thanks.

Oups, "if white moved twice with the same piece" is even wrong. Any two white knight moves back and forth (Nc(a)3 any Nb1, Nf(h)3 any Ng1) would also result in transpositions.

[Fguy64]

noted. thanks.

Oups, "if white moved twice with the same piece" is even wrong. Any two white knight moves back and forth (Nc(a)3 any Nb1, Nf(h)3 any Ng1) would also result in transpositions.

Not as far as I can see, at 3-ply, how can two moves back and forth with the same piece result in transposition If the opponent has only moved once, then we can't possible be back to the original position. So I think you were right the first time. Right?

[Zach Wegner]

noted. thanks.

Oups, "if white moved twice with the same piece" is even wrong. Any two white knight moves back and forth (Nc(a)3 any Nb1, Nf(h)3 any Ng1) would also result in transpositions.

Not as far as I can see, at 3-ply, how can two moves back and forth with the same piece result in transposition If the opponent has only moved once, then we can't possible be back to the original position. So I think you were right the first time. Right?

There's still transpositions. For each black move there are four different white moves that can be executed and retracted on plies 1 and 3.

Example:
1. Nf3 e5 2. Ng1
1. Nh3 e5 2. Ng1
...result in the same position.

[Fguy64]

noted. thanks.

Oups, "if white moved twice with the same piece" is even wrong. Any two white knight moves back and forth (Nc(a)3 any Nb1, Nf(h)3 any Ng1) would also result in transpositions.

Not as far as I can see, at 3-ply, how can two moves back and forth with the same piece result in transposition If the opponent has only moved once, then we can't possible be back to the original position. So I think you were right the first time. Right?

There's still transpositions. For each black move there are four different white moves that can be executed and retracted on plies 1 and 3.

Example:
1. Nf3 e5 2. Ng1
1. Nh3 e5 2. Ng1
...result in the same position.

ah yes, now I see. Of course, you are correct. I misunderstood the previous remark.

[elpapa]

Number of possible chess games at the end of the n-th plie:
1, 20, 400, 8902, 197281, 4865609, 119060324, 3195901860

Number of possible chess diagrams after n plies:
1, 20, 400, 5362, 71852, 815677, 9260610, 94305342

Source:
http://www.research.att.com/~njas/seque ... html#chess

At ply 3 the difference is *drumroll* 3,540!