Slashdot Mirror
Cracking Go
prostoalex writes "IEEE Spectrum looks at current trends in artificial technology to crack the ancient Chinese game of Go, which theoretically has 10^60 potential endings. Is conquering the game via exhaustive search of all possibilities possible? 'My gut feeling is that with some optimization a machine that can search a trillion positions per second would be enough to play Go at the very highest level. It would then be cheaper to build the machine out of FPGAs (field-programmable gate arrays) instead of the much more expensive and highly unwieldy full-custom chips. That way, university students could easily take on the challenge.'"
What about a Bew....nah nevermind.
A computer will never beat a kid possessed by the ghost of an Edo period Spirit!
Ask not what you can do for your country. Ask what your country did to you
But don't expect to finish the game yourself.
Engineering is the art of compromise.
Using an exhaustive method is silly in a realm of 10^60 possibilities. Obviously human players, with much more finite resources (computationally that is) can do a much better job. Why not spend more time and being able to analyze the board better, and mimic the decision making patterns of the masters. I realize this has already been tried, and is still being worked on, but exhaustive search just seems like a waste of time and effort. My .02
je suis parce que j'aime
My favorite game.
First time I played online I had my ass handed to me by a precocious 12 year old. Ah well, the memories.
*Alot* more complex and tactical then Chess, believe it.
See the rules at: http://www.britgo.org/intro/booklet.pdf
Play online here: http://www.pandanet.co.jp/English/
I recommend installing glGo and having a go vs. computer (on the easiest setting there is).
Enjoy, I do.
I'm not an active Go player anymore, but I used to me. And the current state of artificial Go intelligence is pretty sad. The best junior players in the world (10-13 or so, IIRC) can beat the very strongest computer Go programs, and they're literally orders of magnitude worse than the best human players.
Playing Go is more than just searching a lot of positions. The game is _very_ subtle. To even understand how a professional 9 dan player (i.e. the very highest ranked players) plays every move in a game, you really need to be at least a 7 dan or so -- anything less than that and the moves just won't make a lot of sense. I have the feeling that it will be at least a decade (but probably much longer) before computer opponents can beat professional players, and even longer than that until they can beat the very best human player.s
#include ".signature"
Checking all possible moves is unwise. What you do is design a nice directed heuristic, say, a multi objective algorithm, and train this to compute a reasonable set of possible moves from the current state. There is no need to describe an idea end state, just a decent ongoing performance requirement.
Multi objective algorithms are fearsomely hard creatures to get right, but when working they can do great things. Use one to train a neural network with temporal properties (bases current decisions on past inputs at all positrons simultaneously), and you have a means to achieve a decent setup. It would take a long time to get right though.
Go is too complex for a total understanding, if ever there were an NP complete problem, this is it. thats why we have evolutionary algorithms. best solution? don't care about them, best possible in reasonable time? That'll do nicely.
We /know/ what an FPGA is, just because nobody knows what a 'mashup' is doesn't mean we're stupid.
Let's just take the final position of a game of Go. It takes a certain level of Go knowledge merely to determine which groups are alive, which are dead, which can be taken off the board, etc. in order to determine the final score. Beginning Go players will often not be able to determine this on their own and will have to "prove" to themselves that a group really is dead. And then there are the rare cases of dual life, which beginning Go players are frequently not warned about at all. Programming this stuff is HARD. There's a reason why the scoring portion of playing a Go game online is still done interactively (each player taking turns marking dead stones)... it's because there are no algorithms as of yet that can do it accurately enough. With this in mind, I have no idea why they would believe that searching huge numbers of positions would be helpful when computers are extremely hard pressed to come up with useful information about the score of the game at any given stage.
Wake me up when they come up with a computer program that can beat all human Go players without an exhaustive search...
It's a running joke that in artificial intelligence that to solve a problem you almost have to know the answer already. When you consider all the possible ways to be intelligent as a search space, the process of evolution has "narrowed down" what it is "almost" like to be a human and we as individuals fine-tune the rest of the answer starting from birth. The human mind is a remarkable pattern processing machine and the day a computer can play go against a human master and win is the day we truly understand how to replicate sentience in a machine.
Shh.
they can manage to convert the energy produced by Cory Doctorow's ego into raw processing power. Of course, this might just result in every Go board ending up with a depiction of Cory felating Walt Disney.
Carried to its logical extreme, the tree would grow until it exhausted every legal continuation, leaving the program nothing to do but examine the end positions to see which of them were wins--that is, checkmates--and which were draws, then work backward along the branching structure to choose the line that led to the best outcome, assuming that both sides play perfectly.
This is exactly the method that Spock would utilize while playing 3-D Chess, and he would always win. However, due to his reputation for winning by always going to this logical extreme, noone ever would want to play with him.
In the end, it was deemed a highly illogical method, since it killed his ability to play the game.
He who knows best knows how little he knows. - Thomas Jefferson
Yes FPGAs are easy to program, but there is a tradeoff: speed. And since this is a brute force application, you probably don't want to use FPGAs.
Let me know when they invent a computer that can play charades. Then I'll be impressed.
The fact that we're talking about trillion move/second machines rather than even attempting to do it the way humans do it ought to tell us what the current trend in artificial intelligence is.
Basically, the current trend is the same as it was 20/30/50 years ago. This IS NO science of artificial intelligence. We don't have a freaking clue how intelligence works. I think we will someday, but it's going to take a fundamental breakthrough in theory. A "Principia Intelligentsia" (I'm probably mutilating the Latin) by some genius that throws out all the fumbling and finally Explains It All.
Sometimes it's best to just let stupid people be stupid.
Since you can make the architecture of the logic in the FPGA highly specialized, you can run at a fraction of the clock rate of a general purpose processor and still have a wider lead in performance. I remember seeing a paper in a journal about a group doing an encryption benchmark between the fastest Pentium 4, two old yet powerful computers(I would assume probably old super computers) and a FPGA system, the two old computers had a lower clock rate than the 3GHz Pentium but had twice as much throughput, the FPGA had a clock rate of 50MHz and had a throughput about 10 times higher than the old computers.
So using a FPGA to do calculations for playing GO would be very fast at a low clock speed, but thats all it could do until it gets reprogrammed.
...theoretically has 10^60 potential endings. Is conquering the game via exhaustive search of all possibilities possible?No.
A typical star is made up of ~10^57 hyrdogen atoms. If you could store an all the information you needed about a single ending position in a single atom, you'd need storage that had the mass of thousands of stars.
I am curious anyone has ported gnugo (or whatever) to the nvidia cards using their CUDA C Compiler. The high end nvidia cards are something like 128 500 mhz processors. If a position was "at clock" you would only need 20 nvidia cards (and some coding to glue them together) to get 10^12 positions / sec. If it takes say 50 instructions to evaluate a position, that means 100 nvidia cards gets what you need or 20 boxes w/ 5 cards in each, it may not be "at home" affordable but its certainly on the low end w/ regards to cluster style computing. The coding would be a pain but I would guess that the tools are there (MPI wrapped cuda?)
Exactly my thought.
Plus, why is it so important to "crack" Go, anyway? These researchers have come up with a solution that is essentially a brute-force attack for each game position, requiring a supercomputer. We all know that supercomputers can do amazing things that require unfathomable amounts of calculations. It sounds like they know that this approach would work, too -- they just aren't sure that they can build a machine powerful enough to tackle the problem in a reasonable amount of time. So how does this advance computer science? How does it advance the understanding of human intelligence? What important problems in game theory does it help to solve? More importantly, how does this help me play a nice game of Go on my laptop while I'm waiting for my flight to land? As near as I can tell, it achieves none of the above.
Breakfast served all day!
This is one of the worst articles about computer-Go I've ever read. The author seems to completely overlook the recent advances in the field which made possible huge gains by replacing n-ply reading and evaluation by monte-carlo sampling of possible end positions. This is indeed some sort of brute-force but allows to avoid the proble of evaluating a partial position, which is very hard.
:)
Still far from the best human players, but at least improving
"IEEE Spectrum looks at current trends in artificial technology..."
Is that in contrast to natural technology?
I read an article to this effect in an AI class. Apparently the Latest Thing in solving things like Go is to take a good random sampling of just a few thousand (or tens of thousands of) possibilities in the future, and try to see what sort of move looks better, rather than trying to be exhaustive about the entire thing. I thought this was Quite Interesting. Meanwhile, the exhaustive search is really the least interesting way you could possibly do it, and won't likely provide you with much insight on Go, or related matters. *yawn*
The World Wide Web is dying. Soon, we shall have only the Internet.
I don't claim to be anything approaching good at go, but I've watched a lot of games on IGS PandaNet, and I really think the game of Go has far more in common with a Real Time Strategy game than something like chess or checkers, because of that sheer number of paths through the game (never mind the end states), and the possibility that the board can change so drastically during the game. You never really run out of stones in Go as long as you have places to put them on the board. In chess and checkers, you've got a hard limit on resources. RTS games let you churn out as many units as you're able to pay for in a simmilar way. As far as computer processing goes, that makes future state calculation far easier. When thinking about chess, you never have to consider the possibility that your opponent or you are going to recieve reinforcements. That queen you just captured is gone forever. In go, and RTS games, there are plenty more stones where the ones you just captured came from, and you've got to consider their possible impact on the future state of the game.
I'd try for something worth more, cause after you pass Go, you only get 200 dollars...
-
RIAA Involvement: Do not pass go, do not collect 200 dollars
It is, and never will be, a question of optimisation - no matter how stochastic, fuzzy, or hardware based. Chess was only "solved" in this way - it wasn't solved the way we actually play it.
Go... is all about pattern matching.
The tigers mouth, the ladder, the bamboo joint, the turn... that's how I play.
Just as the brain makes sense of our world. We make sense of go through the patterns we see.
And no - I don't mean just throw a ANN at it:-) And yet, something stirs in the heart of AI... Something within the new approaches to statistical pattern matching...
No, it ain't solved yet!
Seems like AI is still struggling to make itself useful (and to redefine itself) if this makes the news for IEEE. Yes, I know there are real world applications of things we might call AI, but as the years go on, the backlash against the naive optimism of the 70's and 80's seems more and more justified.
Maybe someday we'll get to the bottom of this syntax/semantics thing, but I wouldn't bet my (hypothetical) VC money on it.
The best fp devices top out under 10^15 operations / second. in a computer sized box.
Lets assume we can design a go-specialized device that can outperform that by another 10^20th power (ridiculous, but let's imagine).
We build 10^9th such devices (a billion!), and wire them all together to play go.
It will still take 10^16th seconds (317,097,919 years) to figure out go.
So no, it won't happen that way.
Worse, I don't think go is that simple:
http://en.wikipedia.org/wiki/Go_complexity
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
Checkers was just "cracked" recently. It took over 10 years I think. I would think only games similar in magnitude would be worth computing / possible to store.
You'd have to find a new universe to do something similar with Chess.
Just to physically store everything would be impossible. There are more possibilities in chess than there are atoms in the known universe.
And if GO has more possibilities than Chess, go find a another universe full of universes....and find a way to store things on a single atom.
A good interview with Will Wright that talks a little bit about Go.
Go, at it's heart, is a game of cellular automata. From the simple local rules incredible complexity emerges. To date there have been a few academic papers that deal with creating cellular automata rules for playing, but with little success. Very strong local play, but lousy global play.
I think the trick to a successful Go playing program is to harness the local cellular automata knowledge in a higher order algorithm. Perhaps to use the cellular automata to give likely next moves and then do a deep search on them.
Human Go players do this already -- reading, i.e. looking ahead involves players searching through likely play combinations to find the one with the most profit. They find the likely play combinations through a feel of shape or of other criteria, then narrow it down to see if their short list of play combinations works or does not work.
(I was only an egg, but then I cracked)
It's definitely an interesting problem. I spent years researching Chess engines eventually ditching it for Go. If you want to really be on the bleeding edge check out the computer-go mailing list. We're all there. http://computer-go.org/mailman/listinfo/computer-go
I'm wondering if for this one an evolving algorithm will end up getting it figured out and the original human programmers won't understand how the final product works. If the mechanics of play can be programmed and the mechanics of deciding who won can be programmed then let the algorithms mutate a hundred/thousand generations and see what progress has been made. Can the final product play better than the original, if so, keep going, if not, tweek the mutations and try again. Some of the creative ways the genetic algorithms end up making the decisions can be quite baffling when looking at the code, something as complex as playing GO may end up with code that is nearly undecipherable.
I say this like its an easy thing but it would be an interesting process I'd think.
There's probably a PHd. dissertation or three in there somewhere.
Shop smart, Shop S-Mart.
I'm a reasonably strong Go player myself (4. dan) and I've studied computational complexity - my gut feeling is that computers will not beat humans at Go in my lifetime even if Moore's law continues to apply. The only possibility is that someone comes up with a completely new approach, a bit like when alpha-beta search was invented for Chess. At the moment the most interesting approach is Monte Carlo methods applied to Go which has so far lead to a gain of at least two stones strength for the current programs. The strongest Monte Carlo based program is currently MoGo by Sylvain Gelly et al. which you can find more information about at http://www.lri.fr/~gelly/MoGo.htm.
The interactive way to Go -- http://www.playgo.to/iwtg/en/
troll? you've got to be kidding me. bad humor, maybe. offtopic, CERTAINLY! but troll? what exactly was I trolling for there?
Was this your first time with modpoints?
Now this post on the other hand... trollerific!
King Kong Died For Your Sins
For this type of thing, I'd probably at least look at using a software-configurable processor like Stretch's lineup. It's much, much easier to reconfigure than an FPGA (and obviously, a custom fab) would be. Once everything was locked in and if speed proved to be an issue, then I'd start moving to firm/hardware.
There's not an infinite number of paths if you exclude those paths which contain cycles (which you really should do, since they're pointless). The board is finite, thus there are a finite number of possible configurations of the board. Therefore, you do not need to consider an infinite number of paths, only the best move in each of a finite number of states (which is still an incomprehensably large assload). Remember a few months ago when checkers was solved? Technically, there are an infinite number of paths in checkers, too, since you can just move your kings around in circles.
This is all analogous to a turing machine with a finite tape. If you wanted to, your turing machine could run for ever just rewriting a bunch of symbols in the tape, but the set of all configurations of the tape is, in this case, finite, making cycles detectable and the halting problem solvable. Very, very different from the halting problem with your typical infinite tape turing machine.
"Question with boldness even the existence of a god." - Thomas Jefferson
5 * 10^12 != 10^60
SirWired
Methinks, all the computing power they intent to sink cracking Go would be better used to produce an AI capable of playing the game at strong amateur level.
..."
There are lots of games around waiting to be analyzed, and if they are about to crunch gazillions of positions they'd better to extract something more juicy than "for that position the best move is
I have played a lot of go and am a programmer. This will not be solved anytime soon unless there is a very big breakthrough in AI.
Go is challenging to program for many reasons:
1) There is a ridiculous number of moves. As mentioned in the article.. there are 361 factorial moves as the game progresses. Many of these would never be done (a player would not move on the outer most edge of the board in the early stages). Some extra moves can happen as you kill groups and move new pieces into their positions. And of course.. both players pass well before the game is over.. so the board will never be filled up. So there are some limits on this huge number.. but whatever it turns out to be... it is crazy bigger than chess's possible moves.
2) The rule set is much less restricted. In chess... you are very restricted.. each of the 6 types of pieces have very specific rules. All except the knight is blocked by other pieces. In go.. you can move almost anywhere you want (it may not be the best idea but there are no rules about not moving to an empty spot). I say almost because you cannot actually kill you piece by placing it into a spot that would immediately kill it. These spots however are small in number to the number of spots you can move.
3) It is extremely difficult to decide the current state of the game with regards to one position being better than another. In the article he mentioned being able to shorten the move search tree by neglecting paths that led to worse positions. The earlier parts of the game are extremely difficult to decide. In fact.. there is probably no correct answer. This is probably one of this biggest issues with getting a computer to play effectively. There are probably spots that the computer with proper algorithms could deem as not so good.. but what about the 500,000 other positions that may turn out good.. may turn out bad. I think it would have a difficult choice when it has so many positions that it cannot grade as good or bad.
4) The delicate balance between whole board and small area (strategy vs. tactics). He mentions in the article that the computer could focus on a small subsection of the board at a time. This is fine and dandy when the computer can magically know which of the small subsections is vital. As a 19x19 game progresses (especially earlier in the game) there are for example 20 zones of the board that could become hot very fast. If one player takes initiative in a section.. they may only play 3-8 moves there and then jump to a completely different section of the board. These to positions (potentially) will collide.. and the way that the player built these two sections and the way they collide is very important.. this will greatly hinder the computer simply focusing on a subset on the board... that would be to focus on tactics.. and strategy and tactics are constantly balancing back and forth in the human players mind.
5) The human player makes new algorithms as they learn more about the game. One of the trickiest things about go is that there are no sets of rules that define a good move. There are "proverbs" which sometimes are philosophical about the game. Sometimes these are even contradictory. I doubt very much that people will find the golden set of algorithms that describe good play.. at least in a way that a modern computer interprets language.
In the end... I think one day we will have a computer that will be better than people at go. The only thing is.. I am very sure that it will be a very long time from now.. or after a breakthrough happens in AI. Anyone who has played the game for at least 20 games on a 19x19 will see the amazing explosion of possible moves. They will feel how sometimes there are 10 hotspots that you just wish you could move, but you only have one. They have felt what it feels like to be focused on an area of the board and suddenly, due to their opponents craftiness, jump to a whole different area of the board and suddenly.. that area becomes vital. A single move can make a relatively safe area dreadfully
The sad irony is that as software improves, compiler errors are easier and easier to guess. Now computers a few decades ago... they really knew how to play charades.
-1 not first post
...play Go without a computer.
That's exactly it. This is brute force, not AI at all.
My website
The way humans deal with data is just different from how computers do. Tasks we find trivial they find hard and vice versa. For example if you show a human pictures of cats and dogs and ask them to classify them according to which animal they are, that's easy for us. For a computer, it's a very hard task. However a computer has no problems dealing with an analyzing a 50,000 item long table of numbers, whereas a human needs them converted to another form to make sense of them.
Well, when it comes to solving games, it's a similar deal. Computers aren't good in the way humans are. They are good by mapping out possibilities, tons of them, and then figuring out based on that. That's how good chess programs work. At their core it is more or less plotting all the possible endpoints several levels deep from a given move. They then calculate the most favourable set and that's how they choose their move. A little more complex than that, of course, but at its core it is simply mapping out billions of board positions and using those to decide moves.
Thus a similar thing probably would work well for Go, especially if you can do an exhaustive search and go to literally ALL endpoints for every move. It also has unique strengths. Many good human players work off of psychological aspects of the game. Kasparov, for example, was known for "throwing lightning bolts" at the game board, doing things other people couldn't cope with. That doesn't work for a system that just analyzes the current position and where it can go from here. There's no way to confuse something like that, no way to play to a mental state. It simply weighs what you've done, and what you could do from here.
I wrote Honinbo Warrior in UCSD Pascal and sold it for the Apple II. Sadly, I don't have the code anymore except for a printed listing. Anyway, it played a poor game, slowly.
:-)
I wrote a white paper a few years ago on how I would do 'real AI' and Go (PDF file: http://www.markwatson.com/opencontent/AI_Go_Consciousness.pdf). Really not much content, rather, I was just laying how I would go about it if someone funded me to work on AI Go for the rest of my life
The game is flawed!
In that context, I don't wonder that it's hard for computers to handle Go. The game has facets that are hard to quantify. It's hard for intelligent humans, too. Much like life.
Sort of makes you wonder; if a computer can figure out Go, how far from that point is real AI? Or does that question even mean anything?
What is is all that is. Isn't that obvious?
Of course pure number of game states does not equal it.
But after you know how to play both games, you can also see the richness of experience for yourself.
I can say that Go can be even more addictive than WoW, if you get really into it.
We are Turing O-Machines. The Oracle is out there.
On complexity: perhaps the best definition (for matching our intuitive feeling for how complex a game is) I've come across for game complexity is this: Imagine a novice player who avoids glaringly wrong moves (e.g. sacrificing a queen for no benefit in chess) but otherwise randomly choses from the legal moves available to them. Call this a 'level 0' player. Now a player who is smart enough to beat the level zero player 2/3 of the time is a level 1 player, someone who beats a level 1 player 2/3 of the time is level 2 etc. Then the game's complexity is the level of the best human player. If I recall correctly, this gives naughts-and-crosses/tic-tac-toe a complexity of 1, chess was about 20 and go was about 40. Unfortunately, this is all from memory, I haven't found the right magic words to feed Google to get more information.)
So yes, the game-state complexity can be a very poor measure of actual complexity, but go still has a very strong claim to being the most complex common human game. (An extreme example of high game-state complexity but trivial actual complexity would be a large game of "Brussel Sprouts".
On the Diplomacy/Axis and Allies comparison. The three games being compared are very different in nature (although they are all zero-sum.)
Go is two player, complete information, deterministic (as are chess, checkers, hex, naughts-and-crosses/tic-tac-toe) Such a game can, in theory, be completely analysed.
Diplomacy is multi-player, deterministic, incomplete information because moves are simultaneous. I'm not sure if or how this could be analysed.
Axis and Allies is (effectively) two player, probabilistic. It could (theoretically) be completely analysed as a very large dynamic programming problem. From a game-theoretical point of view, it resembles Yahtzee.
Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
I would have hoped they'd be well hosted. Instead, "Please pardon our appearance"
"The IEEE Spectrum Online website is temporarily unavailable while we work to upgrade our features. We apologize for any inconvenience this may cause you. Please check back with us in a day or two to see the new and improved Spectrum Online website. Thank you."
is IEEE-ese for 'Please someone resurrect our melted processors'
Sort of makes you wonder; if a computer can figure out Go, how far from that point is real AI? There was a line in Shibumi- something to the effect that Go isn't a metaphor for life, life is a metaphor for Go.
Sig cannot be found.
That's why they have cheap drinks, cheap food and babes with big bewbs at casinos.
I like that.
Sometimes I imagine Go as the essence of life, distilled into a binary adversarial form. Of course, I snap out of it when my neighbours explain I can't just take their cars because "they had no liberties" when I double-park.
What is is all that is. Isn't that obvious?
You feed in the starting position of the board, it instantaneously computes all the possible moves and then tells what the most likely outcome is. This is generally the computer winning.
I have excellent Karma and I am not afraid to Troll it.
This idea is original (I haven't copied it from anywhere) but it has probably been independently thought of before.
A natural thing to ask about a 2D game such as go, chess, naughts-and-crosses/tic-tac-toe is how can it be extended to three dimensions?
For go, the immediate thought is to play on a 3D grid of cubes. However, I believe (I haven't actually tried) that this will work very poorly. The number of neighbours that each point has will have a huge effect on play. With two many neighbours (6 in the case of a cubic grid) it will be impossible to defend territory, or to capture stones until nearly the entire board fills up. The game would be boring.
To capture the essence of go in 3D, we need each point to have four neighbours. This can be achieved with maximal symmetry by using either truncated octahedra or rhombic dodecahedra as the board's cells.
UPDATE: After writing the above, I did a quick search and discovered diamond go which has clearly used the same basic idea. I haven't figured out yet whether it is equivalent to one of my two options.
Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
After having RTFA, I'd say that the author knows what he talks about. And with techniques he described, the may have a chance to achieve an unprecedented level of computer GO.
Yet, this unprecedented level would steel be far behind real good players because while techniques described in the article can give the program overwhelming tactical advantage(and even tactics are hard to program in GO), it would steel lack deep strategy skills.
For example, the article talks about how vital is to be able to solve tsumego(live and depth) problems. Sure, in a top level game, loosing a group in a tactical battle without compensation usually costs the game, but when you play against some one way stronger than you on when it comes to global strategy, you still have to be able to take advantage of your tactical dominance and this is the very thing the program will lack no mater how strong and fast.
The fact is that in chess, because of smaller board and shorter games. tactics and strategy are more related each to other and in go. This gap is *the* difficulty of go, for programs and humans alike.
Below is a link to an article that may be of interest in this context: how far are top professional Go players from perfect play. http://bax-myx.livejournal.com/1212.html Disclaimer: I found this text file on IGS years ago but could not find it online anymore, that's why I've put in on livejournal.
Star Bridge Systems specializes in FPGA computers and tools to program them. It's been a while since I've checked up on them, but I'm pretty sure the NSA was/is one of their customers. http://www.starbridgesystems.com/
You should make a CAPTCHA thing where you have to play Go in order to post a comment or whatever. Now that all the distorted text things have gotten to the point that humans can't solve them anymore.
Unlike checkers or chess, Go end positions get MORE complex, not LESS complex, in terms of sheer brute force. Of course, many advanced amateur and pro games get resolved quite early -- leaving what appears to be an "unfinished" game on the board. The problem is that human players tell themselves quite interesting stories about the meanings of these boards, while a computer, presumably lacking a sense of spatial narrative, is clueless. One of the best examples of these outcomes occurs early in the Hikaru no Go manga series; the position left on the board is a famous 19th century board by Shusaku Honinbo, and the defeated thug's demeanor (he looks like he's seen a ghost) is apposite and appropriate. The number of possible Go positions is 3**(19*19) - 1, by the way.
``Tension, apprehension & dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_
For those of you who have access to ieee online journal, it is still available through http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6
Just FYI. The author: Feng-hsiung Hsu was the architect and the principal designer of the IBM Deep Blue chess machine. http://en.wikipedia.org/wiki/Feng-hsiung_Hsu
For my research, I've developed a board with multiple FPGAs to solve another similar NP optimization problem. I'm using Actel Igloo FPGAs.
They're decent performance, medium-sized FPGAs with a very clear advantage over all competitors in terms of their power consumption. Power & heat are major issues for my board, and I found that the Igloo parts were perfect. (The fact that they're flash-based also cuts out on the superfluous EEPROMs required to program the older SRAM-based FPGAs.)
Nevertheless, the take home point is that subtle threats and counter-threats are useless unless you are prepared to actually carry them out in tedious detail.
For a work of literature involving the game, I recommend The Master of Go by Kawabata Yasunari. The story of a match that lasted almost six months between the master and his challenger.
GP didn't even mention number of states. The only word he used that comes close is "complexity", but that is far from unambiguous.
Medium cat is MEDIUM.
I remember when Warcraft 3 came out the computer was pretty good. But as soon as balance patches were released and the AI wasn't improved, the AI effectively got a lot dumber. Just change the rules slightly and you'll need to rewrite the whole program. Change the rules of Go once in a while, and humans will stay ahead.
While cracking, exhaustively, the game of GO they will be creating some kind of data structure, some kind of decision tree, and then ever computer in the world will be able to use the stored file and make the best possible move every time.
You have to realize that out of those 10^60 possible moves many are redundant, like moving the same piece back and forth that does not change the outcome the game except for extending its duration. It's just a guess but I would not be surprised if the data structure to hold a perfect game of GO would easily fit on a DVD or CDROM. There are huge portions of the total possible moves that get deleted from the finished decision tree because they lead to defeat and can be avoided or are just silly and do not impact the outcome of the game. Any solution that doesn't end in victory or in worst case stalemate and is avoidable, will be deleted. It is possible that their might be solutions that lead to defeat that cannot be avoided but as soon as the computer realized it was in that scenario it would forfeit making the tree even smaller because the computer wouldn't need to know the moves once it reached that portion of the tree that it cannot win or stalemate. I doubt any human could beat any computer playing with such a tree, unless the human had memorized one of the scenarios, if any exist, from the tree that leads to human victory of which the computer could not avoid.
It would be like playing tic-tac-toe with a third grader. They think it is possible to win but even young players know that you can always force a stale mate and you can only win if someone does something stupid.
I have had talks with many people more intelligent than myself about doing this for the game of chess. They all believe that it is not possible to do with todays computing power. Chess is estimated to have around 10^153 possible moves. Though they all agreed with me that many of those moves could be removed from a final game play tree and that after creating and pruning the tree it is likely that any personal computer would be able to use it to play a perfect game. There would be very little processing to do in making any move. This is because the chess application would not need all 43, the average possible number of moves in a single turn, it would only need the one that is ranked the highest. This also shows another way the final tree for the game of chess would be reduce in size. Until a complete tree for all the possible moves, for the game of chess or GO (or any game), had been computed and stored nobody will know how long the final tree might be. Who knows by then you may be able to have play a perfect game of chess against on your cell phone or it may be too large to be practical.
I have created a decision tree for the game of tic-tac-toe, from my head (not computed), but I think everyone knows that one (lol).
It would be interesting to see if these kinds of problems could be solved using distributed computing over the Internet, like SETI does.
Nick Powers
Encryption: I may not agree with what you say, but I will defend your right to encrypt it...
The article says *chess* has about 10^60 positions. Go actually has 10^170. Now all the people that have made silly arguments about how 10^60 means the game is untreatable should apologize, I suppose. Oh, and go will fall too. My bet is 20 years before a computer beats the best human players. We know more about how to write a go program than most people think.
Speaking of how hard it is to even decide if a board position is good or bad, there are three more things I can add:
1. One of the key concepts of Go is "influence". Stones literally radiate influence. Different groupings of stones, in different regions of the board, and in opposition to other groupings, radiate differing amounts of influence. And in a Heisenberg-ish kind of way (at least during the early stages of a game) pushing too strongly for influence will create less space and pushing too strongly for space will lead to less influence. The master strives for just enough more influence or space to win.
For example, fencing in areas near the edge of the board early on. You may be solidifying space -- though no guarantees if you are not very certain of what you are doing -- but you are giving your opponent great influence -- if they play well, no guarantees.
No doubt chess has a similar concept (pieces, control, development potential), but it just feels different... Not as fluid or symmetrical in so many ways.
In some sense, you are creating your pieces by placing atoms on the board. No doubt chess has a similar concept, say having a bishop and a knight work together, or two rooks, etc, but the small size of the board and the severe movement restrictions and clutter makes these chess meta-pieces much more awkward than Go.
2. Sente (initiative) is a very important part of the game. You may jump around the board making five or six moves in sente, then finally go back to patch up a weakness in gote (yielding sente). One of the difficulties of the game is deciding how urgent moves are, and thus when you should yield sente in order to address them. (Of course, the perfect solution is to figure a way to make the urgent moves in sente, but...)
Of course, in Go it is always advantageous to move if you can -- as opposed to, say, chess -- and the Go board is large-enough scale that it's easily possible to have a dozen places you'd LIKE to move but you have to rank them and decide how long you can postpone most of those moves so you retain sente. I just don't see this in chess -- though perhaps I don't know it well enough.
3. Go has an aesthetic sense. You might say that it's simply a different word for intuition and chess is no different. But I don't think so, because chess does not allow you to move pieces arbitrarily to fulfill "balance" or other aesthetic concepts. I am only an intermediate Go player, but I have been amazed at the number of high-level games I've viewed over the years and I've been able to see where a move must go, based almost entirely on an aesthetic sense that the move somehow balances or fills in something.
(The problem of course is sente -- WHEN should that move be made -- as well as playing the entire rest of the game at that same level of insight, stringing together move after move. Perhaps that's one way that Go is like golf. One of the reasons that golf is so addictive, IMO, is that any good player occasionally hits a shot that's as good as Tiger Woods. The rest of the game does not go that well, but they get a tantalizing taste of greatness for an instant and that's very addictive.)
One of my favorite times in pittsburgh. Went to fix his PM6500 (replacing his dear old Mac II that lasted him for over a decade) and ended up playing a duet on his living room baby grand. :) 2 years before his unfortunate demise... loved that guy.
We are probably never going to have an (earth based) computer that is able to compute 10^60 diffierent possibilities, given that the earth has less atoms and electrons than that (http://pages.prodigy.net/jhonig/bignum/qaearth.html). Assuming that each of the computed possibilities is expressed(stored/presisted) by at least 1 electron. Its probably at least a few orders of magnitude more now..
Perhaps quantum computing may change that?
The RAMP project's hardware would be a good place to start. They have 105 FPGAs per rack. There's enough FPGA-space in each rack to simulate 1008 general purpose CPUs.
Suppose it happened, but after pissing many player off, they decided to increase the board to 20x20 (by a single line)...how much harder would it takes for the computer?? The number of possible board position scales exponentially.
The only possible interpretation of any research whatever in the 'social sciences' is: some do, some don't
If you read the article carefully, you will see that the 10^60 number refers to chess, not go. In go there are 10^170 legal positions. Building a complete game tree would take at least 361! (10^768) nodes, but considering captures, this number grows to a stunning maximum of 10^(10^48) nodes. Good luck with the brute force ;-)
I am a reasonably strong amateur player (currently 3 dan), and I'm willing to bet that no computer will beat me at go in the next 50 years (Assuming I don't get a brain tumor/dementia/etc).
This article has been thoroughly discussed on the computer-go mailing list. There are a pair of threads at:
http://computer-go.org/pipermail/computer-go/2007-October/thread.html
As a long-time subscriber and poster to the list, I think the best thing about the article is the increased visibility it gives to the problem of computer-go.
cheers
see http://en.wikipedia.org/wiki/Go_complexity
unless i am missing something, the game is *much* more complex than stated.
^..^
There was an interesting quote in this article about the number of possible chess positions, "tree containing about 10^60 positions. That's about a thousand times the number of hydrogen atoms in the sun."
It is often misquoted that the number of possible chess positions is greater than the total number of atoms in the universe, however this is saying that it is less than the number of atoms in a single galaxy.
I wonder if anyone has tried to reduce the size of the board and solve that with brute force. Then increase the size of the board by 1x1 and solve that. Repeat this process a couple of times and maybe one can find a recursive relationship that will make it easier to solve the game.
Just a question. I'd consider it somewhat wasteful to let a computational sucker like described in the article play "Go", but I can imagine that 1) the methodologies of attacking problems is valid so it can be applied to other problem domains, but 2) I can also imagine that strategic and planning problems could be formalized as "Go" problem fragments, or even "Chess" problems. Has anyone done any work on that?
With great power comes great electricity bills.
From TFA: ...
...
FENG-HSIUNG HSU earned a Ph.D. in computer science at Carnegie Mellon University,
Hsu now manages the platforms and devices center of Microsoft Research Asia, in Beijing.
To experiment with a Go program, readers can download GNU Go at http://www.gnu.org/software/gnugo. Offered by the Free Software Foundation, in Boston, this free program has performed well in recent computer Go events.
This is getting old, but...
The number 10^60 in the article was referring to the number of end positions in chess, which is much easier to 'solve' than Go. The real number for Go is over a googol times that. Thats 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 times the number you gave, assuming I counted correctly. Though of course these "brute force" algorithms are not solving each of those any more than Deep Blue solved each of the 10^60 chess end games. They are merely searching down a dozen or so plays into the game.
And you are also incorrect in disputing the gp's assertion that the game is subtle. Unlike chess, where there is an easily defined end of game, Go has no such concept. The game is over when both players say it is over. The article also covers how facts like those make Go AIs even more difficult to program.
Mathematics is made of 50 percent formulas, 50 percent proofs, and 50 percent imagination.
Have you ever actually played go? Or even know the rules?
Based on what you've written about both players passing, this tells me that Go is more like Chicken than it is like Checkers or Chess. Basically the only way to "solve" Go is to solve the human psyche of your opponent!
Imagine the scene in Footloose where Kevin Bacon has his shoelace stuck in the tractor. You're losing, but some random move might turn the number of stones in your favor and cause your opponent to pass. If so, you could still win.
Btw, who would pass when they're in a losing position? Someone who just wants the game to be over?
I thought the subject of 1999's Go was Ecstacy, not Crack, and none of the 10^60 outcomes had Katie Holmes doing full frontal, so why is this occupying the time of so many bright people?
There are no karma whores, only moderation johns
At the very end of the article Hsu says: "At Microsoft Research Asia we are seeding university efforts in China with the goal of solving some of the basic problems." What sort of grad student would make the best project manager? Would it matter if he were a rather weak player, as Hsu was in chess, back in his own grad-student days at Carnegie Mellon? Or should he be someone like Vasik Rajlich, author of the chess program Rybka, who is an International Master at chess? (Rajlich has said that he decided on that project becaues "I figured there were about 2000 people in the world stronger than me in chess but not one chess player that was stronger than me in programming.")
This artificial technology sounds pretty impressive. My oh my, a trillion per second....
But if you want to handle 10^60, you need real technology, which nips through a septillion positions in each yoctosecond until the job is done.
So a common game of modest construction accessible to people worldwide would be solved, and the joy reduced to a lookup table. The poor will have to construct even more complex amusements. Can't say it's nice to be poor.
Know your pads. One time pad: good for cryptography. Two timing pad: where to take your mistress.
Elwyn Berlekamp [Berkeley math prof] and David Wolfe wrote a book, "Mathematical Go: Chilling Gets the Last Point," in which they analyzed some "end game" problems for Go. They found situations in which moves could be compared, but the "number" system involved many levels of infinitesimals, reflecting the subtlety of the game.
Methinks a better approach to the problem would be some sort of evolved neural network, like the Blondie24/Anaconda program for playing checkers. It's not the best program ever made, but it was very, very good, and its skill would have scaled if it was given more computing resources. The same program, with minor modifications, could have played Go.
I never played or tried GO, but if Go has such a high level of possibilities, then it has to be possible to build various structures in it's space.
This means that in fact the game must be based NOT on evaluating all the move possibilities, but rather freely "moving" in the space, building and preventing the other player to build certain it's OBJECTS, and groups of objects.
Find out from the professional players about what type of objects they try to create and arrange, when playing a game.
A. Think of algorythms for creating these kind of objects effectively.
B. Think of methods to obstruct the creation of such kind of objects effectively.
Balance the A and B actions depending of the value of the identified objects in question.
http://id3as.livejournal.com/
I bet that ALive is a nice example of what can happen if the rules of Go are a little bit broadened. Solving ALive is whatone whould possibly call "game theory", so it would be interesting if both approaches would converge.
Just thinking..
With great power comes great electricity bills.
Less one, of course, because the empty Go board is not a member of the set of Go positions -- no stone has been placed, no contest has begun. Board plus stones, minimum one stone, and that black, defines a Go position. The notion of null set is not applicable to the spirit of the game.
``Tension, apprehension & dissension have begun!'' - Duffy Wyg&, in Alfred Bester's _The Demolished Man_
The empty board is the start state, and certainly a member of the set of Go positions, I suspect most Go players would say. Would you say that the start state of a Chess game is not a member of the set of Chess positions?