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.
move transposition question
Moderators: hgm, Rebel, chrisw
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: move transposition question
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 wrote: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.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: move transposition question
noted. thanks.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: move transposition question
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 wrote:noted. thanks.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: move transposition question
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?Gerd Isenberg wrote: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 wrote:noted. thanks.
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: move transposition question
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.Fguy64 wrote: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?Gerd Isenberg wrote: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 wrote:noted. thanks.
Example:
1. Nf3 e5 2. Ng1
1. Nh3 e5 2. Ng1
...result in the same position.
-
- Posts: 814
- Joined: Sat May 09, 2009 4:51 pm
- Location: Toronto
Re: move transposition question
ah yes, now I see. Of course, you are correct. I misunderstood the previous remark.Zach Wegner wrote: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.Fguy64 wrote: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?Gerd Isenberg wrote: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 wrote:noted. thanks.
Example:
1. Nf3 e5 2. Ng1
1. Nh3 e5 2. Ng1
...result in the same position.
-
- Posts: 211
- Joined: Sun Jan 18, 2009 11:27 pm
- Location: Sweden
- Full name: Patrik Karlsson
Re: move transposition question
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!
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!