Topic Rybka Support & Discussion / Rybka Discussion / On determining an estimate for the number of games in Chess
There has been a really interesting semi-debate going on in the forum over the number of games in Chess--having started from a discussion on Tablebases. I propose the following for arriving at an estimate for the number of games in Chess:
0. Get a multi-million-games count Chess games database.
1. Determine the average length of the games in the database.
2. Create an integer array of that length. Like AvgLen[(65*2)]. Assume the average length of the games is 65 games.
3. Have a program go through the (multi-million-games) database game-by-game, while having a engine count just the number of possible positions move-by-move (ie. position-by-position).
4. Have each position in the AvgLen[] store a running Total and divide at the end to get the averages.
5. Once you have the average number of possible moves for both White and Black for move 1. to eg. avg. move 65. Then multiply those 2*65 numbers together. That = your estimate.
.......................................................
For brevity,
Upon doing an analysis on Chessbase's Mega Database 2010 (filtered for 15 - 150 moves), it appears the average game length is 39. That means 2*39 = 78 numbers are being multiplied together. For a rough estimate here, I am taking the first game in the database with 39 moves and storing the number of moves from Deep Rybka 4 x64's possible moves in Chessbase's Infinite Analysis mode - Engine Kibitzer in an Excel Spreadsheet to multiply the numbers together at the end.....for the very rough estimate here.
Game under analysis:
[Event "London m2"]
[Site "London"]
[Date "1788.??.??"]
[Round "?"]
[White "Von Bruehl, Hans Moritz"]
[Black "Conway, M."]
[Result "1-0"]
[ECO "C23"]
[PlyCount "77"]
[EventDate "1788.??.??"]
[EventType "match"]
[EventRounds "3"]
[EventCountry "ENG"]
[Source "ChessBase"]
[SourceDate "1999.11.16"]
1. e4 e5 2. Bc4 b6 3. d3 Nf6 4. f4 exf4 5. Bxf4 d5 6. exd5 Nxd5 7. Qe2+ Be7 8.
Bxd5 Qxd5 9. Bxc7 Nc6 10. Nf3 Qc5 11. Bg3 O-O 12. Bf2 Qa5+ 13. c3 Bb7 14. O-O
Rfe8 15. Qc2 Qh5 16. Nbd2 Rad8 17. Ne4 Qg6 18. Rad1 Kh8 19. Qb1 f5 20. Ng3 Bf6
21. d4 Ne7 22. Qc1 Bxf3 23. gxf3 Nd5 24. Qc2 f4 25. Qxg6 hxg6 26. Ne4 Re6 27.
Nxf6 gxf6 28. Rfe1 Ne3 29. Bxe3 fxe3 30. Rd3 Rde8 31. Kg2 f5 32. f4 Kg7 33. Re2
g5 34. fxg5 Kg6 35. Kf3 f4 36. h4 Re4 37. d5 R4e7 38. Rd4 Rd7 39. Rxf4 1-0
Drum roll............
Although the game was not finished in checkmate, the number I came to was:
1.1282E+115
Which is in the range of 2^382 to 2^383. ( 2^382 = 9.8505E+114 ..... 2^383 = 1.9701E+115 )
Whereas the total number of Atoms in the Known Universe has been calculated to be approximately 2^80. (as first pointed out to me by poster Labyrinth) (Note from page 1 results Google for "estimated atoms in the universe": http://www.cs.umass.edu/~immerman/stanford/universe.html)
THAT STUFF SEEMS IMPOSSIBLE TO ME!!!
APPARENTLY WE NEED MORE ATOMS!!!!!
I might quit Chess!
0. Get a multi-million-games count Chess games database.
1. Determine the average length of the games in the database.
2. Create an integer array of that length. Like AvgLen[(65*2)]. Assume the average length of the games is 65 games.
3. Have a program go through the (multi-million-games) database game-by-game, while having a engine count just the number of possible positions move-by-move (ie. position-by-position).
4. Have each position in the AvgLen[] store a running Total and divide at the end to get the averages.
5. Once you have the average number of possible moves for both White and Black for move 1. to eg. avg. move 65. Then multiply those 2*65 numbers together. That = your estimate.
.......................................................
For brevity,
Upon doing an analysis on Chessbase's Mega Database 2010 (filtered for 15 - 150 moves), it appears the average game length is 39. That means 2*39 = 78 numbers are being multiplied together. For a rough estimate here, I am taking the first game in the database with 39 moves and storing the number of moves from Deep Rybka 4 x64's possible moves in Chessbase's Infinite Analysis mode - Engine Kibitzer in an Excel Spreadsheet to multiply the numbers together at the end.....for the very rough estimate here.
Game under analysis:
[Event "London m2"]
[Site "London"]
[Date "1788.??.??"]
[Round "?"]
[White "Von Bruehl, Hans Moritz"]
[Black "Conway, M."]
[Result "1-0"]
[ECO "C23"]
[PlyCount "77"]
[EventDate "1788.??.??"]
[EventType "match"]
[EventRounds "3"]
[EventCountry "ENG"]
[Source "ChessBase"]
[SourceDate "1999.11.16"]
1. e4 e5 2. Bc4 b6 3. d3 Nf6 4. f4 exf4 5. Bxf4 d5 6. exd5 Nxd5 7. Qe2+ Be7 8.
Bxd5 Qxd5 9. Bxc7 Nc6 10. Nf3 Qc5 11. Bg3 O-O 12. Bf2 Qa5+ 13. c3 Bb7 14. O-O
Rfe8 15. Qc2 Qh5 16. Nbd2 Rad8 17. Ne4 Qg6 18. Rad1 Kh8 19. Qb1 f5 20. Ng3 Bf6
21. d4 Ne7 22. Qc1 Bxf3 23. gxf3 Nd5 24. Qc2 f4 25. Qxg6 hxg6 26. Ne4 Re6 27.
Nxf6 gxf6 28. Rfe1 Ne3 29. Bxe3 fxe3 30. Rd3 Rde8 31. Kg2 f5 32. f4 Kg7 33. Re2
g5 34. fxg5 Kg6 35. Kf3 f4 36. h4 Re4 37. d5 R4e7 38. Rd4 Rd7 39. Rxf4 1-0
Drum roll............
Although the game was not finished in checkmate, the number I came to was:
1.1282E+115
Which is in the range of 2^382 to 2^383. ( 2^382 = 9.8505E+114 ..... 2^383 = 1.9701E+115 )
Whereas the total number of Atoms in the Known Universe has been calculated to be approximately 2^80. (as first pointed out to me by poster Labyrinth) (Note from page 1 results Google for "estimated atoms in the universe": http://www.cs.umass.edu/~immerman/stanford/universe.html)
THAT STUFF SEEMS IMPOSSIBLE TO ME!!!
APPARENTLY WE NEED MORE ATOMS!!!!!
I might quit Chess!
Depends what you mean by the number of chess games. If you mean the number of chess games possible ... then for sure that is more than the number of atoms in the universe due to how quickly the math progresses as you double and double. But if you mean the number of games for chess to be solved, then things are a lot more manageable. If you have a strong enough chess entity, it will win with 100% probability if the opposing side manages to lose its queen in the opening. You don't have to calculate all the possible moves, because the engine is strong enough to win no matter what the opposing side does. This is probably true also for a rook, and then you might reach a point where today's strongest engine would start scoring around 98% with a bishop or knight advantage. So in other words if you have a strong chess engine or incredible hardware, you will reach opening lines that are won or drawn without having to go through all the possible moves. That is how chess will be solved ... and it will be much earlier than when 32 EGTB's arrive
> If you mean the number of chess games possible
Yes, this was about ALL THE POSSIBLE games.
> ... then for sure that is more than the number of atoms in the universe due to how quickly the math progresses as you double and double.
There is no doubling and doubling here. Only multiplication.
> That is how chess will be solved ... and it will be much earlier than when 32 EGTB's arrive
This PROVES That!!.....so much as Chess CAN be "solved"!
Checkers was solved, but attributably to the fact that the pieces do not have all that many possible moves per position to them!
That and the abundance of forced moves in the rules.
Number of games has nothing to do with solving chess.
Number of possible games starting from known tablebase position is clearly more than 10^100 but they can be solved because the number of chess positions is small enough.
Number of possible games starting from known tablebase position is clearly more than 10^100 but they can be solved because the number of chess positions is small enough.
> If you mean the number of chess games possible ... then for sure that is more than the number of atoms in the universe due to how quickly the math progresses as you double and double.
Understatement of the year. The number of chess games is on the order of 10^(plies(longest game)*lg(average number of legal moves that don't shorten the game)); I'd guess 10^15000.
Alright alright.....
It was about ALL THE POSSIBLE typical games to typical game-length--though perhaps allowing for way too many games with too much extreme blundering--although NOT necessarily just games that use legal moves "[to] not shorten the length of the game". That would generate an even much much larger number--as you've shown by your guess--probably a combination of the 50-move rule and 3-fold repetition rule. (Note, in composition, you can probably always add 50 moves to "the end" of a game. But this is certainly unimportant and nonsense. Since we are near the topic, generally speaking, sometimes to me when talking about possibility and infinance, there seems to be an accompanying infinite amount of nonsense sometimes (or it is just me)).
It was about ALL THE POSSIBLE typical games to typical game-length--though perhaps allowing for way too many games with too much extreme blundering--although NOT necessarily just games that use legal moves "[to] not shorten the length of the game". That would generate an even much much larger number--as you've shown by your guess--probably a combination of the 50-move rule and 3-fold repetition rule. (Note, in composition, you can probably always add 50 moves to "the end" of a game. But this is certainly unimportant and nonsense. Since we are near the topic, generally speaking, sometimes to me when talking about possibility and infinance, there seems to be an accompanying infinite amount of nonsense sometimes (or it is just me
)).
Number of typical game without blunder is also not relevant.
In tablebases position often the side to move has many drawing moves so even if you take all possible games without a blunder from tablebases position you get easily more than 10^50
In tablebases position often the side to move has many drawing moves so even if you take all possible games without a blunder from tablebases position you get easily more than 10^50
Hi Uri,
If the typical games without blunder is not relevant, then CHESS is not relevant!
I guess you are looking at moves which do not decrease the length of the game again. I was trying to exclude that though.
> Number of typical game without blunder is also not relevant.
If the typical games without blunder is not relevant, then CHESS is not relevant!
> In tablebases position often the side to move has many drawing moves so even if you take all possible games without a blunder from tablebases position you get easily more than 10^50
I guess you are looking at moves which do not decrease the length of the game again. I was trying to exclude that though.
I have also tried to estimate the total number of chess games.
First I calculated approximately the maximum length of a chess game.
I considered A] the 50 moves rule and that B] King vs King is draw.
There are 48 pawn moves and it is possible to capture up to 30 pieces: so every 50 moves I have to consume one of these 78 (48+30) moves.
Therefore the maximum game length is: 78*50 = 3900 moves = 7800 plyes
Then I consider the usual average branching factor of 35 and calculate 35^7800 that is equal to 10^12043
...
Uhm... I have just read Vempele's comment...
I think he is right: the average branch factor includes also pawn moves and captures that should not be considered...
Maybe I should half that number: so 17^7800 = 10^9598
I know, I know: my estimation is VERY rough!
First I calculated approximately the maximum length of a chess game.
I considered A] the 50 moves rule and that B] King vs King is draw.
There are 48 pawn moves and it is possible to capture up to 30 pieces: so every 50 moves I have to consume one of these 78 (48+30) moves.
Therefore the maximum game length is: 78*50 = 3900 moves = 7800 plyes
Then I consider the usual average branching factor of 35 and calculate 35^7800 that is equal to 10^12043
...
Uhm... I have just read Vempele's comment...
I think he is right: the average branch factor includes also pawn moves and captures that should not be considered...
Maybe I should half that number: so 17^7800 = 10^9598
I know, I know: my estimation is VERY rough!
> There are 48 pawn moves
96, but 8 of them are captures.
Sigh... (I hate to be wrong )
but you are totally right...
So the new numbers are 17^((96-8+30)*50*2) = 17^(11800) = 10^14519
Your estimation was perfect (if mine is too, of course)
Thank you!
) but you are totally right...
So the new numbers are 17^((96-8+30)*50*2) = 17^(11800) = 10^14519
Your estimation was perfect (if mine is too, of course
)Thank you!
It really does not matter that the universe has less atoms than possible chess games. That in no way limits the possibility of playing all those games. They do not have to be recorded. They can just be counted. They can be played in sequence just fine...it is not like that destroys atoms or anything.
I think the average length of a random selection of possible games is not the same as the average length of a game in a database played by masters. What you actually need is an engine that will play truly random moves from both sides and generate a few billion games; that will give a more realistic estimate of game length. I suspect it is considerably longer than the master games.
You also have to consider forms of loss or draw. Is a loss by forfeiture the same as a loss by resignation, all things being the same. Then are all losses by forfeiture the same or is cell phone ring forfeiture the same as vomiting vodka all over the board and collapsing on the floor, or slapping an opponent while hurling imaginative Arabic curses involving camels, fleas and whatnot, or forfeiture by mooning him, forfeiture by licking his queen and making grunting sounds, there realy is no limit in that case.
You know there will be gazillions of games in which it is mate in one and the wrong side resigns. Who really needs these games played by monkeys?
I think the average length of a random selection of possible games is not the same as the average length of a game in a database played by masters. What you actually need is an engine that will play truly random moves from both sides and generate a few billion games; that will give a more realistic estimate of game length. I suspect it is considerably longer than the master games.
You also have to consider forms of loss or draw. Is a loss by forfeiture the same as a loss by resignation, all things being the same. Then are all losses by forfeiture the same or is cell phone ring forfeiture the same as vomiting vodka all over the board and collapsing on the floor, or slapping an opponent while hurling imaginative Arabic curses involving camels, fleas and whatnot, or forfeiture by mooning him, forfeiture by licking his queen and making grunting sounds, there realy is no limit in that case.
You know there will be gazillions of games in which it is mate in one and the wrong side resigns. Who really needs these games played by monkeys?
Monkey cell phone ring, monkey slap opponent, moon opponent, make grunting sound, lick queen, then vomit vodka and collapse onto floor.
I've completely lost my mind!
P.S. Make sure all of your functions are declared with a __cdecl in them! That way you'll be sure to not not not not waste your time!
I've completely lost my mind!
P.S. Make sure all of your functions are declared with a __cdecl in them! That way you'll be sure to not not not not waste your time!
Topic Rybka Support & Discussion / Rybka Discussion / On determining an estimate for the number of games in Chess
Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill