The perfect Chess AI engine

[Patashu]

It might be a win for black, but it probably isn't. The fact that you're forced to make a move, however, makes it possible; imagine a game with a 1x3 board, a white piece on one end and a black piece on one. On your turn you have to move a square and if you move onto an opponent's square you capture them. Obviously, black will win this every time. It's a very simplified game but gets my point across.

[colcolpicle]

It's just gut instinct, but I would guess that the game would end in a draw by threefold repetition. They would both realize that if they can't force a win, then a draw is the best outcome and if they get into a loop it would be because both know that if they break the pattern the other would be able to guarantee a win, or, if they knew that the other was perfect, could only force a draw. Neither player would want to break the pattern because it gives the other the advantage, just like when humans play chess. Again, this is just a hunch.

[lightvector]

Hunches and guesses don't count for much. Many expert players with a great deal of experience in connect 4 believed the game was a draw, until it was solved and shown to be a first-player win.

The optimal result of chess under perfect play (white always wins, draw, or black always wins) is simply unknown. It's unlikely, but as far as what we can rigorously prove, we can't even rule out that chess is a forced mate for black. Perhaps the opening position, is some sort of immense, deep zugzwang. It's unlikely of course and we can guess and speculate all we like, but when it comes down to it, we don't know of any substantially better way to prove it than brute forcing most of the game tree, which is beyond our current computing ability.

More or less, the only games where we know something nontrivial about result of perfect play are:

1. Games that we have been able to outright brute-force. Ex: Tic-tac-toe, Connect 4, Checkers, 5x5 Go

2. Games that begin symmetrically and where making a move can never harm your own position. This makes zugzwang impossible, which allows you prove that the first player cannot lose (using a "strategy-stealing" argument). If draws are also impossible, then this proves a first player win. Ex: Hex, Connect 5

3. Games with exceptionally nice mathematical properties. Ex: Nim


Chess falls into none of these categories.

[mward]

The two AI robots faced each other across the chessboard, as all the top Grandmasters and the world's media looked on in anticipation. This would be the greatest chess match the world had ever seen! Speculation had been rife for months: what opening would the robots choose? Or would it be something totally new and bizarre that the chess world had never seen before? What dramatic sacrifices and hairs-breadth escapes would thrill the audience?

A hush of anticipation descended on the room as the Black player punched its button on the chess clock to start the game.

The White player regarded the serried ranks of pieces in front of it for a moment, and then reached out a hand.

"Draw?" it questioned.

"Agreed" replied the Black player, shaking the White player's robotic hand.

Then they both went out for a game of football.

One of the organizers turned to the other: "We're going to get lynched you know that."

[lordatog]

Hunches and guesses don't count for much. Many expert players with a great deal of experience in connect 4 believed the game was a draw, until it was solved and shown to be a first-player win.

The optimal result of chess under perfect play (white always wins, draw, or black always wins) is simply unknown. It's unlikely, but as far as what we can rigorously prove, we can't even rule out that chess is a forced mate for black. Perhaps the opening position, is some sort of immense, deep zugzwang. It's unlikely of course and we can guess and speculate all we like, but when it comes down to it, we don't know of any substantially better way to prove it than brute forcing most of the game tree, which is beyond our current computing ability.

More or less, the only games where we know something nontrivial about result of perfect play are:

1. Games that we have been able to outright brute-force. Ex: Tic-tac-toe, Connect 4, Checkers, 5x5 Go

2. Games that begin symmetrically and where making a move can never harm your own position. This makes zugzwang impossible, which allows you prove that the first player cannot lose (using a "strategy-stealing" argument). If draws are also impossible, then this proves a first player win. Ex: Hex, Connect 5

3. Games with exceptionally nice mathematical properties. Ex: Nim


Chess falls into none of these categories.

Connect 4 doesn't fall into any of those categories either. It wasn't brute forced; it was solved through clever arguments.

[lightvector]

Well, sort of. A lot of positions in connect 4 are indeed surprisingly amenable to parity-based or combinatoric arguments, and you can use them to prove a win/loss/draw. But it seems that quite a bit of search was still necessary, since many positions do not fall immediately to these rules, leaving few options other than to brute-force them (with the usual algorithms+heuristics) until all the resulting positions *are* solvable by parity-based or combinatoric cleverness.

Allis's solution of Connect 4 still required searching and solving of millions of positions in a large tree from the opening position, performed using hundreds of hours of ~1988 cpu time. This would be much less on a modern computer, but is still not entirely a trivial computation. Apparently, Googling around indicates that there was another independent solution around that time too, which used a program with somewhat less knowledge and somewhat more brute-force, and had to search billions of positions to solve the game.

[redrogue]

Chess is 'solvable' in the sense that we could map the entire tree and have a game with perfect play. The question is whether or not black or white will win (or if there will be a draw) once we have the technological ability to solve it.

Until we solve it, we don't know. However, there is some discussion about whether or not the first move advantage indicates that white will win.
http://en.wikipedia.org/wiki/First-move ... ving_chess

[Xami]

I keep seeing 'pick the path with the most 'win' scenarios'

Let me make up a game.
Player A has 2 options. Stand still or hide.
If I hide, player B has to look for me or something and let's say there's 1 way for me to win, but I can force it
If I stand still player B has 5 options
Punch me (win) , do nothing (continue), prance around (continue) , punch himself ( lose) , or quit this stupid game (lose).
The 'most 'win' scenarios' is for me to stand still, because hey, player B has 2 ways to lose, but clearly he would take the easy win.

The best path isn't 'most win scenarios'
It's the path (or one of many potential paths) where the acting player can FORCE the other player into not winning.

And if you assume that the other player also has perfect knowledge, there is nothing they can do to stop this from happening, they would simply choose the 'draw' path if available.

[xkcd follower]

Based on strategy, I would feel white would have a greater advantage in winning.

Here's another thought. White does a move that is the most logical. Black does a move that is not the most logical, but in analyzing board, sees a possible weakness in White. The result is Black now at an even chance of winning against white. This can constantly repeat back and forth until they are truly equal.

In addition, a computer that smart would try to analyze the other player (i.e. the other computer). This would result in a near endless of cycles to figure out which move the opponent will do.

So, my big question is, would it be logical for Black to do an illogical move and thus gain an advantage over White, which is expecting another move?

[lightvector]

In addition, a computer that smart would try to analyze the other player (i.e. the other computer). This would result in a near endless of cycles to figure out which move the opponent will do.

Yes. It would not be endless, however, because there are only a finite number of positions in chess, and only a finite number of possible choices for the opponent at every step. But it would take a *lot* of computing power.

So, my big question is, would it be logical for Black to do an illogical move and thus gain an advantage over White, which is expecting another move?

If white is a fallible player, and black believes he has a good chance to create a situation where white will make a mistake, then yes, depending on the situation. Maybe black has a choice between a move that draws no matter what, and a move that loses if white plays correctly but wins if white makes a blunder. Then if black judges that the chance of white making a blunder in that position are greater than white playing correctly, black might choose the "worse" move.

If white is a hypothetical computer capable of perfect play, then no, never. This might be clearer if you understand what "perfect play" is. Here's a procedure to compute the perfect outcome of any game in Chess (for simplicity, we will ignore a few minor details, like 3-fold repetition or the 50 move rule).

Enumerate all of the trillions of possible legal arrangements of pieces. For every position where one of the players is in checkmate, mark that position as won for the opposite player. Then, look at all possible positions that aren't marked as won for some player yet. For each position, if every possible move for the current player results in a position that was marked as a win for the other player, then mark the current position as a win for the other player. If on the other hand at least one move results in a position that is marked as a win for the current player, then mark the current position as a win for the current player. Repeat this over and over for every position, until no new positions are being marked, then you're done.

Can you see how a computer could use all of these marked positions to play perfectly? That is, be guaranteed to win no matter what if you start in a position marked "win" for it, and be at least guaranteed not to lose if you start in a position not marked "win" for you? And can you see why there no way to trick or make a move that the other player doesn't expect, if the other player is a computer that has computed all of this and playing accordingly?

[xkcd follower]

Ow. Now I got too much thinking. Lets just say white figures out Black's plan and goes around it, then white will win. But later in the game, white may take black's strategy and use it against black to try and trick black. Then black could regain an advantage and continue the game. Too many problems with this situation.

[mfb]

There is no way to trick a perfect chess AI engine with a perfect chess AI enginge..

There are 3 possible cases:
Case 1: White has a winning strategy (and knows it).
That means that for every move of black, white has an appropriate answer to come to another position where white has a winning strategy. Every position where white can do a move to set black check-mate is a position with a winning strategy (obvious).
In this case, it does not matter which moves black will do, white just looks them up in his earth-sized memory and moves to another position with a winning strategy until it finally wins.

Case 2: Perfect chess is a draw (and both know that both know it).
There is no way to reach a position with a winning strategy for both sides, as long as both players are perfect (and know that). The best move you can do is to go to another draw-position, the worst is to go to a winning position for the opponent. If there would be a move towards a winning position, perfect chess would not be a draw.
A perfect chess AI enginge versus a human player may use some strategy here and wait for a mistake of the human. However, a second perfect AI will not make any mistakes, so this is pointless.

Case 3: Black has a winning strategy (very unlikely)
Like case 1, just with black and white exchanged.

[xkcd follower]

Very true. I think you ended this discussion with a really good answer.

[lorb]

According to what I read. In professional games white wins 60% of the time. The only reason why this would happen would be because they get the first move.

Definitely not.
The chessgames.com Database gives us:
White wins 232,924 games (37.27%)
Black wins 170,325 games (27.26%)
221,657 games are drawn (35.47%)

If you look at the results of very high-level games it becomes even more draw-ish.

[Gwydion]

According to what I read. In professional games white wins 60% of the time. The only reason why this would happen would be because they get the first move.

Definitely not.
The chessgames.com Database gives us:
White wins 232,924 games (37.27%)
Black wins 170,325 games (27.26%)
221,657 games are drawn (35.47%)

If you look at the results of very high-level games it becomes even more draw-ish.

Which, to be fair, is a win for white in 58% of the games in which there is a winner.

[Proginoskes]

The two AI robots faced each other across the chessboard, as all the top Grandmasters and the world's media looked on in anticipation. This would be the greatest chess match the world had ever seen! Speculation had been rife for months: what opening would the robots choose? Or would it be something totally new and bizarre that the chess world had never seen before? What dramatic sacrifices and hairs-breadth escapes would thrill the audience?

A hush of anticipation descended on the room as the Black player punched its button on the chess clock to start the game.

The White player regarded the serried ranks of pieces in front of it for a moment, and then reached out a hand.

"Draw?" it questioned.

"Agreed" replied the Black player, shaking the White player's robotic hand.

Then they both went out for a game of football.

One of the organizers turned to the other: "We're going to get lynched you know that."

Actually, that violates the rules of tournament chess: You're supposed to make a move, then propose a draw. (I think "propose" is better than "offer", since you don't "own" the draw to begin with.)

I wonder what the longest guaranteed 'mate in X' moves is? (from a mid-game or end-game board position). Mate in one or two is easy, but how far out can you get without the option of a stalemate? Hmm....

Wow... here's a site with 'mate in 290' ... link

The board position isn't legal, but it looks like there are supposedly legal 'mate in X' board positions in which X is greater than 250. Wow.

Nenad Petrovi\'c, 1969, is mate in 270. The FEN for the starting position is 8/Bk3p1p/1P3p2/KP2n2p/1P1p4/1Pp2p2/B1P5/7B. ( http://en.wikipedia.org/wiki/Forsyth%E2 ... s_Notation )

J N Babson pubished a problem in 1882, where White mates Black in 1220 moves, after forcing the Black knight to make three successive complete tours of the board. FEN: 3nk3/3NN3/3PP3/3BB3/3PP3/3PP3/3PP3/2RQKR2. Yes, there is a mate in one as well.

The longest announced mate during an actual (correspondence) game is at least a mate in 45.

(All of this is from The Even More Complete Chess Addict by Mike Fox and Richard James, pages 243-245.)

Anyone who wants to learn more about perfect-information games should check out Winning Ways by Berlekamp, Conway, and Guy, if they haven't already. Fun way to waste a few months.

[sigsfried]

I would be shocked if Chess wasn't a drawn game. It certainly feels that way and I understand that increased opening knowledge has increased the rate of draws. That said this would feel a lot more reliable guide if draws were not allowed to be made by mutual consent (that is the only draws would be stalemate, repetition, 50 moves and insufficient material [though even that in principle could be made up of the repetition and 50 move]).

[Tnarg]

I'm not sure about this line:
"taking into account the likeliness that its opponent will make any given move"

but if you what a perfect Chess AI engine then here it is:
http://www.shredderchess.com/online-che ... abase.html

any postion you give it, it will tell you who will win and whats the best move. ie if its can win from any give postion it will tell you the move to take you to that win as quick as possable, if it will lose agenst the perfect play it tells you how to hold off for as long as possable. It will also list what will happen if you play any other move. Clearly Knowing what it going to do will not help you.

1 problem it can only cope with 6 pieces so it can work it out for the opening postion sorry.

[mfb]

Your last remark is the point. 6 figures are like a joke compared to the initial 32 pieces.
And as the complexity of the game tree of chess is way too big to examine it in the near future (and possibly forever), that number of 6 might become larger. But the perfect chess AI is still far far away.

[Damarco]

After reading some ideas posted I believe that 'Draw' seems to be my conclusion.

Where every move set is determine it is only possible for 1 player to force a win, not both. (Call him player A)
That being said the player unable to force a win is thereby able to force a draw. (Call him player B)

So.. Player B will never attempt to win as it is impossible to him to do so. I lack the knowledge to put it into any type of mathematical proof or answer with 100% certainty but by the statistics given, my knowledge of chess and the possible ways to force a draw, it seems much easier when aimed to do so to come into a stalemate then to play to win, as well as many stalemate combinations.

[mfb]

That being said the player unable to force a win is thereby able to force a draw. (Call him player B)

Why?
There are many simpler examples where this is not the case. Many games have a lot of winning positions (much more than 50%, usually).
Do you have any chess-specific reason for your claim?

[BombSite_A]

Correct me if I'm wrong, but wouldn't this scenario be the same as just having a regular chess AI play itself? In that scenario it would be the same game every time, assuming neither one randomized their moves at all. So, we don't need a perfect Chess engine to test this.

[Yakk]

Ok. You are wrong!

Examine a game of tic-tac-toe. A poor tic-tac-toe AI could easily lose to itself: either the first, or second player could win (depending on the way in which the engine is imperfect). A perfect tic-tac-toe engine, when it plays against itself, gets a draw.

As an explicit example, the tic-tac-toe engine that plays on the first row that has an empty square, and the leftmost square that is empty -- the second player loses to the first.

AIs where the second player wins are a bit harder to come up with, but they wouldn't even have to look that dumb on the surface.

[mmmcannibalism]

After reading some ideas posted I believe that 'Draw' seems to be my conclusion.

Where every move set is determine it is only possible for 1 player to force a win, not both. (Call him player A)
That being said the player unable to force a win is thereby able to force a draw. (Call him player B)

So.. Player B will never attempt to win as it is impossible to him to do so. I lack the knowledge to put it into any type of mathematical proof or answer with 100% certainty but by the statistics given, my knowledge of chess and the possible ways to force a draw, it seems much easier when aimed to do so to come into a stalemate then to play to win, as well as many stalemate combinations.

Here is a game

rules
1. start with two players A and B
2. at the beginning of the game, player A decides if the game is a win loss or draw
3. B is not allowed to try and influence A in any way

How does B force a draw?

[douglasm]

Where every move set is determine it is only possible for 1 player to force a win, not both. (Call him player A)
That being said the player unable to force a win is thereby able to force a draw. (Call him player B)

These two statements are contradictory. If player A is able to force a win, then by definition player B is unable to force a draw.

[Wisher]

If chess is a win game:
White will win, black tries for draw. Since a win/draw is respectively optimal and loss avoidance is key for black black calls draw, refusing the game.
If chess is a draw game:
Since they will draw anyway white and black waste no time and accept a draw.

Chess is a draw game.

[Yakk]

If chess is a win game:
White will win, black tries for draw. Since a win/draw is respectively optimal and loss avoidance is key for black black calls draw, refusing the game.

There are games for which the 2nd player can force a win, while nothing the first player will do can prevent it. We do not know if chess has or lacks this property.

Second, you cannot refuse a game in chess and get a draw by any tournament rules I am aware of.

[thc]

That being said the player unable to force a win is thereby able to force a draw. (Call him player B)

Why?
There are many simpler examples where this is not the case. Many games have a lot of winning positions (much more than 50%, usually).
Do you have any chess-specific reason for your claim?

He's trying to say that it is easier to play towards a draw and draw than it is to play for a win and draw. Playing to win involves accepting dangerous combinations that could easily lead to a blunder. Playing to win seems to involve greater risk and increases your chance for a loss (ironically).

This isn't an argument based on any kind of solid proof, just one on intuition.

[rpenido]

There are finite game states but you can have loops, right ?
You can play indefinitely with no time constrains.
So you can have white wins, black wins, draw and no end.

If you have finite time and a non-zero time to make a move, you can also win by looping and forcing the opponent to lose by time. As black plays after white, he will always have less accumulated time than white. This could lead to a "black always win" situation.

[mfb]

Playing to win involves accepting dangerous combinations that could easily lead to a blunder. Playing to win seems to involve greater risk and increases your chance for a loss (ironically).

You are thinking like a human chess player. Two perfect chess AIs have no risks, no probability. Just paths through the known game-tree, where either one player can force a win (and it does not matter how the other player plays) or both players can force a draw.

Chess has some additional rules to avoid infinite loops.
Assuming a simple lookup in the memory does not need too much time, this AI could play a lot quicker than humans, so time should be no problem.

[douglasm]

There are finite game states but you can have loops, right ?

If 50 moves go by without either player advancing a pawn or capturing a piece, either player can claim a draw immediately. In a match between two perfect players, one of them will know that claiming the draw is his best possible outcome and will always take it. Pawn moves and captures are always irreversible, so no loop can continue for more than 50 moves. If you include the count of moves since a pawn move or capture in the game state, then true loops (which would require an identical move count in addition to board layout) are completely impossible.

[skeptical scientist]

There are finite game states but you can have loops, right ?

If 50 moves go by without either player advancing a pawn or capturing a piece, either player can claim a draw immediately. In a match between two perfect players, one of them will know that claiming the draw is his best possible outcome and will always take it. Pawn moves and captures are always irreversible, so no loop can continue for more than 50 moves. If you include the count of moves since a pawn move or capture in the game state, then true loops (which would require an identical move count in addition to board layout) are completely impossible.

The threefold repetition rule also puts an upper bound on the number of moves before someone can claim a draw, although I suppose the upper bound imposed by the 50 move rule (16*6+30)*50 = 6,300 moves is slightly smaller than the upper bound imposed by the threefold repetition rule (roughly 10⁴⁵).

Technically, these rules don't imply that the game is finite, because they give conditions when both players may claim a draw, rather than forcing the game to end in a draw.

It is sometimes interesting not to assume that the game ends in a draw after the 50 move rule can be invoked, because endgame tablebases have found positions which are drawn with that rule, but would be a win for one player without the 50 move rule.

However, if your interest is in solving chess, you might as well assume that threefold repetition leads to a forced draw. Everything in the game tree below a threefold-repetition-node other than claiming a draw is repeated elsewhere in the tree, so both variants (forced draw and optional draw versions) result in the same optimal result from every position, if infinite games are counted as drawn.

[beefmasta]

Presuming that both sides had the absolute best strategy and, as such, were unbeatable, and there are no draws allowed, that would mean that it would probably boil down to who went first.

[mmmcannibalism]

Presuming that both sides had the absolute best strategy and, as such, were unbeatable, and there are no draws allowed, that would mean that it would probably boil down to who went first.

You realize draws are an inherent part of chess right?

[skeptical scientist]

You realize draws are an inherent part of chess right?

...and that "no draws allowed" contradicts many of the other rules of chess? What happens if a player has no legal move? What happens if there is insufficient material for either side to achieve a win?

[tomtom2357]

There is a way to remove draws from the game, but it may change the optimal moves slightly (and make the game a lot longer). This is simply to play that, if the players reach a draw position, they simply start the game over. However, on this second game, they cannot repeat the exact same series of moves as the previous game. This only changes gameplay slightly because this added rule will only restrict possible moves on the last few moves, and only if the make the exact same moves up until then. If it is a draw again, the game is played a third time, and they cannot repeat the exact same sequence of moves as the first or second games, and so on. Obviously there are only a finite number of drawing positions in chess, so eventually they will all be played, then one of the players must win.

Edit: Actually, this can be made faster by changing the rule to: you are not allowed to end up in a position that is a draw position and was reached in a previous game. This prevents you getting to that position by using a different set of moves.

[lorb]

First there are not just "draw positions". A draw might also occur in the form of a non-draw position that repeats itself endlessly. That's the reason there is a "threefold repetition = draw" rule.

Second: Imagine both players are left with just their king and the queen. By your rule one player may capture the queen of the other player, for whom it will be illegal to recapture after the first time. That changes the game fundamentally.

Third: What about positions that are only draw with perfect play but not inherently so? There are some endgames that are proven to be draw with perfect play, although there is still enough material left for the game to end if imperfect play is allowed. (called a "book draw")

[Yakk]

First, threefold repetition isn't needed -- that is an artifact of giving humans a first chance at spotting the draw loop. We can easily use the PSIZE Go draw rule:
"If the board is ever in the same state as in this game prior, this is a draw position."
State would include "have we castled", etc. And for chess, which has forcing moves, we augment it with:
"If the board is ever in a state where the rules force you to return to a draw position, this is a draw position."
optionally. (I don't know if this augmentation is a good idea).

Secondly, we say that if a player cannot make a move, they must surrender. This is a serious modification to the standard rules of chess.

Either way, this gives us a rigorous way to determine if a given board is in a draw position.

Next, we can eliminate draws with the "when you enter a draw position, you start a new 'instance' of chess, with some positions no longer legal", where an 'instance' of chess is where you start from the initial positions, with white going first, and play through until one player wins or enters a draw position. Which set of positions? I can think of a few (all of which would eliminate draws):
1) You may not repeat any previous instance of chess from this game -- which means you cannot reach the exact same draw position via the exact same set of moves. If you are almost at the draw position, the move that reaches the draw position is not allowed. As in normal chess, if you lack a legal move, you lose.
2) You may not repeat any previous draw position from any instance of chess in this game. This is a bit broader, in that a different way to get to the same position is also blocked.
3) You may not repeat the first move of any previous instance of chess in this game.
4) You may not enter into any state that any previous instance of chess in this game has been in (except the starting board state, naturally!). This is the most restrictive -- if a previous game started with white moving king's pawn forward 2, white may not start the game with that move.

These aren't quite equivalent, because the rate at which we make board positions illegal grows faster in #4 than in #2 than in #1. #3 basically gives white a count-down timer before white loses the game, each time with an inferior opening. And the existence of illegal board positions can change which move is ideal. However, in all 3 cases, each instance of chess that ends in a draw eliminates at least one position, and there are a finite number of chess positions, so eventually one player must win -- in theory, if you eliminate all positions except the starting board state as being illegal, then black wins as white cannot make a move.

Hmm. I think #3 basically says "if white cannot win the first game, black wins". That's boring.

[tomtom2357]

I think that the way I did it is simpler, and it works better because, as you said:

Hmm. I think #3 basically says "if white cannot win the first game, black wins". That's boring.

All mine does is simply remove all draw positions, so the only end positions left are ones where either white or black wins, and it does not change any of the basic rules of chess, so it does not change the game completely. I do need to make one change to my idea, simply to consider whether someone has castled or not, which can change the outcome of the game.

[Yakk]

Not quite. Suppose you are not in check but the only move you can make moves you to a position that was a previous game draw position. You position is nothing now a draw position. What more, if you where in check then adjacent draw positions can lose you the game.The state of previous games changes what moves later are checks. What more is that draws are pulled forward as more and more of the possible chess positions are made illegal. In theory ,every opening move by white could be made illegal, which then causes setting up the board to be illegal. So not only does this change the game in very complex ways, it also does not eliminate the possibility of a draw.