Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is well known that solving Chess is practically impossible using brute force methods. I'm interested to know if there have been any serious attempts using alternate methods. What theory and mathematical tools have been developed to solve (in the weaker sense) Chess? What has been done in abstracting the rules of Chess into a workable mathematical framework?

share|improve this question
3  
According to chess.com/chessopedia/view/mathematics-and-chess there are less than 5 million "logical possible games." That may have seemed daunting ten years ago, but maybe in another ten it'll go the way of the four-color theorem. –  Robert Soupe Jun 28 at 6:47
    
It is computationally intensive to solve chess, but not impossible. There are finite board states, and if board states are repeated, you end up in a tie. So the game must take finite time, so the game is solvable. It would just be unfeasible using current levels of computer. –  Thoth19 Jun 28 at 6:51
    
There are several programs that can play chess, and a few that can play better than any human. Is that what you mean by "solve"? They use a combination of brute force and other methods. –  bubba Jun 28 at 7:08
6  
@RobertSoupe: somehow I find that number highly doubtful. Perhaps it's because with just 5 million games, someone would have solved chess in the time between our comments. Or perhaps because Wikipedia put it at $10^{123}$. –  Gina Jun 28 at 7:14
2  
As far as I can make out, when the article says "logical possible game", it means "board position that could feasibly be reached in a real-life game between experts". Not what I would call "logical"! –  TonyK Jun 28 at 9:59

1 Answer 1

I first started working on this question about 25 years ago when I tried programming chess AI onto a TI-81 calculator, which has a 2400 byte memory limit. I've been playing tournament chess for about 25 years as well.

the answer is yes there are ways to prove a position is winning or drawn. one example of a self-evident drawn position is the 'checkmate is impossible' example here:

http://en.wikipedia.org/wiki/Draw_(chess)#Examples

here is a similar theoretical discussion of a draw at the chess stack exchange forum:

http://chess.stackexchange.com/questions/354/is-this-endgame-position-a-theoretical-win-or-draw

the most common 'proofs' I see regarding chess is when human experts can prove a position is drawn but computers still assign a winning evaluation to either player (a computer evaluation of +2.0 or more for example). a 'fortress' in chess is when one side is at a disadvantage but proves a draw. in fact such pathological draws sometimes can provide inspiration and extra insight, and motivate computer chess programmers to re-work their engines until the correct evaluation is reached.

http://en.wikipedia.org/wiki/Fortress_(chess)

once you establish proofs about draws, it's easy to disturb the balance and prove a win. one way to prove wins is by counting tempi: http://en.wikipedia.org/wiki/Tempo_(chess)

former world champion Botvinnik perhaps was the first to make serious progress in the area you are asking about:

http://en.wikipedia.org/wiki/Mikhail_Botvinnik#Computer_chess

there may be various theorems or proofs, but if the person who discovered them is a competitive player they would be disinclined to share results. I imagine that across all books, academic papers, and message boards there is a large theory that has been developed but has never been concentrated into one place.

also... human experts can look at a position and often determine if white is provably winning, provably drawing, or provably lost. an example would be white has a queenside majority vs black's crippled kingside pawn majority.. which tends to win for white since she can create a passed pawn while black cannot. another example would be arguments regarding move opposition and which king achieves opposition. a subtle example would one side having a light-square or dark-square color complex and the other side having no compensation. such discussions largely revolve around chess 'initiative' and 'compensation'. this is all assuming perfect play.

http://en.wikipedia.org/wiki/Initiative_(chess) http://en.wikipedia.org/wiki/Compensation_(chess)

there is a general theory regarding about if chess is solved, will it be a win for white, draw for white, or loss for white. It is largely believed to not be a loss for white. IM John Watson discusses chess and information theory in his book 'Chess Strategy in Action'.

share|improve this answer
    
The values of the evaluation functions implemented in strong Chess programs would have a high correlation with the true outcome of the game in many positions, but are still only approximations. The only way to prove questions in Chess is to formulate the rules as a set of mathematical axioms. Mathematical techniques can then be used to answer questions exactly without resorting to brute force or approximations. My question is more directed at such axiomatic approaches. Surely this problem has been developed in the framework of mathematics before? –  user3766223 Jun 28 at 9:29
    
you can prove, actually prove, with a proof, results about chess within chess itself. it's robust enough that you can do that. one example of a self-evident drawn position is the 'checkmate is impossible' example here: en.wikipedia.org/wiki/Draw_(chess)#Examples –  user136920 Jun 28 at 19:49
    
that example is provably drawn since 1) no pawns can move 2) the kings can't move past the pawn barrier 3) the bishop cannot move past the pawn barrier. this type of analysis extends to very complex positions that are still far outside being solved by brute force yet are still theoretically, ie., provably, winning or drawn given perfect play by both sides –  user136920 Jun 28 at 19:59
    
I don't doubt that these aren't obviously drawn but the reasoning is not a mathematical proof and still relies on intuition. It would be impossible to extend this past trivial positions –  user3766223 Jun 29 at 0:21
    
I'm not dismissing the conclusions of professional Chess players. I'm a Chess player myself but that is irrelevant to the topic. My question concerns if anything has been done to abstract Chess into a purely mathematical (and exact) framework. The reasoning for the draw given by user136920 still fails as a rigorous mathematical proof. –  user3766223 Jun 29 at 1:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.