Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is a game like chess solvable ?

  1. Jul 27, 2006 #1

    loseyourname

    User Avatar
    Staff Emeritus
    Gold Member

    Why does this thread have no posts in it?
     
  2. jcsd
  3. Jul 27, 2006 #2
    Heh. Weird.
     
  4. Jul 27, 2006 #3
    Dont know. My intended post was:

    What I mean by solvable would entail some method of determining all possible outcomes from a single board configuration (most likely with computers). Theoretically this would result in only one possible outcome from the begining of the game (white wins, loses, or a draw) if both players play optimally (like tic-tac-toe), which is why I'd call it "solved". Most estimates I've seen place the total number of chess board configurations well above the total number of atoms in the universe by many orders of magnitude(10^120 for chess vs 10^75 for atoms), but does that mean that the game can't be solved? If you think it will be solvable when do you think it will happen?
     
  5. Jul 27, 2006 #4

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, chess is theoretically solvable.

    This is, in fact, one of the most naive approaches to developing a chess computer. You simply create a database of every possible board configuration, and compute the move to make in each configuration. Standard metrics can be used to compute the best move given each position. You end up with an enormous database which is the "solution" to chess, since you will have considered every possible move for every possible configuration, and determined the best for each.

    The problem with this approach is that number of configurations, as you mentioned, is enormous. The problem is that computers have nowhere near enough memory to store such a database. The "solution" is simply too bulky to store in its entirety.

    You can greatly reduce the size of the database with the realization that you really don't need to precompute and store ALL board configurations, only those that require lengthy computation. Most configurations have a single, obvious best move which can be quickly calculated through heuristics.

    A good heuristic algorithm (to calculate the easy moves on the fly) coupled with a large precomputed database of configurations (to lookup the hard ones) would comprise an essentially perfect chess player. This hybrid approach is probably already within the grasp of modern supercomputers, and will likely eventually be able to fit in the palm of your hand.

    - Warren
     
  6. Jul 27, 2006 #5
    I suppose it's possible that a heuristic algorithm/database hybrid might constitute a solution to chess as thorough as a complete database, I mean to the point where the game result (white ALWAYS wins/loses/draws) can be known before the game begins, but I see no reason to be sure. I'm not an expert on the subject but I doubt that "most" situations have an obvious best choice move when the immidiate goal from the onset is an unavoidable checkmate, or if that's not possible, a draw (material advantage, a piece's position, and things like center control are not directly relavent). It's possible (though highly unlikely) that white's "best" first move is moving the A column pawn up one square, because this may somehow be the only move that avoids his demise 30 turns and countless permutations later, yet it is definitely not considered a "good" first move by any current standards.

    A complete database might not be necesary if one particular player can be shown to achieve any of several board configurations that lead to a check sequence resulting in a final unavoidable checkmate, but this might not be possible.

    I find it interesting that the game itself may be "solvable", it almost makes playing chess to win seem as pointless as tictactoe to me. If a solution is currently achievable by super computers as you speculate might be the case I would be curious to know the outcome between two "perfect" players. I'm also curious as to why the solution hasn't already been found or published (maybe it's just not as interesting to other people as it is to me, or not worth a supercomputer's time).
     
    Last edited: Jul 27, 2006
  7. Jul 27, 2006 #6

    selfAdjoint

    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    I don't think the OP meant solvable through brute-force enumeration. For example checkers has a decision rule expressible in a sentence or two. Indeed one can ask questions like is chess NP-complete? For example could you show that solving chess would involve solving the travelling salesman problem (which given their definitions, doesn't seem intuitively outrageous to me)?
     
  8. Aug 2, 2006 #7
    That doesn't make sense - chess doesn't scale on the size of an input. There's no meaning to the "computational complexity of chess" - it's simply O(1). :wink:
     
  9. Aug 5, 2006 #8
    Chess provides for the aspect of "selective-suicide" during a thrust towards an achieved objective. That type of involvement renders computer computation very, very dificult.
     
  10. Aug 5, 2006 #9
    What do you mean?
     
  11. Aug 5, 2006 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think he's talking about sacrifices. E.G. sacrificing a pawn to obtain a positional advantage in the center, in the hopes that down the road you can turn that into a material gain.

    Or, sacrificing a bishop to expose the enemy king, in hopes that you can force through a mate (or at least capture some big material) before the enemy can defend himself.

    Of course, I'm told that the latter kind of sacrifice tends to be extremely risky against the better computers, since they tend to be very slippery.

    I don't know why he brought this up, though.
     
    Last edited: Aug 5, 2006
  12. Aug 5, 2006 #11
    From my understanding, what has limited chess programs to this point is their inability to think in the abstract. Even if you decided what is statistically the "best" move in every given situation there are other moves you can make that gain long term advantages that can be exploited. Someone already mentioned sacrifices to control the center. Other things you can do are seemingly poor trades that open up an area of the opponents line that make it difficult for them to defend and then pressing the hole...tying up pieces defending it which gives you openings for a different front elsewhere on the board, etc. This is why (well...until Deep Blue came along) super computers have been largely unable to beat the pro players at chess. They may have an advantage in processor power, but they lack the flexibility...or something of the human mind to improvise and plan for the endgame.
     
  13. Aug 6, 2006 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If there are other moves that you can make that gain long term advantages that can be exploited, then it's not statistically the "best" move, now, is it?

    Computers can do that, by the way. The scoring systems computers use account for a lot more than just material value. For example, see http://www.frayn.net/beowulf/theory.html.
     
  14. Aug 6, 2006 #13

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If you presented all the members of the grandmaster community with an entire chessboard in some specific state, would they generally all be in agreement about which move to make next?

    - Warren
     
  15. Aug 6, 2006 #14

    -Job-

    User Avatar
    Science Advisor

    I don't agree. In this case the input to the problem is the algorithm(s) that each player is using. The problem of determining which player wins, black or white, is solvable in a deterministic manner (assuming that no player is running a randomized algorithm) and its complexity is dependent on the size of the algorithms.

    To simplify, suppose each player runs the same deterministic algorithm. The problem of determining who will win is solvable, and its complexity is f(n), where n is the number of bits used to represent the algorithm in some predefined architecture.
     
  16. Aug 6, 2006 #15
    The "best" move is simply the one that when compared to other possible moves yields the highest stastical probability of leading to a sequence that will win the game. This is largely how computers on "master" levels pick their moves today from how I understand it, they run through all the different possible pathways from a move to the end and choose the one that has the highest probability of leading to a win. The problem is that the computer "re-evaluates" the entire situation after every move. It cannot say to itself, "making this move puts me in a disadvantage in this way, but I want to get rid of both his knights early on anyways so that I can build my pawn line freely without worrying about them jumping it." That sort of thing. If the computer ran through the scenarios it would generally pick the "best" move to make in any given situation, and that is both it's strength and it's weakness. It wins on percentages, it loses to creativity.
     
  17. Aug 6, 2006 #16

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No it's not -- they were talking about perfect play. It takes O(1) time to, given a board position, return one of the following:

    (1) A move from which a perfect player can guarantee a win.
    (2) A proof that a perfect opponent will win no matter what you do.
    (3) A move that will guarantee at least a tie, and a proof that a perfect opponent can avoid losing.


    No it's not -- the size of an algorithm has little bearing on how long the algorithm will run.



    A computer can't compute that (yet). They simply compute something they hope is a decent approximation.


    No it doesn't. A decent chess program will remember all of the relevant analysis it did from the previous turns, and continue analysis from that point.


    But I think you meant the idea of choosing a plan and sticking with it. You have to remember that advice is meant for weaker players (and this is essentially true for any game, and even real life). A common problem is that the beginner might come up with a new idea in the middle of a game, and try it out even though it doesn't work in the current board position. By sticking to a plan, it makes it more likely that you will take advantage of the current situation.

    But the expert has the experience to realize which ideas won't work from the current situation, and the expertise to fully exploit the current position when switching over to a new plan. For the expert, choosing a plan and sticking to it will degrade his game.


    Why not? It's easy enough to implement a heuristic that rewards having a good pawn line when the opponent doesn't have any knights.


    Creativity is usually a bad thing. :tongue: In fact, computers are well-known for punishing "creative" play.

    But if you meant to talk about strategic play, then yes, humans are currently better than computers in the strategic domain for chess.

    That isn't necessarily because computers are incapable of strategic play -- it's just that computers were quickly seen to excel at tactics, and most of the research was spent improving tactical play, and discovering how to include more interesting factors into its evaluation methods.

    A computer, for example, will happily discover and execute an 8-move combination that sacrifices a pawn for what it believes is a greater compensation in terms of board position.
     
  18. Aug 6, 2006 #17

    -Job-

    User Avatar
    Science Advisor

    Are you sure? Rach3 said that chess doesn't scale on the size of an input in reply to selfAdjoint's idea of asking whether "chess is NP-Complete", while the OP put forward that:
    ... by which the "chess" problem, being solved in determining "who wins", is the problem of determining which player will win. So i don't see where you're coming from, but whatever, rather than get into a quote cycle, i'd rather argue the following:
    Is it possible that no one will win?
    Say the two kings end up by themselves, running from eachother?
    That seems possible, and it leads to an interesting thought.
    For example, assume here that this "chess problem" is the problem of, given two algorithms and which goes first, determining who will win.
    So our algorithm for solving the "chess problem", takes in two algorithms, and tries to determine who will win.
    I think this is equivalent to the Halting problem, because, suppose we build an algorithm which is the sum of the player's algorithms (meaning an algorithm where algorithm A goes, then algorithm B goes, then A again, etc). Then the problem becomes that of asking whether this compound algorithm will end with A (A wins) or B (B wins) or whether they tie (the algorithm doesn't Halt).
    It sounds like the halting problem (since we can build any algorithm from two algorithms), and means that no single algorithm can ever determine, for any two possible players, who will win.
    Now that is interesting. Does that go against what you were saying Hurkyl?
     
    Last edited: Aug 6, 2006
  19. Aug 7, 2006 #18
    That was my thought as well. Chess is sometimes used as an example of a formal axiomatic system, and it seems to me a stalemate equates to an undecidable theorem. Don't know if this analogy really holds up though.
     
  20. Aug 7, 2006 #19

    Curious3141

    User Avatar
    Homework Helper

    Even if they are all in agreement on the move they perceive to be the best, they may not actually be right! It doesn't even have to be a complex midgame position, I remember a chess book with the example of an endgame with a paucity of remaining pieces. It was supposedly an "exhaustively analysed" position (by humans, of course, this was in the older days before computers were used extensively). The master writing the book had posed the problem to one of his novice students and asked him to find the best continuation for one side (to win the game and avoid stalemate). The novice came back after a day's deliberation asking what was "wrong" with Re8 (or some such move).

    The master goes on to say, "As I was preparing some instructive rebuke, I suddenly realised I had none. The move was actually better than the accepted "best continuation"".

    A non-intuitive solution found by a novice in a relatively simple position turned out to be better (mate in fewer moves) than the accepted wisdom of the grandmasters who came before.

    Just for fun, I set my (lousy) Kasparov 2000 Chess computer this problem and asked it to continue. While that computer was very weak, it did have the strength of being able to continue computations indefinitely until the battery ran out.

    When I stopped its cogitations quickly, it moved weakly. A little more "thinking time" and it replied with the accepted "best" variation. But it was only after I had let it analyse the position overnight that it managed to find the ideal continuation the novice had been able to find.

    I use this instance as a reminder of how rich the game of chess really is. The move really is very counterintuitive, most players would've chosen to attack the opposing king immediately with the rook, but this contination seems to be neither here nor there at the outset, yet actually attained the goal of a victory more efficiently.

    Which is why I disagree that using heuristics in a "complete solution" to the game is acceptable. Heuristics can be wrong, and one misstep in the tree of the perfect game will lead to a ruined analysis. Brute forcing every step of the way is the only sure way to solve the game completely, and we're nowhere near being able to do so computationally.
     
  21. Sep 6, 2006 #20
    Chess is a boring program for computers, if you want a real challenge try to make a computer play GO.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Is a game like chess solvable ?
  1. You gonna like this game (Replies: 40)

Loading...