PDA

View Full Version : Computers 'solve' chess



Maxwell843
08-10-2007, 02:58 PM
Recently a computer program was created that 'solved', that is it was unbeatable at, checkers. The perfect game being a draw.

I wonder if a similiar result will happen in chess. I know chess is thousands of times more complex than checkers but as computers continue to evolve will they end up 'solving' chess.

Computers in the last decade have overtaken human ability and the best progams like Zappa and Rykba are now virtually unbeatable by humans.

So I guess the real question is what impact will the continued improvement in chess programs have for human chess? I know they contribute so much to opening theory and other facets of the game.

But one day will computers be able to prodcue the 'perfect' game?

CameronD
08-10-2007, 03:12 PM
http://www.xs4all.nl/~timkr/chess2/honor.htm

Personally, I believe that computers are cheating by having an infinite game database and endgame database, which the player is not allowed to have (dont mind the opening books though). i see it the same as if the computer sat down at the table with a pile a books at his side (which is against the rules of chess). The best answer would be to allow the human player to have the same resources/open book, or remove the computers memory to just openings and basic endgame knowledge.

Aaron Guthrie
08-10-2007, 03:17 PM
I know chess is thousands of times more complex than checkers but as computers continue to evolve will they end up 'solving' chess. If by "thousands" you mean "1000000,000000,000000,000000,000000", then yes, it is.

Aaron Guthrie
08-10-2007, 03:20 PM
Emphasis mine.
Personally, I believe that computers are cheating by having an infinite game database and endgame database, which the player is not allowed to have (dont mind the opening books though).And I thought the opening post was out by orders of magnitude! :P

Rincewind
08-10-2007, 03:45 PM
Emphasis mine.And I thought the opening post was out by orders of magnitude! :P

Perhaps we should add to the mangled sayings thread something on the misappropriation of the term "infinite".

Aaron Guthrie
08-10-2007, 04:03 PM
Perhaps we should add to the mangled sayings thread something on the misappropriation of the term "infinite".My edit in that post was fixing "magnitudes of order".

eclectic
08-10-2007, 04:43 PM
i've heard it said that processors are now supposedly as intelligent as an ant or a bee so may we please have have a thread on their chess solving abilities

:eek: :hmm: :uhoh:

DanielBell
08-10-2007, 05:29 PM
i've heard it said that processors are now supposedly as intelligent as an ant or a bee so may we please have have a thread on their chess solving abilities

:eek: :hmm: :uhoh:

You mean to tell me a machine with the intelligence of an ant beats me at chess?

Thanks man, thanks.

Davidflude
08-10-2007, 09:22 PM
Recently a computer program was created that 'solved', that is it was unbeatable at, checkers. The perfect game being a draw.

I wonder if a similiar result will happen in chess. I know chess is thousands of times more complex than checkers but as computers continue to evolve will they end up 'solving' chess.

Computers in the last decade have overtaken human ability and the best progams like Zappa and Rykba are now virtually unbeatable by humans.

So I guess the real question is what impact will the continued improvement in chess programs have for human chess? I know they contribute so much to opening theory and other facets of the game.

But one day will computers be able to prodcue the 'perfect' game?

Sorry but I have tried computers von arious completed correspondence games including world championship games and they can play anywhere from brilliant to useless in the same game. Saw a game recently where two very strong engines wanted to play a move that humans would consider inferior. I suspect because on of the chess heuristics coded into the programs was "do not move your king other than castling in the opening

Rincewind
10-10-2007, 09:03 AM
I wonder if a similiar result will happen in chess. I know chess is thousands of times more complex than checkers but as computers continue to evolve will they end up 'solving' chess.

Out of interest I have dug up an except from Littlewood's Miscellany where he gives an upper bound no the number of games of chess. The upper bound he proposes is 10^10^70.5 which is enormous.

Given more time I'll try to provide a sketch of his argument. But if anyone wants to beat me to the punch, it's on pp.105-107 of Littlewood's Miscellany, revised ed.

Aaron Guthrie
10-10-2007, 02:23 PM
Out of interest I have dug up an except from Littlewood's Miscellany where he gives an upper bound no the number of games of chess. The upper bound he proposes is 10^10^70.5 which is enormous.You might even say that "is big. REALLY big. You just won't believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think it's a long way down the street to the chemist, but that's just peanuts..."

The number I gave was computed via number of positions, which wiki gave (http://en.wikipedia.org/wiki/Game-tree_complexity) 10^20 for Checkers, and 10^50.

Rincewind
10-10-2007, 03:08 PM
The number I gave was computed via number of positions, which wiki gave (http://en.wikipedia.org/wiki/Game-tree_complexity) 10^20 for Checkers, and 10^50.

Ah yes, obviously there are far fewer position then there are games. However 10^50 would seem to be rough.

Firstly the number says it is taken from a celebrated paper by Shannon (http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon .062303002.pdf) in the 50's who (as far as I can tell) gave the number as 10^43, however there were a number of approximations. Fristly he just considered distributing a chess set over a chess board without accounting for pawn promotion and positions which cannot legally occur (e.g. a major one being pawns cannot occur on the first or last ranks).

Shannon's estimate on the game tree size as 10^120 needs to be read within context, as Shannon offers it as a conservative representative estimate, not even a whole-hearted attempt at a lower bound.

I think Littlewood also says something about the number of positions and I might get to posting that when I get home tonight too.

I should also point out that I have been referring to Littlewood the mathematician who is distinct from Littlewood the chess player.

Aaron Guthrie
10-10-2007, 04:38 PM
Ah yes, obviously there are far fewer position then there are games. However 10^50 would seem to be rough.

Firstly the number says it is taken from a celebrated paper by Shannon (http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon .062303002.pdf) in the 50's who (as far as I can tell) gave the number as 10^43, however there were a number of approximations. Fristly he just considered distributing a chess set over a chess board without accounting for pawn promotion and positions which cannot legally occur (e.g. a major one being pawns cannot occur on the first or last ranks).The wiki page isn't that clear (as ought be expected!), but it does say that it is not that paper from which the numbers are taken-
The size of the state space and game tree for chess were first estimated in Claude Shannon (1950). "Programming a Computer for Playing Chess". Philosophical Magazine 41 (314). Shannon gave estimates of 1043 and 10120 respectively, smaller than the estimates in the table, which are from Victor Allis's thesis. See Shannon number for details.Emphasis mine. But he doesn't seem to give much detail on his final estimate.
In our calculation of the state-space complexity of chess, we have included all states obtained through various minor promotions. Using rules to determine the number of possible promotions, given the number of pieces and pawns captured by either side, an upper bound of 5x10^52 was calculated. Not all of these positions will be legal, due to the king of the player who just moved being in check, or due to the position being unreachable through a series of legal moves. Therefore, we assume the true state-space complexity to be close to 10^50. A state-space complexity of 10^43, as mentioned by various authors (Schaeffer et al., 1991), is in our opinion too low an estimate. The illegal position thing is interesting. I guess the two main types are to do with checks and pawns. And with pawns you can have-pieces getting in front of the pawns illegally (e.g. all white pawns on second rank, and King on e4), or pawns magically passing each other (e.g. all white pawns on third rank, no pieces have been taken, and a black pawn is on the second) and so on.

Rincewind
10-10-2007, 06:00 PM
Okay, according to Littlewood...

"With N men all on the board there are (with the individuality convention) 64!/(64-N)! A's." (NB A = arrangements).

Littlewood then comments about the illegality of certain arrangements but doesn't adjust this number. This is justified since he is concerned with an upper bound. He then goes on to say

"The number of different sets of men composed of pawns and pawns promoted (to Q, R, B, or Kt) is 5^16 + 5^15 + ... + 5^1 < 2 x 10^11.

Since the two K's must be present the number of sets of pieces other than those promoted from pawns is

14C1 + 14C2 + ... + 14C14 < 14 x 14C7 < 5 x 10^4

hence the number of sets of N men is for every N less than 10^16."

He then concludes that the number of arrangements is less than this number times the arrangement term (64!/(64-N)!) which is summed over all N from 1 to 32. However I not here this estimate could be improved a couple of ways including starting at N = 2. Anyway he says

"The number of A is less than a = 10^16 * sum(64!/(64-N)!,N=1..32) = 10^69.7"

So Littlewood's number here is pretty rough but certainly an upper bound.

He then calculates the total number of moves for any position. The upper bound of this figure (which he calls mu but I'll substitute u) is

" u = 9 x 28 + 2 x 14 + 2 x 14 + 2 x 8 + 8 = 332."

This would seem to perhaps be a little lax as it doesn't seem to have accounted for special moves such as two castlings and one en passant as well as two possible normal captures for every pawn. It also doesn't allow for the fact that you might have promoted and have 9 queens and therefore this number will probably be higher that 332. So I think this is the main weak point of Littlewood's calculation because he is underestimating a preliminary result which will directly effect his upper bound. Anyway, he then gives...

"The number of possible games is at most

u^(2a+1) = 10 ^ 10 ^ 70.5"

So as an upper bound this is a number but it might not be a definite one for the reason that u is not a strict upper bound of moves from any given position.

Note while this is based on the aforementioned pages in Littlewood's Miscellany, edited by Bela Bollobas, the chapter is a reprint of an article titled "Large Numbers" appearing in the Mathematical Gazette, July, 1948. This is 2 years prior to Shannon's paper.

Aaron Guthrie
10-10-2007, 06:24 PM
He then calculates the total number of moves for any position. The upper bound of this figure (which he calls mu but I'll substitute u) is

" u = 9 x 28 + 2 x 14 + 2 x 14 + 2 x 8 + 8 = 332."I thought this was way higher than could be achieved in practice (because pieces get in the way of each other, also I realize this isn't the purpose of an upper bound), but it isn't. White has 218 moves in this position. Link (http://en.wikipedia.org/wiki/Tasks_and_records_in_chess_problem)R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1

Desmond
14-10-2007, 03:53 PM
I have heard it said that there are more possible games of chess than there are atoms in the universe. Don't know if it's true, but it sounds like A Lot.

Basil
14-10-2007, 04:46 PM
I have heard it said that there are more possible games of chess than there are atoms in the universe. Don't know if it's true, but it sounds like A Lot.
I've said it myself! I rely on the concept that the variations are endless whereas the universe consists of finite matter.

However with a little more thought, I'm not at all certain about the infinite concept. I'd be interested in what the mathematicians have to say on the matter once we plug in the 50 move rule, but still allow for all nonsense (but possible) moves.

Rincewind
14-10-2007, 05:13 PM
However with a little more thought, I'm not at all certain about the infinite concept. I'd be interested in what the mathematicians have to say on the matter once we plug in the 50 move rule, but still allow for all nonsense (but possible) moves.

The number of positions is large but finite. Littlewood uses the triple repetition resulting in a draw to limit the number of possible of games. This is where his u^(2a+1) term comes from. The +1 is the point where a position recurs for the third time.

Basil
14-10-2007, 05:45 PM
Thanks Barry. What sort of number is that in lay terms? Is it more than $1,000,000?
http://i4.photobucket.com/albums/y105/scene66/avatars/evil.gif

Rincewind
14-10-2007, 05:51 PM
Thanks Barry. What sort of number is that in lay terms? Is it more than $1,000,000?

I get the pop reference but to answer you question: think of 1 followed by 70 zeros. Imagine how big that number really is. By way of comparison, a million is 1 followed by only 6 zeros. So it will take a minute to appreciate the magnitude of 1 followed by 70 zeros.

Once you think you have a handle on that THEN imagine 1 followed by THAT many zeros!

That is the number Littlewood come up with, which he expressed as 10 ^ 10 ^ 70.5

Cheers.

Desmond
14-10-2007, 05:55 PM
That's a spicy meatball!

Basil
14-10-2007, 05:57 PM
Mind bending. I don't think I can get my head around it.

Rincewind
14-10-2007, 10:25 PM
Mind bending. I don't think I can get my head around it.

I don't know if this has been clear in the earlier posts but Littlewood only investigated this problem as an example of what he calls a 'Large Number'. The chess component is really quite a small part of the larger article.