"Solving" Chess - Possible?

I don't claim to be an expert in computer science, or in Chess, but I have an idea for creating a "solution" to chess (an algorithm that forces a draw, not one that guaruntees a win, though the same principle would apply for a win). I question, though, whether it would be feasable, so I'd like to run it by you intelligent and beautiful people. First, a quote.

Claude Shannon in a 1950 paper "Programming a Computer for Playing Chess" (as referenced on Wikipedia):

My idea is essentially to take a very strong chess AI and "patch" it to determine moves that will at least force a draw, creating a coded "solution". The algorithm for generating the program (as the starting player) would be something like this:

Code:

Take your AI, and have it play against every possible move the
opponent could make. (*)

Follow the 50-turn stalemate rule (no captures or pawn moves in 50 turns
results in stalemate), apply some kind of algorithms to reduce the number of
moves you have to compute in such situations.

If the game reaches a point where your AI has been checkmated:
   While the AI is still being checkmated:
      Retract one move.
      Determine by brute force if any next move for your AI can lead to a
      situation where it will not be checkmated.
      If yes:
         Save any game state where the AI must make a move contrary to
         its coding, along with any moves it must make.

(*) This is essentially having the opponent brute force your AI.
    Yes, this results in many, many possibilities.

After this, you'd have the AI play the game, but check as it plays whether it has reached a move it needs to play with alternate instructions, and if so, it would make the move indicated.

There are two main difficulties I see - one, there are a lot of computations that need to be done for the opponent to brute force the AI. However, this is many less than if you were to use two brute force players - the AI only has one move it makes on each turn (until it gets beaten, but more on that later), and many moves made by the opponent are likely to lead to it getting beaten early on.

My math is very rough here, but unless it's significant, I don't care. Assuming a game lasts on average 40 moves, and on each of the opponent's turns they have 30 available moves, this means we need to consider 30^(40/2), or about 3.5 x 10^29 variations to end-game. The number of moves would be the sum of a geometric series, something like (1-30^21)/(1-20) or 5.5 x 10^29 moves. That's a lot of moves, but also a lot less than 10^120. Using the given 10^90 years to compute 10^120 variations, or 10^30 moves/year, if we computed 1000 moves per second, this part of the process would be done in less than a year (though of course, needing to do calculations for the AI limits the number of moves we can compute per second, but perhaps not by that much with enough processing power)

Second, once the opponent has beaten the AI, it is possible that the AI must step back an unfeasable number of moves, for example, back to the start of the game. One way to try to get around this is to make a defensive AI, or perhaps have the first n moves be played defensively, to avoid needing to retract too far when trying to avoid a checkmate. Someone who knows more about chess than me might be able to shed some light on this. Perhaps with a very good AI, you would never end up in such a situation?

How many steps back would be likely be unfeasable, i.e. how many steps back before the brute-forcing of a way out takes too much time?

Also, it is possible (though I don't know whether it's probable) that the number of alternate solutions that would need to be stored is too large to realistically store, or realistically search through in the resulting program.

One should also consider that the solution needs to be made twice, once for white and once for black.

Considering all this, do you think coming up with a program that can guaruntee a draw in chess is feasable?

 

Log in or Sign up to hide all adverts.

I always thought that the reason that people play chess is to WIN, not have draws, which only show that you can't win. :shrug:

 

Log in or Sign up to hide all adverts.

Log in or Sign up to hide all adverts.

Well, the resulting program *would* win, in every instance where your strong AI is able to win. It would just also never lose. If you really wanted to, you could have the AI brute force the game whenever it reaches a draw as well as whenever it loses, but there's always the chance that it is impossible to force a win, and you wouldn't know that fact for a very, very long time.

 

the thing is that you are assuming your opponent will make a certain move.

There is only one situation in chess when you can potentially force your opponent to make a certain move, and even then it is not always so. And that is check. Other then that there is nothing binding your opponent to a certain move.

Take for example the immortal game, a famous game between a chess master and a chess teacher.

The reason this game, which was played almost 160 years ago, has so much fame is because the master sacrificed his bishop, both rooks, and then his queen and in the next turn he mated the enemy king using his knights and his remaining bishop.

that is an example of a person who would throw a wrench in your plans by sacrificing something the AI didn't think they would.

 

I guess I've never met anyone like that, everyone I have played has always tried to beat me while I tried to beat them. No matter how good another player is, to me, I'm going to play to win every time but if a draw happens I don't plan it that way and again I don't know anyone that does.

 

I think you misunderstood what I said - the program I described would protect against exactly that. The whole reason why it guaruntees a draw is that it considers *every possible move* made by the opponent, and finds which of those moves lead to a loss. It's the AI that only makes one move, you check the outcomes for every possible move the opponent can make.
Hence the difficulty of the sheer calculation of ~5.5*10^29 moves, I believe half of which are moves your AI has to calculate.

When you find an outcome of the opponents' moves that causes you to lose (and remember, you're checking all of them), you figure out how to avoid losing by brute force. The other difficulty is that I don't know whether this brute forcing would need you to step back too many moves to be feasable. You step back until *none* of the moves the opponent can make can lead to you being checkmated.

 

yes, but not every move leads to a draw.

 

Do some research on Game Theory.

You do not mean to say "solving". What you are trying to describe here is decidability.

To date, the game of checkers (for example) has been proven to be decidable. Chess however (for reasons already mentioned here by others) remains elusive.

 

Well, essentially one of the things I'm wondering is, "will it always be that some move will lead to a loss?". I want to know if the claim you're making will always be true. If not every move of the opponent following one the AI has made can be forced to lead to either a draw or win (for all of the opponent's moves), then you would retract one more move made by the AI, and check all other moves it could have made for a move that has sets of moves you can choose which must lead to either a draw or win.

What I'm wondering about and find interesting to try to deduce is, will you need to retract too many moves made by the AI to find a way to force a draw, making it computationally infeasable? It would be really cool if you could give reasoning why you will never be able to force either a draw or win.

Thanks for correcting my term. It seems Wikipedia thinks the term I mean to say is "determinacy" (though perhaps they refer to the same thing). But of course, I don't mean determinacy, because I'm looking for a tie-or-better strategy, not a winning strategy. I'll research game theory some day, but for now, I'm just pondering an interesting idea, and want to share it.

Could you point out the reasons to me more plainly? What I see has been said so far (by others) is:

• People play chess is to WIN, not have draws
• You are assuming your opponent will make a certain move
• Not every move leads to a draw.

I understand the first point, disagree with the second, and it would be nice to see some clearer reasoning for the third. One of the problems I know with this method is that it doesn't guarantee a win, and I have no way to prove that you cannot guarantee a win. Remember that I'm not arguing with anyone or making hard claims, I'm just interested in the topic. Any recommendations for must-read game theory textbooks?

 

Hey, no problems. Yeah.. Wikipedia can be iffy on highly technical terms.

Decidability is a game-theoretic specific term. Game theory originated as a strictly mathematical concept ( von Neumann and Morgenstern : Theory of Games and Economic Behaviour ), but was grasped upon by philosophers of logic and expanded upon from there. Although, that being said, there are earlier instances of the general type of analysis that you're seeking. Check out Hilbert and Godel (both mathematicians of note...).

In any case, basically, you're looking to find an algorithm to 'solve' the problem. The difficulty with chess is that, although the rules to the system are finite, the variables of decision involved are nearly infinite. As others have noted, one cannot calculate with certainty, how the opponent will choose to move.

I agree with the second and third, but the first is incorrect.
In some cases, the best way to play is to seek a draw. Technically speaking, in chess, the goal is not to win, but rather, to not lose.

To get a decent general idea of Game Theoretic approaches, check this out:

IEP - Game Theory

Enjoy.
I wish you good pondering.

 

But that's what I was saying. You can calculate (if you call it that) with certainty that the opponent is going to make one of the legal moves they have available to them. When I say "won't lead to a loss", what I mean is, if you make a move, then for every next move the opponent can make either there is a draw, or you win, or you can make a move that for every next move the opponent can make either there is a draw, or you win, or you can make a move that for every next move... etc. I'm talking about using a game tree. The problem I'm unsure of is how large that game tree will need to be. I'm talking about considering every single possible choice the opponent can make.

I see now that I was unclear, when I said "force a draw" I didn't mean force the opponent to make a set of moves that lead to a draw, I meant force the opponent to have a set of available moves such that none of them can lead to a win (for the opponent) with any of the opponent's subsequent available moves (if you respond to each of the opponent's possible moves in specific ways).

 

I'm working on a similar problem. I'm programming my handheld calculator (with 26 bytes of RAM (A-Z)) to play chess. I have programmed it to play noughts and crosses already, however when a computer plays the computer, the same game results.

Chess

The board

&01234567
801010101
910101010
A01010101
B10101010
C01010101
D10101010
E01010101
F10101010

Then simply overlay OR (/):

001
0/1
110

...onto the board to find each peices move. The central square (OR (/)) is true (1), and the surrounding eight squares show movement across three dimensions. If the movement if the same as the square it is on (i.e. if it is AND/OR) then the peice can move there, otherwise it cannot. If the peice can move, then it gets another turn from the new square. This process seems to show chess moves.

Please Register or Log in to view the hidden image!

As for the odds of winning, well I'm not sure because it's not just a code you have to type in (i.e. 7E-7D), it has to be a valid move. Plus you have the added complication of the opponents moves.

The game is essentially doing an (&&/) calculation (AND AND OR).

 

The realm of the mathematical tractability of chess is a well studied one, both from the computer science community and the game theory community. I don't mean this to sound insulting but I don't think you're going to get a solution just by asking on a forum where the posters aren't particularly familiar with the problem. If it were that easy it'd have been done already.

I'm a little confused how you got to the 1000 moves a second. If you're considering 10^30 moves and there's about \(\sqrt{10}\times 10^{7}\) seconds a year then you need about \(\sqrt{10}\times 10^{19}\) years to consider them all. That's around ten billions times longer than the age of the universe.

You're starting off with "Perhaps this could happen" and concluding with "It should be doable, lets try". Chess, despite it having well defined and easily programmable rules, is extremely complex due to its strategic nature. The game 'Go' even more so, where the number of moves each term is much larger and strategy even more complex. No Go AI exists which can challenge even medium level human players.

Questions like "What is your AI architecture" are very important. Do you get it to play every possible game and create a huge decision tree? It'd be impossible to run or store. How about some kind of heuristic method? Or perhaps a machine learning approach using support vector machines or neural nets? All of them have advantages and disadvantages but most run into problems when you get into huge dimensionalities and data sets. How do you train them? A genetic algorithm? Something else?

There is no single AI architecture, almost invariably 'intelligent' programs are 'simple' methods specifically tailored to the thing they are designed to address. They might handle one set of problems very well but fail utterly in others (that's what I mean by 'simple'). Few, if any, handle significantly different problem types well.

In the middle game brute force beyond something like 7 or 8 turns is not really practical. However, for end games supercomputers often use huge look up data sets because its possible to enumerate the most likely setups or general classes of end scenarios, ie 2 knights vs a queen or a rook vs a biship and a pawn.

If you're interested in writing such things start with simpler games where perfect drawing strategies are known to exist, such as noughts and crosses (or tic-tac-toe, depending on where you live), or perfect winning strategies, like connect 4. Then learn about how to program simple learning algorithms and see if you can implement something which ends up learning, through repeated playing, a strategy which is close to the optimal one.

Or perhaps something more fun, using genetic algorithms to play Super Mario!

 

I ran on the assumption that it takes 10^90 years to compute 10^120 variations (rather than 1 second per variation), meaning 10^30 variations can be computed in a year. That assumption was drawn from the quote of a 1950 paper, "Programming a Computer for Playing Chess".

Ah, yes. I hadn't considered that any AI powerful enough for the purpose would be too slow, and any fast AI not skilled enough. An ultimately skilled AI would be brute-forcing itself, reducing the problem back to where it started, whereas an ultimately dumb AI will lead to brute-forcing the problem once again when you have to retract its ill-chosen moves back to the start of the game.

Writing a learning algorithm would perhaps be fun. I got into this whole idea because I had been coding perfect AIs (tic-tac-toe, ghost, and nim), but I find perfect brute-force coding too... easy? I'd like to come up with some good heuristics. Perhaps I'll try a novice-level Go AI.

I'm still not convinced this approach would fail, though I see it's likely. I doubt it would be tried if someone had thought of it. It would take a very large amount of time (a year or two, if those numbers were right? Perhaps ten years or more, in reality? Fifty?) before you could get the sense that it's not going to succeed, and it would take the full length of the initial problem before you can be certain it will never succeed. Even if it succeeded, you haven't shown that it's impossible to do better than a draw.

I'm definitely not interested in writing something that would do this, but maybe someone else here is writing chess programs? I doubt it now, but meh. In any case, I'd rather see this is wrong than be unsure about it. Is the assumption of 10^120 variations in 10^90 years too idealist?

 

I thought Go was harder to predict than chess, no?


As to your question, I have no idea (actually, I'm too lazy to attempt to calculate it) how many gazillion years it would take for brute force computing to force a win or draw at chess. Also, I'm confused - you seem to conceptually switch back and forth between conventional procedural computational routines and some sort of "fuzzy AI". Which are you thinking of? Or perhaps both?

I do have a little (actually some serious) programming background and I'm a decent chess player.. What I don't know is how most computerized chess algorithms work. Do they try to analyze every possible move in order to find the "most likely to win" or the "most likely not to lose" strategy when computing the next move?


Also, if chess truly is not "winnable / decidable / determinable" then aren't we dealing with a "probability" issue? Meaning, wouldn't the best way to proceed be something along the lines of:

• Assume my opponent is a moron (easy enough, works for 90% of the population)
• Use any of the standard opening game moves.
• Inspect the reaction from my opponent.
• From this position, what is the quickest way to a win / draw?
• Determine what would be the simplest way for my opponent to stop that win / draw.
• Begin loop:
• Which move could I make that would prevent my oponent from defeating that strategy, yet still lead to the quickest win / draw?
• If I make that move instead, what would be the most likely way for that strategy to be blocked?
• Chron / Timer / # loops, then make a move.
• End loop

Proceed accordingly, based on the "most likely" to win / draw option - or the "least likely to lose" goal, whichever. This would limit the time involved to something less then 100 times the age of the universe, right? Simply adjust the number of loop iterations to whatever level you would like.

However, it seems you are looking for a "perfect" strategy, as opposed to a practical "How can I beat / tie the most opponents that I can?". I understand that my approach would not work for attaining that theoretical "unbeatable" solution.


In any event, my real question remains - does a computer (currently) play an offensive or defensive game? Or both? If the board is in any given position, does the computer look for the quickest way to a win / draw, or the best way to protect its assets? What is the general strategy? Can you give me pseudocode? (Just the basics)

BTW, this is just a question of curiosity... I mainly did database and website stuff, I have no vested interest in game theory - so if the question is inane or burdensome, don't bother...

 

Predict perfectly, yes. I don't know anything about advanced Go strategy, but from what I've played, it seems there are some simple enough heuristics that can be exploited for making a novice AI, though.

It's a bit of both. In your tree of possible outcomes, The 'player' whom you're trying to make win would make moves as decided by the AI (so one defined move on each player level of the tree), while the 'opponent' would make every legal move it has available (so ~30 moves on each opponent level of the tree). When you come to a node (endgame) where the opponent wins, you would step back to the last 'player' node up the tree, and start brute-forcing from that node. If all moves 'player' can make at that node lead to a loss, you step back yet again to player's previous move, and brute force from *that* node, which squares the number of outcomes you have to consider for this endgame situation. This continues until you find a move that at least forces a draw for that endgame.

The "fuzzy AI" makes moves for one player while the pure brute forcer makes moves for the opponent, then where the fuzzy AI loses the brute force method is used for the player.

The AI approach I know of is minimax, where the "most likely to win" strategy is precisely the "most likely not to lose" strategy. It's a recursive function (if I understood it correctly) with these properties:

• If the node is in your endgame database as a win, return 1
• If the node corresponds to a loss, return -1 for a loss
• If the node corresponds to a win, return 1 for a win
• If you are traversing to depth 1, return the heuristic for this node
• Otherwise, return the negation of the minimum of minimax computed on each child of this node, to a depth of (depth - 1).

You also need the first instance to return the best move coupled with the 'score' it gives. The last item on that list is the greatest win status you can force - the children are the opponent's nodes, so if there is a -1 it means you can force the opponent to lose. The heuristic would be some function that looks at qualities of the board, and determines how "good" that board is for the current player. It could look at spaces guarded, spaces guarded that the other player can move to, pieces threatened by either player, pieces possessed by either player, etc., and returns some value between -1 and 1, where 1 is perfectly winning and -1 is perfectly losing.

Determining whether it's 'winnable' is a much more difficult problem. The issue I'm thinking of is more to determine whether chess is 'drawable', and if so, get a drawable strategy. Getting a good AI is a different problem

Please Register or Log in to view the hidden image!

Though you know that already.

The 'offensiveness' of the minimax strategy depends on the heuristic, that is, what it values achieving as it progresses through the game.

Writing this now, though, I realize that if you're using minimax for the AI, you need to compute ~30^(depth) variations for each move of the player makes. If you can concurrently grow the main 'strategy' tree and the current 'what move do I make' tree, perhaps this could still be salvaged, but it would take something more like 60 years to compute (at least, I really haven't done the math), and that's only to the point of getting the endgames with your AI. There's still the backtracing for situations where you lose to deal with.

Seems this approach has hit a dead end.

 

Please Register or Log in to view the hidden image!

Sorry about that...

However, thanks bunches for the info - I've wondered offhand about the logic on chess computers for years. So thanks...

Please Register or Log in to view the hidden image!

 

I wasn't disagreeing with the \(10^{30}\) but your comment that equates to 1000 variations a second. It doesn't, its more like \(10^{22}\) a second, which is 10 billion trillion.

I'd say anything which relies on brute forcing is a 'dumb' AI. Its easy to solve problems if you have infinite computing power and memory. Humans do not yet we are 'intelligent' so we're doing something more than just brute force. Sure, better players can take into consideration more avenues of strategy and possibilities but they also work on levels of play novices don't.

I don't have any experience with chess coding but I do have with signal and image processing. Suppose you give a child a picture of a cow. You then give it a picture of a farm yard full of animals and say "Draw around the cow in the second picture". Even if its not literally the same cow a child can do it easily. Giving that to a computer is extremely difficult. The computer has to work out the outline of the cow in the first picture. Then it has to find the set of pixels in the second picture which form similar shapes, but not identical in shape or size and might be blocked by other animals. A brute force approach might be to consider every single possible combination of pixels in the second picture and to then ask "Which one best matches the first picture?" but then you have to say what 'best' means. Best outline? Best size? Best colour? Best texture? such an approach is even less practical than computing every single chess game. Yet despite all that there are algorithms which can indeed identify the cow and draw around it. Sure, they are more accurate if you have more computing power to hand but they work by being clever and not doing brute force.

Generally the methods which instantly spring to mind in how to solve something algorithmically are going to be the more inefficient ones. People devote their entire research lives to speeding up commonly used algorithms. I'm absolutely certain a huge number of people are appreciative of the person who developed the n log(n) fast Fourier transform!

A general rule of thumb in computer science is if you're doing it by brute force you're doing it wrong. This is why prime number encryption is currently 'safe', the only algorithmic methods known to cracking it boil down to brute force attacks.

Brute force attacks on chess are generally measured in multiples of the age of the universe.

There's 31 million = \(3 \times 10^{7}\) seconds in a year. You're asking for \(10^{30}\) variations a year, which is \(3 \times 10^{22}\) variations a second. Yes, that's a little idealistic. A typical modern computer does \(3 \times 10^{9}\) cycles a second so even if you could magically do 1 variation per cycle (in reality you'd likely need hundreds or thousands of cycles at least) that would mean you'd need \(10^{13}\) CPUs. Even allowing for quad and dual core PCs there aren't that many CPUs in the entire world. That's about 2000 computers for every person on Earth.

So yes, you're a little idealistic in your analysis.

 

Doing a "hard" solution of chess is still difficult, just due to the brute force computation required. But AIs capable of beating the best human chess players have already been developed - AI chess is considered "done" from a basic science point of view. The AI community has largely moved on to more difficult games (Jeopardy!, etc.).