The perfect Chess AI engine

[warriorness]

Consider a "perfect" chess AI engine. Also suppose we have an infinitely powerful supercomputer, so CPU cycles are not an issue. This AI engine determines its moves by analyzing the entire tree of possible moves and considering how likely each move is to generate a win, taking into account the likeliness that its opponent will make any given move, etc. It also attempts to avoid draws, so it'll stay away from three-move repetitions, the 50-move rule, and stalemates. If two moves are deemed equally good (i.e. two possibilities for checkmate) then it chooses at random.

Now consider two such chess engines, set to play against each other. What happens? Does white or black always win, or do they draw?

Also, would it be possible to design a better engine, which considers what the first engine would consider, then also considers a way to fool the first engine - say, by making an unexpected move that the first engine had assigned a low probability of being made? If so, what would happen if two of these engines played each other?

This thread is purely speculative, so I don't know the answer. If you can prove an answer, feel free to post it or make your own solutions thread.

[Rat]

hard to say...

*takes another hit*

[Yakk]

An engine as good as you describe -- with infinite CPU power -- already determines what the best move for their opponent.

We don't know what kind of game chess is -- chess could be a game where black wins, where white wins, or where it is a draw.

But the best analogy that we can grasp would be tic-tac-toe. We all know that tic-tac-toe is a draw game. But imagine if you where playing tic-tac-toe against someone who doesn't know it is a draw -- then your moves can be designed so that more of the opponents moves are screwups that change the game into a winnable game.

There are varients of tic-tac-toe which are wins for one side or the other -- like 2x2 tic tac toe. In those games, the player who goes first has a winning strategy -- and it doesn't matter what the other side does.

But once we know if the game is winnable or drawable or not, two computers that know this can't fool or trick each other, because both know the entire game tree. It would be like trying to trick someone using tic tac toe -- it works, but only if the other player isn't paying attention enough.

Now, practically, leamining the entire game tree of chess isn't reasonable. The enitre game of chess is large. At best you can solve it using mathematical trickses -- exploring it all explicitly isn't really possible.

[Gelsamel]

I am curious as to what their first move would be. One that opens up the most possibilities?

[warriorness]

I am curious as to what their first move would be. One that opens up the most possibilities?

It would be either that, or the opposite. I could see it playing b3, g3, d4, or e4 for maximum development, but then there's also the "You can be white!" opening - a3 or h3.

Speaking of that - suppose the answer to my first question were that Black must win. Would White be able to reverse that by playing a3 or h3 as the opening?

[Gelsamel]

Mm, black would have to win since it reacts to white's first move and white's first is open, and there are a lot of equally opportune moves. That is your line of thought?

I think black wins no matter what because of that. White is technically a step behind, despite starting first it had nothing to judge the first move on.

I think optimum move would be King-4 honestly. But Queen-4 and other similar moves all seem to open the same winning possibilities etc.

[Strilanc]

Well, at the very least I know black doesn't have a winning strategy where the first move is always advancing the same pawn two squares, no matter what white does on his first move.

If he did have this strategy, white could just move his equivalent to that pawn forward over two moves, effectively passing a move and taking black's role.

I'm sure there's thousands of little quirks like this. The problem is that the player's start interacting very quickly and in a complicated way in chess, making it difficult to handle all the cases.

[skeptical scientist]

Technically speaking, if one player has a winning strategy, and both players know it, then any moves made by the opponent can be considered correct. If white has a winning strategy, black can make her moves entirely at random and be as good as an expert, since both will always lose. However, one can tell the difference between chess games where one person is playing at random, and where both players are experts. There are different ways of choosing moves for the losing player. One of them would be to have that player play in such a way as to maximize the length of the game. Another would be to have that player play a move with the fewest correct lines of play coming from it. This has the advantage that while white must have a correct move, if white has very few, it will be hard for white to spot it, and easy to make a mistake.

[Tchebu]

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.

In in the perfect vs perfect scenario white would win as well (more often at least), because the first move is by definition "perfect" and is the most likely one to give you a win, but black might not have an "equally perfect" move available anymore, because even e2-e4 already scratches out several moves for the black (i.e. in a lot less likely to do f7-f5 unless its a gambit of some sort) so this way the "best" first move for black might already be less probable to bring you a win. Otherwise its just as good (it cant be better because white wouldnt have made a move that allows that), and we're back to where we started. So white can do the "best" move, and the only thing black can do is at best match it. So the match will be at best a draw.

Also if im not mistaken, the sum of probablilies of white winning, black winning and a draw should be 1 right? If there is a first move that gives you a 51% chance of winning, you automatically win, because being a perfect computer you will take full advantage your.... uh... advantage.

[Strilanc]

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.

In in the perfect vs perfect scenario white would win as well (more often at least), because the first move is by definition "perfect" and is the most likely one to give you a win, but black might not have an "equally perfect" move available anymore, because even e2-e4 already scratches out several moves for the black (i.e. in a lot less likely to do f7-f5 unless its a gambit of some sort) so this way the "best" first move for black might already be less probable to bring you a win. Otherwise its just as good (it cant be better because white wouldnt have made a move that allows that), and we're back to where we started. So white can do the "best" move, and the only thing black can do is at best match it. So the match will be at best a draw.

Also if im not mistaken, the sum of probablilies of white winning, black winning and a draw should be 1 right? If there is a first move that gives you a 51% chance of winning, you automatically win, because being a perfect computer you will take full advantage your.... uh... advantage.

Moving first is not always an advantage. For example, consider the game where each player either adds 1 or 2 to a sum, and whoever gets the first number of 12 loses. Player 2 has a wining strategy here by always picking the opposite of what player 1 does.

Also, perfect players either always win or always lose in games with perfect information. There is no probability of perfect white beating perfect black other than 1 or 0.

[3.14159265...]

Haha!
K so what would the first move be?
I actually think that if its just a perfect computer in chess and not AI psychology they would play the same game always.
Always starting with e2-e4 and responds with e7-e5. Also, I think it will always be a draw. Think about it, If you started witht that play, and were allowed to undo as many moves as you wished, would you not draw?

I think the reason you get so many different games in chess, is because people actually use psychology as well as.

[warriorness]

Also, perfect players either always win or always lose in games with perfect information. There is no probability of perfect white beating perfect black other than 1 or 0.

Because with these AI engines, they would always make the same move given a situation. If you played fifty chess games with these AI engines, they'd all turn out exactly the same.

Always starting with e2-e4 and responds with e7-e5. Also, I think it will always be a draw. Think about it, If you started witht that play, and were allowed to undo as many moves as you wished, would you not draw?

I think the reason you get so many different games in chess, is because people actually use psychology as well as.

Why would this computer need to undo a move? It would consider everything; thus, it would not make a mistake.

As for psychology - that plus human error/limits is what causes it. Like I said, with perfect AI, each game would be exactly the same.

[LE4dGOLEM]

The perfect engine would learn.

[Tchebu]

Moving first is not always an advantage. For example, consider the game where each player either adds 1 or 2 to a sum, and whoever gets the first number of 12 loses. Player 2 has a wining strategy here by always picking the opposite of what player 1 does.

Also, perfect players either always win or always lose in games with perfect information. There is no probability of perfect white beating perfect black other than 1 or 0.

Its not ALWAYS an advantage for all games, but in the case of chess it is. Like I said, in pro tounaments white wins 60% of the time. I wouldnt think thats because the better players always get to play white.

The first move won't necessarily be the same all the time. Its possible that there are several openings that will give you an equal probability of winning. By probability I dont mean that with that opening, the perfect system will win that fraction of times out of a given number or games, i mean that the ratio of all the "winning" ways for the game to continue to the number of possible outcomes in general. The "perfect system" as said in the original post, doesnt attempt to predict what the opponent does. It simply looks at ALL the possible moves that it or the opponent might to, no matter how stupid those moves might be from a human point of view. Then the system takes the move that has the most "winning" outcomes and that's the move it makes.

Now suppose white calculated all the possible moves it can make as the first move (that would be moving any pawn one or two squares forward, or the knights). The one that will give it the most "winning" outcomes later on will be the move it makes. If there are many such moves (which is quite possible) then it will choose a move at random. Now the black will already have a bunch of the overall possible outcomes of the game removed from them (like all the possibilities involving d2-d4 as white's 1st move, because white didnt actually move there but went e2-e4 for example).

Now when white makes a move that has the biggest fraction of "winning outcomes" in it, this also implies that it has the SMALLEST number of "tied" or "black wins" oucomes out of all the possibilities. This means that the best move black can come up with is at least as probable to give it a win (this only happens if the best move white makes gives it a 50% chance of winning, not taking ties into accout, otherwise white wins by default).

So in this way black will never win because it can't come up with a move that will give it more options that white. The best it can do is a stalemate, and this is only possible if white can only make 50% win probability moves all the time, because that the highest the game will ever allow it. This means that chess has to be completely unbiased, which it probably isn't, considering the 60/40 ratio in pro games. Otherwise, if the game ever allows white to make a move with a greater than 50% probability of winning (probability as defined above) the white will take full advantage of it (never making a mistake, being perfect), and will win, because black will never get the chance to make a better move.

[warriorness]

The perfect engine would learn.

Why would it need to learn, if it did everything right the first time?

[Strilanc]

The only situation where the probability of a perfect player winning is not zero and not one is when it is playing against a non-perfect opponent and it isn't on the side guaranteed to win.

White making '50% probability win moves' makes no sense in a deterministic game against a perfect opponent. If there's even one way black can beat white, black will take it. Otherwise, if there's even one way black can tie white, black will take it.

Also, you're description of a perfect white player is wrong. White does NOT attempt to maximize the number of possible wins with each move. White applies the minimax algorithm ( http://en.wikipedia.org/wiki/Minimax ).

[Zephyrus]

Wouldn't it be defend on the aggressiveness of the AI ?

It's an extreme example, that if both AIs are defensive, the game will be endless( or draw simply) 'Cause whoever starts first, both computer may move Knight back and forth and never moves other units

[warriorness]

Wouldn't it be defend on the aggressiveness of the AI ?

It's an extreme example, that if both AIs are defensive, the game will be endless( or draw simply) 'Cause whoever starts first, both computer may move Knight back and forth and never moves other units

N{b,f}3 is hardly a defensive opening. Aside from that, though - the AI would be programmed to try to avoid ties if there were still feasible winning possibilities.

[fortyseventeen]

I have to say that Yakk summed up practically everything we know on the subject and that this thread has mutated to a discussion on opening moves. Seeing as I've given up Chess for Go, I'm going to have to leave it there. Bye!

[Zephyrus]

Wouldn't it be defend on the aggressiveness of the AI ?

It's an extreme example, that if both AIs are defensive, the game will be endless( or draw simply) 'Cause whoever starts first, both computer may move Knight back and forth and never moves other units

N{b,f}3 is hardly a defensive opening. Aside from that, though - the AI would be programmed to try to avoid ties if there were still feasible winning possibilities.

That i didn't consider. Thanks

[genewitch]

If you think about this in terms of Checkers < chess < Go...

Speaking purely from speculation here... Chess is a game that is easy to determine moves in, as is checkers. Easy as in a computer can be trained to do it.

Go, on the other hand... the answer to this question is ""impossible"

also do both machines have the same code?
If so, it'd be the same outcome every time, unless the code learned. but it would only be 2 steps before one would learn how to beat the other, so on and so on. (maximum of two steps, minimum of one AFTER one had been beaten by the other using a new strategy; then they'd switch sides, and the other one would have to learn).

Also, far and beyond just "chess math", if you could teach the AI how to be clever...

[warriorness]

also do both machines have the same code?
If so, it'd be the same outcome every time, unless the code learned. but it would only be 2 steps before one would learn how to beat the other, so on and so on. (maximum of two steps, minimum of one AFTER one had been beaten by the other using a new strategy; then they'd switch sides, and the other one would have to learn).

Also, far and beyond just "chess math", if you could teach the AI how to be clever...

Yes, both machines use the same AI. That's the point of the question.

Although this raises another question: Suppose the code could learn (say, at the level of a reasonably intelligent human). What would be the outcome of the second game they played if a) white won the first game b) black won the first game or c) they tied in the first game?

[jestingrabbit]

If the algorithms are perfect, then they have nothing to learn. They both know the entire game tree and each one, at every turn, makes the move that maximises the chance of winning, given that the other player is doing the same.

Hmm I started out confident of that learning was impossible, but now... I'm not really sure what "perfect" means in this case.

[Yakk]

Each move has three possibilities, if you assume the opponent is as smart as you.

It can be a winning move, a losing move, or a draw move.

Now, if you assume the opponent can make mistakes, only then do probabilities and fuzzyness enter into it.

So let's define two metrics on chess moves.

Let C(N) be the "best" turing machine of size N at playing chess, where "best" is defined as "beats the ideal chess program in more legal game states".

DoNotLose(Move) = 2 if the move is a winning move, 1-1/N if the move is a draw move that beats all C(n) for n < N, 0-1/N if the move is a losing move that beats all C(n) for n < N.

AimToWin(Move) = 2 if the move is a winning move, 1-1/N if the move beats all C(n) for n < N.

If Chess is winnable, none of these metrics matter -- with two perfect chess AIs, one side always wins. Period.

If Chess is a draw game, then both of those metrics being used to play are interesting. If one side is playing DoNotLose, it will not lose -- it will at worst draw. DoNotLose, backed up by a perfect AI, assuming chess is not a losing game for that colour, simply never loses.

If one side is playing AimToWin, and the other side is playing DoNotLose, the DoNotLose will draw or win, and AimToWin will never win.

If both sides are playing AimToWin, things can get interesting.

This holds for simple varients (with slightly different metrics, but the same overarching strategy encoded into those metrics) of AimToWin and DoNotLose.

[jestingrabbit]

If both sides are playing AimToWin, things can get interesting.

Agree with the rest of what you wrote. But this is the problem. If chess isn't a definite win for white or black, then what would a perfect ai do? Aim to win, lose or possibly either depending on the game state? Does perfect make sense in this case?

[Hix]

If chess isn't a definite win for white or black, then what would a perfect ai do? Aim to win, lose or possibly either depending on the game state? Does perfect make sense in this case?

If it's not a definite win for white or black, that means that both sides are capable of forcing a draw. Any perfect AI, therefore, MUST force a draw at every move (unless the opponent has made enough mistakes that it is able to force a win). If its opponent is also perfect, then it makes no difference as to which forced-draw move it makes when there are multiple such moves. If we consider the possibility that this perfect AI will play against non-perfect opponents, then it SHOULD always choose the forced-draw move for which it is hardest to find a forced-draw reply (if not immediately, then perhaps several moves from now). Of course, some definition of "hard to find" must first be made, and that definition will vary from opponent to opponent. A reasonable attempt at defining a "hard to find" drawing reply would be based on what percentage of total moves available actually lead to a draw versus the perfect AI.

[Yakk]

On second thought, my metrics suck. A machine that happens to know the winning move to beat a given move is a pretty damn small. And it contains no limit on execution time/space, so it reduces to the halting problem in many cases.

:)

[bbctol]

Do the two computers know the other one is a "perfect machine" like themselves?
If so, there would be no point in playing, because both computers would know all the moves the other would make. As to who would win, I'm inclined to believe that chess isn't a perfect strategy game, and that white or black has some tiny mathematical advantage, simply because the two sides are different.
If both computers think they are playing against a "normal" opponent, the outcome would be...um...strange.
First post by the way.

[elminster]

Ive thought about this before. I came to the conclusion, if a computer worked out the probability of success for every move, for every possible position of pieces, along with the chance of success and visibility of any chain of moves.

It would consistently play in a similar manner, although would randomly choose between tactics it picks. The only way to get around this random tactic picking, would be to make it study a huge amount of players, and use their common mistakes or tactics against them.

i.e. it would be more of a case on how the computer can analyse human behaviour, if it were to be 'perfect' (which is technically impossible).

At worst case, it would be best to design it to be able to force a draw.

Like tic tac toe, its possible for the first player to either win, or force a draw. Chess very most likely has an advantage for the first player, so if it was perfect ai vs perfect ai, it would most likely be the white to win.

[Yakk]

In tic tac toe, the first player cannot win.

When you have the entire game tree, what does "your probability to win" mean? You know that the other player can force a draw, can win, or if you can win or force a draw.

[Gelsamel]

I agree with Yakk, Chess, where every possible move is known is a scaled up Tic-Tac-Toe.

[Fiddly]

In Game Theory, Chess is classified as a finite, perfect information, game with no chance moves. It's proven that these games have a value, that is if both players play optimally, the outcome of the game will always be the value.

Perfect information means that you know exactly where in the game tree you are at all times. A very simple game with imperfect information is Rock, Paper, Scissors. Another more complicated game is poker.

A chance move is something like the roll of a dice.

If you know the entire game tree, which in Chess you technically do, you can use Zermelo's algorithm (which is basically dynamic programming) to find the value of the game. In doing so you'll calculate the optimal move(s) for every position.

[AllTooHuman]

With perfect information a new game would always result in stalemate (in my opinion).

If computers with perfect information were to take-over a human-played game closer to the end-game, it is possible that the board would be in a position where there was an absolute unavoidable path to victory without stalemate for one of the sides. Each computer would know it. The side destined to lose could try to prolong the game as much as possible, but there would be no 'mistakes' and every outcome would already be known. Defeat would be predetermined, impossible to avoid and prolonged at best.

That said, there are only twenty possible first moves in chess. If we were to map out all of the possible actions and reactions after each of these initial moves, I do not believe we would find (with perfect information) any path that did not at least lead to stalemate.

Chess has a game complexity of something approaching 10 to the 23rd. So a computer with perfect information would be pretty hard pressed to store that data in some kind of memory or database. That is a lot of zeros....

Wikipedia: Relative Game Tree Complexity

With perfect information, a chess engine would have to try to avoid stalemate in an attempt to win. Each perfect chess engine would likely pick a path that had the most possible winning outcomes for its side, the least possible winning outcomes for its opponent and as few stalemates as possible.

Even with this simple algorithm it would be hard for either side to win. As winning opportunities dwindled on one side, the weakened side would force a stalemate ending. The key is that no move would be made if all subsequent possible paths didn't result in at least a stalemate further down the tree. A perfect chess engine would never make a move that allowed the apponent to force a victory through any combination of moves.

I didn't think Tic-Tac-Toe could end in other than a tie with perfect information. Here's a site that seems to think so as well: Site

I believe that much like Tic-Tac-Toe, a new chess game will always end in tie, if perfect information could truly be known, stored in memory and evaluated.

[gmalivuk]

I believe that much like Tic-Tac-Toe, a new chess game will always end in tie, if perfect information could truly be known, stored in memory and evaluated.

But is there specific evidence for this? With tic-tac-toe, it's obvious (because the tree is so small) that two even basically competent (let alone perfect) players can always force stalemate. But that alone isn't evidence that the same would be true of chess.

It is known, for instance, that the first player can always force a win in Connect-Four by starting in the center and then playing the right subsequent moves.

With chess, as far as I know, it remains unknown what kind of forced outcomes exist from the very beginning.

[Fiddly]

Perfect information means you theoretically have access to exactly where you are in the game tree at all times and all the possible places you can go. It is a property of a game, it does not depend on whether or not you have actually calculated out the entire game tree. Essentially, if both players could in theory play optimally, the same outcome would always result. However, it is impossible to say what this outcome is without actually calculating at least an enormous fraction of the game tree.

I'm surprised player 1 can force a win in Connect Four, I'd be interested to see a proof of that. Also another game that player 1 can always force a win in is Hex:

http://en.wikipedia.org/wiki/Hex_%28board_game%29

[gmalivuk]

I'm surprised player 1 can force a win in Connect Four, I'd be interested to see a proof of that.

http://www.connectfour.net/Files/connect4.pdf

[Patashu]

Since chess is deterministic, the game will either be a win for white OR a win for black OR a draw assuming perfect play.

However, we'll need a perfect chess engine to know what a perfect chess engine will find the game to be.

Or, more simply, we'll need to map out the entire move tree for chess until it reaches such a depth as to be able to force a win (or a draw) by one player from the very beginning of play.

Any volunteers?

[AllTooHuman]

That's the beauty of complex games like Chess or Go.

Estimated game complexity of 10 to the 123rd for Chess, 10 to the 766th for Go.

Even if you could use every atom in the Earth to store a unique 'game' you would need about .... oh... 10 to the 74th 'Earths' full of atoms to map out Chess. That would be (give or take):

1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 Earths...

With 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 atoms in each Earth.

That is if I am doing the math correctly (based on this estimate that the Earth contains about 10 to the 50th atoms: qaearth )

I suppose somewhere in that ginormous tree there could be an unavoidable 'mate in 40 moves', but my gut says there isn't a path that begins at 'move one' that leads to unavoidable mate every time (for either side).

Fun to think about though...

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....

[AllTooHuman]

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.

[Your.Master]

Actually, I don't have the actual proof for this, but I have read that it was proven that black cannot guarantee a win given perfect play on both sides. Either white always wins, or the game always draws. Which of these it is, we do not know -- but we also don't necessarily need to know the perfect game tree to be able to figure it out.

Consider a game of tic-tac-toe on a board of side-length N >> 3. It is trivially easy to prove that a perfect game outcome is a draw without considering many cases at all.

It's not the greatest example, because it's also trivially easy to see moves that are equivalent to perfect play in that situation, but I hope it gets the point across.

Of course, it may also be that we really DO need the entire game tree to figure it out. But I haven't seen anybody prove that there isn't a clever proof of whether white wins or the two players draw.

EDIT: Now that I think about it, it might not be quite so trivially easy to show that about tic-tac-toe as I said. But it can be shown, nevertheless.