estimating the number of possible stalemates in perft(n)

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Uri Blass
Posts: 8526
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

estimating the number of possible stalemates in perft(n)

Post by Uri Blass » Sat Feb 18, 2012 10:26 am

perft(19) has at least 9 possible stalemates(both white and black has 3 options to change the order of moves at moves 1-3)

1.c4 2.h4 3.Qa4
1.h4 2.c4 3.Qa4
1.c4 2.Qa4 3.h4

1...h5 2...a5 3...Ra6
1...a5 2...h5 3...Ra6
1...a5 2...Ra6 3...h5



1.c4 h5 2.h4 a5 3.Qa4 Ra6 4.Qxa5 Rah6 5.Qxc7 f6 6.Qxd7+ Kf7 7.Qxb7 Qd3 8.Qxb8 Qh7 9.Qxc8 Kg6 10.Qe6 1/2-1/2

I wonder if people can calculate the number of stalemates in perft(19) and estimate this number for bigger n and the same for checkmates and I wonder if there is some n when the number of stalemates in perft(n) is bigger than the number of checkmates in perft(n).

User avatar
Ajedrecista
Posts: 1395
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Estimating the number of possible stalemates in Perft(n).

Post by Ajedrecista » Sat Feb 18, 2012 11:38 am

Hello Uri:
Uri Blass wrote:perft(19) has at least 9 possible stalemates(both white and black has 3 options to change the order of moves at moves 1-3)

1.c4 2.h4 3.Qa4
1.h4 2.c4 3.Qa4
1.c4 2.Qa4 3.h4

1...h5 2...a5 3...Ra6
1...a5 2...h5 3...Ra6
1...a5 2...Ra6 3...h5



1.c4 h5 2.h4 a5 3.Qa4 Ra6 4.Qxa5 Rah6 5.Qxc7 f6 6.Qxd7+ Kf7 7.Qxb7 Qd3 8.Qxb8 Qh7 9.Qxc8 Kg6 10.Qe6 1/2-1/2

I wonder if people can calculate the number of stalemates in perft(19) and estimate this number for bigger n and the same for checkmates and I wonder if there is some n when the number of stalemates in perft(n) is bigger than the number of checkmates in perft(n).
Have you discovered those stalemates by yourself, without computer help? :o You are a genius! But it surprises me that, once done the most difficult task (by far), which is finding the mainline, then you forget that c3 also does the task (not only c4). So, the minimum number of stalemates for Perft(19) are not 9, but 18, happening with two different final positions: white pawn in c3 and white pawn in c4. I am simply unable of looking for more mainlines, I am not a genius...

I understand that you say that 19 is the minimum number of plies where a stalemate can happen. I have no idea about that, the same as the estimate, that should be clearly difficult: Perft(19) will be around 2.462e+19 according to François Labelle (his estimates are very accurate) and maybe one have to go through each position for verifying if a stalemate happens (only a guess). A huge task for everybody and an impossible task for me. Obviously, I also can not say anything about the comparison between checkmates and stalemates in Perft(n).

In conclusion: no help from mine, but I only can point out that c3 is also valid in your fabulous mainline. Well done!

Regards from Spain.

Ajedrecista.

Uri Blass
Posts: 8526
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Estimating the number of possible stalemates in Perft(n)

Post by Uri Blass » Sat Feb 18, 2012 2:35 pm

I did not find the game that lead to the stalemate by myself and it is a known stalemate for many years.

I believe that I heard about this stalemate many years ago in a chess lecture that happened after a tournament that I played(I think that it was more than 30 years ago but I am not sure)

I did not remember the moves but found them in some chess site today.

http://www.ichess.co.il/viewboard.html#!id=1032

You are right that c3 also achieve the same effect and that there are at least 18 stalemates with 19 plies.

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Estimating the number of possible stalemates in Perft(n)

Post by rjgibert » Sat Feb 18, 2012 4:00 pm

Instead c4, White can play d3 with the idea Qd2, Qxa5 instead Qa4, Qxa5. Later Black will be playing 7...Qxd3 instead of 7...Qd3.

And then there is 1.e3 a5 2.Qh5 Ra6 3.Qxa5 h5 4.h4 ... etc.

Note that White can delay h4 until after Qxc7 before playing h4 in all of these.

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Estimating the number of possible stalemates in Perft(n)

Post by rjgibert » Sat Feb 18, 2012 4:33 pm

rjgibert wrote:Instead c4, White can play d3 with the idea Qd2, Qxa5 instead Qa4, Qxa5. Later Black will be playing 7...Qxd3 instead of 7...Qd3.

And then there is 1.e3 a5 2.Qh5 Ra6 3.Qxa5 h5 4.h4 ... etc.

Note that White can delay h4 until after Qxc7 in all of these.
Fixed last sentence that got mangled.

Post Reply