## The perfect Chess AI engine

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### Re: The perfect Chess AI engine

If you realize that you are forced into a draw position that you have previously been in, then you have to reverse the moves back far enough that you can move differently and not end up in a previous draw position.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: The perfect Chess AI engine

You cannot make a better chess engine than an engine that could consider every single possible circumstance and each circumstance is given a value based on how effective it is. They would have an identical strategy each time unless programmed to change strategy's after a draw in which case there would still be countless possibilities that would end in a draw and the engine to be perfect would never allow itself to lose so the cycle would repeat. Or something like that anyway.
00squigzilla

Posts: 2
Joined: Tue Apr 24, 2012 8:10 am UTC

### Re: The perfect Chess AI engine

00squigzilla, that doesn't make sense. It isn't clear what exactly you mean (if indeed you have a clear meaning in mind).
tomtom2357 wrote:This is simply to play that, if the players reach a draw position, they simply start the game over.
tomtom2357 wrote:If you realize that you are forced into a draw position that you have previously been in, then you have to reverse the moves back far enough that you can move differently and not end up in a previous draw position.
These are distinct and different rules. Are you proposing yet another different attempt to modify chess in a way to eliminate the draw from chess? Or are you claiming that they are the same rule, expressed differently, given that both players are perfect AIs?

A board position not being allowed in chess has a clear meaning in the rules of chess -- if your king is in check and there is no legal position you can transition to, then you lose twenty dollars and my self respect. If your king isn't in check and there is no legal position you can transition to, the game is a draw. If you add previous draw board states to the list of positions that are not allowed, this does not involve "winding backwards" -- it involves adding more draw positions, or more checkmate positions, to the game (immediately adjacent to the now-illegal position).

Now, do these two things result in the same set of winning positions, or not? I'd want to be careful. But I could believe it.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10209
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: The perfect Chess AI engine

Unlike tic-tac-toe, chess can theoretically go on for an infinite amount of moves. With infinite computing power, (mathematicians may argue on this one) it would still take an infinite amount of time to consider all possible moves to game ending. Take a scenario where there's just two kings and two knights on the board, each in their own corner, each just moves out of its corner, then back into its corner ad infinitum. That "branch" will still be doing the same thing over and over again, no closer to endgame - regardless of how many CPU cycles you throw at it.

As an analogy: Given infinite CPU cycles, could you iteratively find what \Sigma^{\inf}_{n=0}\left(-1\right)^{n} converges to? Of course not, it doesn't converge

If we could avoid following infinitely repeating sequences of moves then this wouldn't be a problem, right? With infinite CPU cycles, we could follow non-converging branches a trillion times if we wanted to - as long as we do only follow for a finite number of moves.

BUT if we take every finite sequence of moves generated by X iterations of one repeating move-sequence (e.g. moving kings back and forth), and Y iterations of another repeating move-sequence (e.g moving knights back and forth) where X and Y are natural numbers, how many possible sequences are there? Can a "countable" set be completely counted, given an infinite amount of time?

Anyway enough about that, I've got work to do...
battlesnake

Posts: 6
Joined: Fri Mar 09, 2012 1:53 pm UTC

### Re: The perfect Chess AI engine

battlesnake wrote:Unlike tic-tac-toe, chess can theoretically go on for an infinite amount of moves.
Spoiler:
Please don't show contempt for the people who have posted in this thread by arrogantly presuming you don't have to read any of it to contribute. Especially when you are flat out wrong.

You are being incompetent, incorrect and rude.

I'll summarize what previous posts have said about your "contribution": chess as a game has a rule saying that there is a draw after X moves (for an increasing value of X as the game has developed!) where no pawn moves and no piece is taken. It is easy to show that this bounds the set of possible games to a finite set. The downside to this rule is that there are forced mates that in theory would take more than X moves without a pawn move or a piece taken: if we want to extend the definitions of the ideal game of chess to include these forced mates, the natural extension would be to declare a draw on a repeated board state (or, if we feel generous, the 3rd time we return to a given board state). As there are only a finite number of board states reachable in chess, this also bounds the size of the game tree via the pigeon hole principle. This extension comes from games like "go", which (in some versions) use it to define a draw. A downside to this is that it probably makes chess PSPACE hard, but we are talking about ideal chess players, so that isn't a problem.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10209
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: The perfect Chess AI engine

Yakk wrote:The downside to this rule is that there are forced mates that in theory would take more than X moves without a pawn move or a piece taken

For a while, there were efforts to modify the official rules of chess to allow these specific known solved endgames to continue past the normal move limit, but people kept finding more and more of them and they were always ridiculously long and required absolutely perfect play in such a convoluted manner that nothing short of rote memorization was likely to pull them off in real play, so those exceptions were removed and the move limit made absolute again.

Technically the move limit rule doesn't require a draw, but for the consideration of ideal chess players it might as well because there will always be one player with reason to claim the draw.
douglasm

Posts: 499
Joined: Mon Apr 21, 2008 4:53 am UTC

### Re: The perfect Chess AI engine

Chess is a draw. A perfect AI engine will easily see and avoid any loss, and so will its opponent. Thus, draw.

Exhaustively proving the above statement is outside the reach of physical computers, but here is how I convince myself.

1. One extra move is worth about 1/3 of a pawn according to opening theory. Let's round up though, and say white's first move is worth an entire pawn.
2. Remove all of the pieces except the two kings and one white pawn.
3. This 3-piece game is now a draw according to endgame theory.

So black has a simple drawing strategy: trade all the pieces without getting his king too far out of position to block white's last pawn.

If white refuses to trade pieces, the game will eventually run into the 50-move draw or repetition draw.

White will use his first-move advantage to steer the game into complicated positions, hoping black will be unable to see far enough ahead and make mistakes. But a perfect chess AI will see all the way to the 3-piece ending and never make a mistake.
DaveMcW

Posts: 23
Joined: Sat May 17, 2008 7:42 pm UTC

### Re: The perfect Chess AI engine

DaveMcW wrote:Chess is a draw. A perfect AI engine will easily see and avoid any loss, and so will its opponent. Thus, draw.

I remain in a bad mood.
Spoiler:
That is your opinion. Stated in the form of a fact, which makes it pretty arrogant, but in the context of your post, a mere opinion.

But your opinion isn't all that well informed. Your description of how you convinced yourself is about as water tight as a sieve. So why should we care about an ill informed opinion?

Do you want us to point out where your description of how you convinced yourself leaks all over the place?

I'm not sure how you intended your post to contribute to the conversation, really.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10209
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: The perfect Chess AI engine

DaveMcW wrote:2. Remove all of the pieces except the two kings and one white pawn.
3. This 3-piece game is now a draw according to endgame theory.

I recommend that you read Wikipedia's articles on endgames, especially the article on the king-pawn v.s. king endgame. It is not a draw as stated above, the outcome of the game depends very much upon where the king ends up, it could be that white could force the swap to occur in such a way that the black king ends up in a position that will lose him the game.

Also, where did you get the idea that swapping pieces off ends up in a king-pawn v.s. king endgame anyway? I would think that trading pieces results in equal material. Your first move bonus gets less later on in the game if white hasn't utilized his opportunity of moving first, and if white does utilize his position, it probably won't result in there being equal swapping, it would result in white having a significant advantage.

Finally, if the game is proved to be a draw, then there is no advantage to being white in the first place if you are a perfect player, and therefore you are assuming two contradictory things, that there is an advantage to being white even if you are a perfect player, and that the game is a draw with perfect play. They cannot both be true.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357

Posts: 555
Joined: Tue Jul 27, 2010 8:48 am UTC

Previous