Slashdot Mirror
Computer Cracks 5x5 Go
gustgr writes "The American Go Association is reporting that Go for the 5x5 board has been solved by the computer program MIGOS, reports the program's creator, Erik Van Der Werk, a professor at the University of Maastricht in Holland. At about a quarter of the full-board version, 5x5 go is miniscule, similar in scale to "solving" 2X2 chess. The fact that a programmer would even consider this a noteworthy challenge is itself a remarkable testament to the game's complexity. Van Der Werk's approach is described in detail in an
article at the Netherlands Organization for Scientific Research (NOSR)."
If computers can beat chess grandmasters and similar feats, how is this anything special?
People on Slashdot probably fall into a different demographic, but I've found that people generally haven't heard of Go. They'll recognize a chess set by site, but they see Go and if you're lucky they assume Reversi or Othello. I was in the student lounge with a friend who was teaching me how to play Go, and somebody asked what game we were playing. When we told him, his reply was, "Go? I thought that was a card game."
I've always believed within my lifetime, chess would be solved. In other words, a computer would come up with the perfect solution to chess so that no matter what moves you possible make, out of the, i dunno, billions, trillions, or higher number of possible moves, the computer knows how to beat you. The simplest comparison I can think of is tic-tac-toe. If you've played tic-tac-toe enough, you've learned that no matter who goes first, someone can always force a cat (tie game). I wonder, is it possible to always force a draw in chess or might it be that whoever goes first can always win? Sure the computing power to figure this out is beyond anything we have now, but with quantum computing and other advancements, I expect to see chess solved in my lifetime.
There is a neat leaning variant called Quic k Chess.
Note that a liberty is an empty spot on the board that is either next to your stone or can be reached by moving across your stones horizontally or vertically. This is great for computer scientists who don't know the game yet, http://brooklyngoclub.org/jc/rulesgo.html:
The Alternating Rule:
Two players, called Black and white, keep alternating moves till the end of the game. Black plays first. A move by a player begins by his placing a stone on an empty intersection of the go board. The first player who cannot put down a stone without breaking a rule loses the game.
The Rule of Capture:
After a stone is placed on the board, all enemy stones which have no liberties are removed. A player's move is not finished until this phase has been completed.
The Rule for Suicide:
Suicide is illegal. Precisely, after a stone has been played, and after the rule of capture has been applied to his enemy stones, if the stone has no liberty, then the move was illegal.
The SuperKo Rule:
A player is not allowed to place down a stone if, after the rule of capture has been applied, the resulting Board position has appeared previously in the game.
Transcend Humanity. Please.
Everytime chess gets mentioned on /. (ok I know it's a go story but you know the comparisons will start) I like to post a link to this short story written by Arthur C. Clarke. I originally found the story through someone else's /. post
http://www.research.ibm.com/deepblue/learn/html/e. 8.2.shtml
It has to be a black win or a tie. If White has an advantage, Black can just pass the first turn, effectively trading places and giving him White's advantage.
I found the meaning of life the other day, but I had write-only access.
5x5 go is miniscule, similar in scale to "solving" 2X2 chess
Sorry, but that's like a full chess board with the pawns removed (if even that much).
5x5 Go is still fairly complex. Although the article is old (2002), I'd still like to see a caltulation time comparison.
2x2 chess can be solved in a manner of seconds/microseconds. 5x5 Go might take a few days to brute force it.
It would seem that it could be very different. There are a lot of these computer-only competitions and tuning for that will be very different from tuning for humans online.
Transcend Humanity. Please.
An initial dig brings up terms like "EXPTIME-complete" which doesn't match anything I remember from my undergrad algo class. Apparently, there is a rule modification that makes EXPTIME-complete games EXPSPACE-complete. This makes even less sense to me. Explanations in lay speak are appreciated.
To have a program which has solved Go (unlike the best chess programs, which are merely at the strength of Grandmasters)
It should be noted that even on a 9x9 board (let alone 19x19), competent amateurs can beat any computer program.
19x19, 13x13, and 9x9 (the "standard" sizes, though 7x7 is fun sometimes), require totally different strategies. 9x9 is pure life and death, 13x13 is mostly fighting, and 19x19 requires a good understanding of balancing influence for defined territory (don't spread your stones too thin while not letting them get bunched up).
For all who don't play go or are new to go, the biggest problem with the 19x19 and even 9x9 computer programs is that the computer can't see the dual threat someone might play with a sequence of moves. For example, you can start to attack a specific section of the board, and use what you played to grab hold of an even larger section of territory, or even kill a large portion of their stones. It's easy to fool the computer in Go.
from the website;The solution was found at 22 ply deep (23 for the empty board).(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz)
4-hours is on a single p4 machine is just a joke.. but good point though, solving a game takes alot of time. University of Alberta (Canada) have been working on solving checkers (which is a much simpler game) for years. I think they are about half done with that. They are just using search, as checkers has low branching factor compared to Go
Van der Werf also investigated learning techniques, which are used in games such as backgammon
I belivie this is the way to be able to create a decent Go program, by learning (Reinforcement Learning, because Backgammon techniques). Brute force search gets boring, no matter how advanced it is!
Since computers have started to beat strong chess players, it *is* taken for granted by many that computers can beat reasonably strong people with today's processing power.
Presently, if a typical geek started playing Go, they would get their ass kicked by the weakest computer for a week or two.
After a month, they would be winning the odd game, if the computer gave them a 3-stone headstart. (Like 3 free moves to start in chess).
After three months, they would win some games in an even match against the weaker programs (Turbo-go)
After six months, they would be winning against a 3-stone or higher handicap for the computer.
Then they find a stronger Go program.
They start to lose every match again.
After another month or so, they start to win on the weaker levels.
Take it six months ahead, and they are smashing the computer in an even match with no handicap, playing white (white moves second) or at lower levels against a 3 or 4 stone handicap.
The only thing that makes the game playable against a computer is that Go has an incredible handicapping system that lets uneven players play against each other.
So what makes this story interesting? Aside from the brute strength issue?
The first moves of the game, often in the corners in roughly a five-by-five area (Joseki) are only recently being evaluated for best move potential...
That can affect the outcome of professional matches played for big $$$$.
But more importantly for people like me, I can't play humans much... Kids, wife and home environment mean I can't spend 30 minutes undisturbed, so playing against human opponents is out for me.
Any technology that makes computer programs stronger, improves algorythms or makes me play harder will keep my morning bus trips interesting.
Because Go programs have got a long way to go if they are easily defeated against a human opponent with just 1 year experience.... Who would be easily classed as a novice let alone just a weak player.
GrpA
Enjoy science fiction? "Turing Evolved" - AI, Mecha, Androids and rail-gun battles. What more could you want?
Eventually we may have the horsepower to brute-force win every game at 19x19 but I wonder if it might be more economical to program computers to play the same way that people do. (The father of one of my friends seemed to have all of Alekhein's games memorized. We couldn't do anything that he hadn't seen before.) By using pattern recognition we might be able to get a more capable game sooner. You wouldn't have to store all possible games; only the good ones. If someone blunders while playing the computer and produces a game it hasn't seen before then it could probably win by brute-force calculation. If someone does something different and wins then the computer has another game for the database. The game is symmetrical in a way that chess isn't and that would reduce the number of games stored by a factor of at least four.
Seems kinda obvious so there must be something wrong with it but I'm not sure what it is.
"Scoring 100,000 boards per second" is the catch - there is no good way to score. How do you know what a move is worth without knowing its effect? A move that looks seemingly awful, and suicidal, might be a brilliant move whose effect develops 25 moves later, or 50 moves later. The only true way to "solve" is not to consider all game states, but to consider all possible paths, or sequence of states to a state where no more moves are made. (note: the board never gets completely full, game stops before, when no more territory can be made, and playing into enemy territory would be suicide inviting a pass from the opponent while the invasion stones still being dead, increasing the enemies points.) Now take those 847,288,609,443 possible states, and consider all the sequences through which you can travel because you can't just look at a position and "evaluate it" without knowing the "future" it holds (don't forget captures that give you back empty spots that can be played again.) Actually, knowing all the possible "reasonable" end states, then tree searching backwards on how you can arrive at them might be a better way than starting forward from an empty board. Basically knowing the "future" of a position, or all the "futures" that you get to from a given position, could be a better way to go about things.
I have been interested in computerized Go for a while now, but have never actually gotten my feet wet in the subject.
One approach I have always wanted to try is this:
set up a massive neural net that takes the state of the entire board as input, goes through way too many intermediate layers, and spits out a preference for spots to play. The state of the neural net could be exhaustively described with a few tens of thousands of [0,1] doubles.
Then set up "breeding" algorithm, make a few hundred instances of the program, each with its own neural net, and then have them pretend to be users on an internet Go site. Don't try to understand how they play, just let them figure it out. You could even, on occasion, let them play eachother...
I don't know if this would produce a good genome ever, but I'd be interested to see where it went regardless.
Does anybody know if this sort of thing has been tried before?
"I fully expect someone to breathlessly explain the Great Goodness that is Chess."
You asked for it...
Each game of chess means there's one less variation left to be played. Each day got through means one, or two, less mistakes remain to be made.
Not much is known of early days of chess beyond a fairly vague report, that 1500 years ago two princes fought though brothers for a Hindu throne. Their mother cried, for noone really likes her offspring fighting to the death. She begged them stop the slaughter with her every breath, but sure enough one brother died.
Sad beyond belief, she told the winning son "You have caused such grief, I can't forgive this evil thing you've done." He tried to explain how things had really been, but he tried in vain; no words of his would satisfy the queen.
And so he asked the wisest men he knew the way to lessen her distress. They told him he'd be pretty certain to impress by using model soldiers on a checkered board to show it was his brother's fault.
They thus invented... Chess!
(now there's some REAL Slashdot lore for ya)
These people looked deep into my soul and assigned me a number based on the order in which I joined.
Honinbo Warrior was coded in UCSD Pascal and really did not play that well, but my boss and a few friends talked me into running ads in some Apple II magazines and marketing it. Working on that program was a fun obsession that lasted about 1 1/2 years.
Go is such a great game. In the 1970s, I got to play exhibition games with Miss Kobyoshi (women's world champion) and Mr. Lee (national champion of South Korea). The high level of their play really blew me away - getting slaughtered was a surprisingly great experience.
The Gnu Go program plays a good game, BTW. It is best to play against human opponents, but give Gnu Go a try also. Just like studying chess, if you get into playing Go, make sure you study complete master games: studying opening, middle game, and end games in isolation just does not cut it.
When you're dealing with a ply tree, it's relatively straightforward: the score is positive infinity if the board wins, negative infinity if the board loses, 0 if no path to a win is possible (tie boards or unknown boards,) and +-inf +-epsilon/ply for any board whose path towards a solution/solutions are known.
How do you know what a move is worth without knowing its effect?
Uh, when you're solving a game, there's no such thing as a move. You consider only board states, not the moves which lead to them, except in determining in which order to evaluate states. In this way it's trivial to understand how the value of a board in an infinite cycle between two paired positions - say, two kings moving back and forth between their same two cells each turn on a chess board - have up to four board scores through which they oscillate (unless there's a terminate-at-N-moves rule like in chess, but whatever.)
The only true way to "solve" is not to consider all game states, but to consider all possible paths
Game theory 101: the board states are the only thing there is. There are no "paths" - there is no difference between a board which has had a cyclic move applied to it ten thousand times than one which hasn't gone through them at all.
Solve has a very specific mathematical definition here - that the perfect response is known for every move. For games of no chance and perfect information such as go, chess and so forth, the traditional way to handle this is to create the entire move ply tree and then follow through the paths of least risk. When that tree is completed, you know for every possible board state every possible result of every move, and therefore know what exactly the best move is.
In this way you can find out that some games are balanced (tic tac toe, for example, is always a tie with perfect play with both sides) whereas other games are unbalanced (with perfect play by both sides, the second player will always win at connect-4; there is nothing player 1 can do.)
The reason chess remains unsolved is that its solution tree is so preposterously huge that even by modern computing standards it's just an absurd thing to want to attack, even given twenty years and positing 20 years' hardware development.
By the way, what I described above is not the only way to sove a game; if you'd like to find out how the branch of mathematics called Game Theory works, I recommend the primers "The Compleat Strategyst" (yes, it's spelled like that) and "Game Theory: a Nontechnical Introduction."
Common sense as what you're saying may seem, John von Neumann proved you quite wrong in the early 50s. I suggest you read up before challenging these terms; they're very well defined.
(note: the board never gets completely full, game stops before, when no more territory can be made, and playing into enemy territory would be suicide inviting a pass from the opponent while the invasion stones still being dead, increasing the enemies points.)
Er, yes, I know how Go works, and that's what I was referring to when mentioning that I was counting impossible boards. The number I quoted is the mathematically-derived high end cap on possible board definitions as a simple string of radix-3 digits. Observing that you can reduce the solution space here does you no good: you're only making my job easier.
Now take those 847,288,609,443 possible states, and consider all the sequences through which you can travel
That's a giant waste of time. Watching the ko cycle doesn't change the board, and since Go is scored not on held piece count but rather difference in held piece counts, the scores aren't changing either. It really doesn't matter how you got to a board - if you play squares a,b,c,d,e,f in order then the next game you play f,a,b,e,c,d, nothing has changed; your opportunities are still exactly the same.
because you can't just look at a position and "evaluate it" without knowing the "future" it holds
StoneCypher is Full of BS
The number of potential moves grows way faster then in chess
Which is a problem, but not the main one. The real advantage of computer chess over computer go is the relative ease with which the leaves of the search tree (e.g. all positions after n moves) can be evaluated statically. In chess you can perform excellent static evaluation by counting material, mobility, king safety and maybe a few other features. In Go, static evaluation is considered difficult for an expert, let alone a computer.
How did the parent get moderated "Informative"?!?
There are 20 potential moves in the first iteration for chess, and exactly 361 (19*19) for Go.
There are around 10^120 possible chess games, and around 10^760 possible Go games. That's why the milion-dollar prize for the first program to beat 1-dan Go player is still not taken.
He-he...
;)
Funny how it was the American Go Association who reported this...
They were always a bit slow compared to the Dutch in mathematics.
I've read about this and 6x6 being solved a *long* time ago already here:
http://senseis.xmp.net/?SmallBoardGo
You might be referring to this game.
i ge n_1959/Takagawa_GoSeigen_1959_0.htm
http://jhubert.club.fr/Go/Parties/Takagawa_GoSe
I'm not sure what you're saying about the result is correct. I advise you to read the page i've linked above and google around for other information related to the situation.