Solving Chess?

R. Jason Valentine asks: "One of the more complex problems that computing has tackled has been the game of Chess. The rules are simple, the strategy complex. We now have computers, based upon current technology, that can play as good as or better than the best humans. However, the current computing power is still far from answering the age old question: Is there such a thing as a perfect game of chess?" Anyone have spare processor time on a Beowulf Cluster? Or maybe this could be another project for distributed.net? Update: 04/30 10:38 by J : Remy de Ruysscher writes to say he's still working on distributed chess; to join his mailing list, email him.

"For those who don't know, it is theorized Chess may be a solveable game -- i.e. one that if played perfectly, yields a predictable outcome -- be it a victory for white, black, or a draw. There are two new computing technologies that *may* be able to answer this question -- DNA computing and quantum computing. DNA computing is advancing fairly rapidly, and recently the largest quantum computer was devised -- a mere 7 qubits.

I am admittedly completely ignorant in algorithms used by computers to calculate moves, but I was wondering if anyone had any ideas on which technology would be more likely to solve the game of chess, and how one would devise a method to do so."

Comments

Re:Some numbers.....

[Hobbex]

In the same chapter of Applied Crptography, BS goes on to calculate some theoretical maximum values for how fast a computer could perform a brute force crack, using thermodynanics to calculate the minimum energy necessary to change one bit.

According to his calculation, a perfect computer kept at background temperature, powered by the energy from a perfect Dyson sphere around our Sun, could do 2^187 bit operations in a year.

All the energy from a supernova could power such a computer to do 2^219 operations.

10^120 = 2^398 is 8*10^53 Supernovas, or the annual output of 3*10^63 Sun sized stars. Something tells me that we can have as many quantum and DNA computers as we want, chess will hold out.


-
We cannot reason ourselves out of our basic irrationality. All we can do is learn the art of being irrational in a reasonable way.

Not true

[p3d0]

You can get an exhaustive search of a tree without searching every node in the tree. Pruning techniques can remove many, many orders of magnitude from the amount of nodes that need to be search.

Have a look at Branch and Bound for example.

I have implemented a circuit partitioning engine using branch and bound that only searched 1% of the possible partitionings, and was still guaranteed to come up with the same solution you get with a real exhaustive search. This was with very small circuits; the larger the circuit, the smaller proportion of the nodes need be searched.

So, the raw number of possible games is not really an issue, even if you want to do the equivalent of an exhaustive search. If there happens to be a good pruning technique, the number of nodes in the tree becomes almost irrelevant. Branch and Bound may not work for Chess, but perhaps another technique would make the problem solvable by current technology.

--
Patrick Doyle

Chess vs Go

[yjlim]

Chess has been the focus of most of the AI research of western world for the last, I don't know, twenty or so years. It is fairly clear that computers have improved by leaps and bounds in this time. Computer programs running on Intel computers have beaten grandmasters in tournament time. (e.g. Rebel and Deep Junior)

However, the game of Go/Weiqi/Baduk is a complex computational problem even when compared to chess as stones (pieces of Go) can be placed anywhere on a 19x19 board, making for a very large branching factor in the selection of each move, whereas pieces in chess are constrained to a much smaller set of legal moves (branch factor ~40). Go is also a loopy game, in other words, it has a game graph with cycles. (This occurs when you have double kos for example)

The branching factor plays a major role in the different stages of both games (beginning, middle and end). In the opening stage of chess, there are many well-known openings (Ruy Lopez, King's Gambit, blahblah) and these are often followed by both players (including the computer who really loves it, who can forget the last game of Deep Blue vs Kasparov?) upto 10 or more moves. In Go, the number of sensible openings is much larger, and whole game openings are rarely followed for more than about 5 moves. However, there are sequences of moves in local skirmishes, known as joseki, that reflect local optimal play (for both sides) in tactical battles in the corners. Skill in the use of joseki libraries lies in selecting the right joseki to optimise interactions with stones on the whole board or diverge from the known sequence to serve other interests. In the endgame stage of Chess, massive databases have been made to solve specific endgames. Computer programs thus can effectively wait and see if its puny human opponent makes a mistake when it finds itself in a favourable position. In Go, to the best of my knowledge, there has been a lot of research that have produced very good (even locally optimal) Go endgame programs but none of the existing Go programs in the market play even a decent endgame.

The quality of Go programs is looking better these days. The best programs can give an average amateur a good game at best. The ranking system of Go is (in ascending order), 30kyu-1kyu, 1dan-9dan (amateur), 1dan-9dan (professional). The highest ranked program Handtalk was awarded a 3kyu, but I remember reading somewhere that the author felt that it was due more to the fact that it was then the best computer program rather than its true ability that the Japanese Go association awarded the rank to it. (they are ranked around 15kyu in Internet Go servers) What does this entail? It means that you can pick up Go, play it for a about a month or so, and you can probably beat the best Go programs out there more then 50% of the time! Try doing that with chess!

In conclusion, while chess and checkers have not been solved, it is my opinion that computers are already better then any human being. (can be argued against for Kasparov vs Deep Blue but we will leave that aside) The point of my discussion? Forget about pumping more man hours into chess and reach for the pinnacle of AI research, Go!!!

That's my 5 cents.

[No Flames Intended]