Nine Men's Morris has been solved by Ralph Gasser in 1996 (Draw).
So has Qubic (4x4x4 Tic-Tac-Toe) by Patashnik O in 1980. (First Player Win)
Connect Four by James Allen in September 1998. (First Player Win)
Let's see John W. Romein and Henri E. Bal from that wonderful games research group in U of Alberta solved Awari in 2002. (Draw)
Read Victor Allis' PhD thesis for a good overview on finding game theoretic results of games. He invented the proof-number search technique that he used to (re)solve Qubic and Connect-Four. http://www.cs.vu.nl/~victor/thesis.html
Nine Men's Morris is not researched actively anymore, but Ralph Gasser's paper is often cited in any paper that deals with artificial intelligence in games.
Of course, even though the game might already be solved, that does not mean that it is not fun to play...
Why tackle Go instead of Chess?
on
Solving Chess?
·
· Score: 2
*sigh* Hopefully, this should be the last thing I will append onto my own thread.
For a complete survey of Computer Go hit this link where I got most of my material.
As I mentioned before, Go has a even larger branching factor than chess which does some implications. A brute-force search method cannot be used in Go. This implies a whole paradigm shift in tackling Go. Second, this means that perhaps even when faster machines appear, they might not improve a Go program's playing ability by a lot. Rather, to improve Go programs would require improving the algorithms.
So why tackle Go instead of Chess? I feel that to make a computer play Go effectively you would need to be able to recognize patterns and act on intuition due to its impossibly large search space. i.e. brute-force searching is secondary (you still need it to determine life/death of groups) in this case. You need to incorporate tons of knowledge into Go programs, much more than you would need in Chess programs. In addition some form of functional approximation (neural networks?) will be needed to abstract all the knowledge and apply it effectively on the board. Unfortunately, many experiments involving neural networks and Go have been failures. This suggests that some new technique will be required to play Go well.
If this technique is found, the same method could possibly be applied to many areas that other people have brought up in this thread. e.g. Computer chess then can be based on pattern recognization and these programs will probably play more "human-like" and Computer vision problems can (big perhaps) can benefit from this.
On the other hand, solving chess would simply require many many more machine hours of number crunching and would have applications to other fields of computer science.
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!!!
Slashdot Mirror
Nine Men's Morris has been solved by Ralph Gasser in 1996 (Draw).
So has Qubic (4x4x4 Tic-Tac-Toe) by Patashnik O in 1980. (First Player Win)
Connect Four by James Allen in September 1998. (First Player Win)
Let's see John W. Romein and Henri E. Bal from that wonderful games research group in U of Alberta solved Awari in 2002. (Draw)
Read Victor Allis' PhD thesis for a good overview on finding game theoretic results of games. He invented the proof-number search technique that he used to (re)solve Qubic and Connect-Four. http://www.cs.vu.nl/~victor/thesis.html
Nine Men's Morris is not researched actively anymore, but Ralph Gasser's paper is often cited in any paper that deals with artificial intelligence in games.
Of course, even though the game might already be solved, that does not mean that it is not fun to play...
*sigh* Hopefully, this should be the last thing I will append onto my own thread.
For a complete survey of Computer Go hit this link where I got most of my material.
As I mentioned before, Go has a even larger branching factor than chess which does some implications. A brute-force search method cannot be used in Go. This implies a whole paradigm shift in tackling Go. Second, this means that perhaps even when faster machines appear, they might not improve a Go program's playing ability by a lot. Rather, to improve Go programs would require improving the algorithms.
So why tackle Go instead of Chess? I feel that to make a computer play Go effectively you would need to be able to recognize patterns and act on intuition due to its impossibly large search space. i.e. brute-force searching is secondary (you still need it to determine life/death of groups) in this case. You need to incorporate tons of knowledge into Go programs, much more than you would need in Chess programs. In addition some form of functional approximation (neural networks?) will be needed to abstract all the knowledge and apply it effectively on the board. Unfortunately, many experiments involving neural networks and Go have been failures. This suggests that some new technique will be required to play Go well.
If this technique is found, the same method could possibly be applied to many areas that other people have brought up in this thread. e.g. Computer chess then can be based on pattern recognization and these programs will probably play more "human-like" and Computer vision problems can (big perhaps) can benefit from this.
On the other hand, solving chess would simply require many many more machine hours of number crunching and would have applications to other fields of computer science.
And oh, I forgot to mention a few things. :)
Go is a 4000 year old oriental game, invented initially by Chinese, moved to Japan and Korea, and currently dominated by Japanese and Koreans.
The Web Go Page Index
This will be the only index on Go you ever need.
Mick's Computer Go Page
News and informataion about computer programs that play the ancient oriental game of Go
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]