Computer GO - Problems and Solutions

Quote:

Original post by laurimann There have been studies on minimax, monte carlo and neural networks i.e. machine learning, but so far none of the methods has been successful beyond surface.

A lot of progress has been made. Computer go is in a similar situation as computer chess was in the eighties. I expect many small improvements will get us to strong go programs in maybe around 10 years.

Quote:

I think that expert systems are not the solution. I have thought about some kind of learning associative system that would associate board situations with made moves and game end result and with that data learn the significance of the moves and expected end result of move M in board B.

That sounds a little too vague for my taste. But if you put the work to implement it and show it to work well, I'll be happy to learn something.

Quote:

But i want to discuss about this: Does anyone have any ideas why GO still remains unsolved, what is GO all about and what could be tried to solve the strong master level GO problem? :)

The problem is that there is no money involved in creating a strong go program. I think it was Chrilly Donninger who said that this is like a bunch of amateur pilots and engineers on their spare time trying to get to the moon. It's not like it cannot be done; it just would take more resources than anyone is willing to spend on this.

Secondary problems are the large branching factor and, more importantly, the fact that there is no obvious basic evaluation function that can play the role that material count played in computer chess.

It was really depressing to read an opinion stating that amateurs can't get anywhere, or atleast not to the moon! I hope they can and that's why i'm still excited. :)

And alvaro that's exactly the problem with GO programs so far: No obvious basic evaluation function! That could maybe be solved with ANNs or something; as far as i see GO programs today can make master level moves without even realizing what they're doing. Therefore chess programs understand what they're doing? Well, in the context yes.

So any ideas or discussion about amateur successes and evaluation functions for GO? :) I don't have none yet, except that i think the program needs to learn also strategies, plans, styles of playing and maybe certain set of moves reminds the network of some stradegy it has noticed before and knows where it leads and therefore adjusts it's gaming according to that...

Quote:

Original post by laurimann And alvaro that's exactly the problem with GO programs so far: No obvious basic evaluation function! That could maybe be solved with ANNs or something;

I know that's a tempting thing to think, but just throwing an ANN at a problem rarely solves it. You need to carefully know what inputs you will use, how to measure the quality of the output... and then you'll probably find a better method to do it than ANNs.

Quote:

So any ideas or discussion about amateur successes and evaluation functions for GO? :) I don't have none yet, except that i think the program needs to learn also strategies, plans, styles of playing and maybe certain set of moves reminds the network of some stradegy it has noticed before and knows where it leads and therefore adjusts it's gaming according to that...

We heard that kind of claims about computer chess for a long time. Computers seemed reasonably good at tactics first, and then at positional play, but they didn't understand strategy, they didn't make plans. As far as I know, nobody has figured out how to make a computer come up with plans, and yet very strong chess programs have been written. Reasoning by similarity to previous experience is something humans are extremely good at, but I doubt the first strong go programs will have any of that. It's a little bit like the period in the late 19th century, when people were trying to figure out how to make machines that could fly. The only models we had in nature involved flapping wings. These days the most popular flying machines are planes and helicopters, which work in completely different ways. And as far as I know, nobody has managed to make a flying machine based on flapping wings. I predict something of this sort will happen with go; we will manage to make strong go programs without ever figuring out reasoning by similarity, or understanding of strategy.

Quote:

Original post by alvaro As far as I know, nobody has figured out how to make a computer come up with plans, and yet very strong chess programs have been written.

*cough* What about the whole field of AI planning? Chess algorithms can be described as planners, except that they typically re-compute the plan after each opponent's move.

Anyhow, what I understand from GO is that it involves a lot of intuition, which is hard to reproduce with computers... And then the fact that it scales so much. Parallel systems will help GO a lot, a modern quadcore desktop is as powerful as a supercomputer of some years ago. They said that computing would never catch up with Chess's scalability, and there you go...

Quote:

Original post by laurimann And alvaro that's exactly the problem with GO programs so far: No obvious basic evaluation function! That could maybe be solved with ANNs or something; as far as i see GO programs today can make master level moves without even realizing what they're doing. Therefore chess programs understand what they're doing? Well, in the context yes.

I think what alvaro meant by evaluation function was not the method used (ei. ANN's) but a way of assigning value to different moves. In chess there is a very well defined method called material cost:
Each piece is assigned a value. For instance, pawns = 1, rooks = 47, queen = 100 (can't remember the actual figures). Material is gained by removing the other players pieces, lost by loosing pieces. So two moves causing you to loose a rook, but take the opponents queen would net you 53 points.

Using these values the computer can compare all the possible moves at any given point in time, and any given number of moves resulting from those moves, and add up how much material was gained. Then it's just a matter of selecting the move that nets the most material gained (or least lost). It's of course more complex than that, but thats the general idea.

GO doesn't have an valuation like that. All pieces have the same value, so it's much harder for the computer to choose between decision branches. If you have 50 possible moves, and after 20 future moves (simulated by the computer) they all net almost the same material count, how can the computer know which is best?

Quote:

Original post by Steadtler Quote: Original post by alvaro As far as I know, nobody has figured out how to make a computer come up with plans, and yet very strong chess programs have been written. *cough* What about the whole field of AI planning? Chess algorithms can be described as planners, except that they typically re-compute the plan after each opponent's move.

I think the word "plan" means more than one thing. The way I was using it, it means whatever chess players think of when they talk about plans. These are usually vague ideas of what to do in the long run in the game, which no chess program uses.

See for instance this old paper: http://portal.acm.org/citation.cfm?id=809724&dl=ACM&coll=GUIDE&CFID=15151515&CFTOKEN=6184618

Quote:

From the abstract A serious deficiency in game-playing, tree-searching programs is their short-sightedness. Program strategy revolves around the maximization/minimization of what is attainable within the scope of the search tree with little consideration of what lies beyond. This paper describes Planner, a long-range chess strategist that assesses positions, determines a long-range strategy, and makes moves in the short-term (within the scope of the search tree) consistent with a long-term objective (beyond the depth of the search tree). In effect then, Planner allows the program to “see” beyond the limitations of the search tree.

My point is the very successful chess programs that we have these days do not incorporate any explicit plan making of this type.

What laurimann is saying about go programs needing to learn about strategies and plans reminds me of those thoughts people had in the 70s and 80s about computer chess. I think that when we see strong go programs they will not have any explicit knowledge of strategies or plans (again, in the sense chess players use the term).

The best computer Go program on the market, and has been for some time, is "The Many Faces of Go." (I think that's what its called) It uses a database of patterns, seen in most all go textbooks, handbooks, and guide, and their optimal resolution method to do a pattern search on the board. Once it narrows down to a pattern or a portion of the board, it then can either resolve the situation using the patterns stored or do a branching search for the possible outcomes (since by concentrating on a small portion of the board drastically reduces search space). It also uses other heuristics and known moves to help it make choices.

Since go has traditionally been known to be a hard problem even for human players, large volumns of text and data has been compiled over the centuries presenting "good" ways at opening up the game, which is when the branching factor is at its greatest. Then there are sets of commonly known good moves used to progress the game. The problem then comes down to how to use them.

From a search space point of view, go's branching factor is the opposite of chess. Where the branching factor starts small in chess and gradually expands, go's branching factor explodes at first then tightens somewhere near the middle of the game.

I've also pondered the problem of fitness assignment in go before and have concluded on a few things. Firstly, we must understand the winning condition in go. Unlike chess that requires capturing pieces, go involves capturing territory on the playing field. So, ideally, the fewer the moves required to end the game, the better, which implies fewer stones on the board and more open space. It's this abstract concept of territory that is hard to convey in a program, which good go players can easily tell in a glance. Secondly, there is the concept of connectivity between stones. It usually isn't until the middle of the game that stones really start connecting to complete the closing off of territory or killing opponent stones. So, then a program must be able to understand or perceive how connected its stones are and whether they effectively close off a territory or prevent opponent stones from surviving within its enclosed territory. This will probably fall back to pattern recognition again as some connections are riskier and more vulnerable than others. Finally, there's the problem of survival. For a set of connected stones to "survive" they must "effectively" enclose two separate spaces (eyes as they are known). I say effectively two separate spaces because it doesn't explicitly have to be two separate regions. It could be one large region that has the high potential of becoming multiple sub-regions when attacked and properly defended. These seem to be the most fundamental elements of the game. Based on these, we should be able to create a sort of abstract evaluation function as to how good a move is.

Ultimately, go is really just a game of securing territory, while resolving many local conflicts. It is really is alot like war. You have your local skirmishes, but you also have your overall war going on. Too much focus on the local scale loses the war, and too much focus on the grand scale will still lose you the war. And like most strategists will tell you, get your men (stones) safely to where your opponent wants to be before they do and you will have gained a great advantage.

Connecting the themes of the last few posts... the material value in GO is context dependent. In Chess we set a priori material values and maintain them throughout the game. In Go, the value of a piece depends on where on the board it is and its connectivity to other pieces, both friendly and enemy. That territory can apparently change hands back and forth also makes this material value and time/turn based function. In other words, using a material value for pieces is a really bad way to go (pun intended!) ;)

My personal feeling, having poked around this problem on and off over the past few years, is that we need better ways of evaluating the value of territory and the value of interdicting into that territory. Again though, these values will fluctuate wildly as we play, making it hard to produce long term plans. I believe pattern based AIs will reach consistent master level play eventually, again as our analysis and data access capabilities improve (as was the case with chess). I think getting there sooner will only be achieved by coming to a deeper understanding of the issues involved in relating strategic planning to tactical behaviour and how we can influence the behaviours of our opponents by affecting their perceptions of our intentions. Of course, now we're talking about a strange mix of psychology, politics and economics... and we'd probably get more benefit from applying our ideas to predicting the stock market than making a strong Go AI! ;)

Cheers,

Timkin

[Edited by - Timkin on August 15, 2007 1:57:20 AM]

The goal of GO is to own the most territory at the end of the game. The "material" in GO is, therefore, territory.

The problem is the horizon effect inherent in minimax algorithms that don't see the end of the game. Unlike in chess where once a piece is captured its gone for good, some territory in GO can change hands multiple times during the course of the game. This difference increases the horizon effect greatly.

Thus I would explore some some of certainty heuristics revolving around territory: How certain is it that this territory belongs to white? Use the sum of these certainties as the score for a minimax search of a given depth (note that at the end of the game, all territory should be certain)

Now, how you go about implimenting such a certainty heuristic .. well it sounds like pattern matching to me.

Quote:

Original post by Rockoon1 Thus I would explore some some of certainty heuristics revolving around territory: How certain is it that this territory belongs to white? Now, how you go about implimenting such a certainty heuristic .. well it sounds like pattern matching to me.

To mee too. Then again, i like to think that learning is about remembering what leads where and what's the goal, which is associations with goal. I think certainity system descriped above could be done with associating board positions, made moves and ens results together in a fine tuned way. How to fine tune such a linked system is another story that i have no clue about. :P