Thanks for the clarification - I thought I had a bug in my scoring code, although I had successfully tested numerous scoring scenarios. Most likely, I simply forgot to set KGS to Chinese scoring when I ran some games against GnuGo then tricked myself into thinking that dead stones counted as points for the opponent!
On Fri, Feb 8, 2013 at 5:51 PM, Don Dailey <[email protected]> wrote: > > > On Fri, Feb 8, 2013 at 5:08 PM, Woody Folsom <[email protected]>wrote: > >> I wrote an AI agent which plays go using a pure Java implementation of >> UCT-RAVE for my MS project at Georgia Tech. With better data structure >> optimization I'm relatively sure 10,000s of roll-outs per second, per core, >> is not an unreasonable goal. >> >> Chinese scoring is easier than Japanese but I wouldn't go so far as to >> say trivial - my initial implementation erroneously counted surrounded dead >> groups as points! >> > > Chinese scoring is trivial if the game is fully played out. In Chinese > scoring there are no dead groups. If the group is on the board it is > counted as alive - that is the whole point of Chinese scoring. > > You are really doing playouts the hard way if you don't have the eye fill > rule. The way it works is like this: > > 1. Never fill a 1 point eye (a properly defined one.) > 2. Never allow a pass in the playouts unless there are no other moves > (subject to rule 1) > 3. Otherwise pass. > > The zobrist hash rule you use is a very good idea too. > > Note that at Chinese scoring time there will be NO dead groups on the > board to score incorrectly. There is nothing to get wrong at all, you > basically add up all the points on the board, white stones belong to > white, black stones belong to black and the single empty points belong to > whoever completely surrounds them. > > Here is probably the best definition of a single point eye: > > definition of eye: > > an empty point whose orthogonal neighbors are all of the > same color AND whose diagonal neighbors contain no more > than 1 stone of the opposite color unless it's a border > in which case no diagonal enemies are allowed. > > This is excellent to get started and your suggestion to start with uniform > random playouts is a good one. Later on he can explore some more > advanced issues such as dealing with seki and other things. > > > >> I used no heuristics whatsoever in the roll-out policy, and would >> recommend getting your MCTS algorithm working with purely random roll-outs >> first. I also did not explicitly code for avoiding filling the player's >> own eye, but used Zobrist hashing for super-ko detection and in practice >> never observed games run into hundreds of moves. >> >> I suspect that with Zobrist you avoid the most serious cases, but I'll > bet you are still going far more moves than necessary. The one point eye > rules is very powerful and is probably the most important piece of > knowledge you could add. It's almost always the worst move on the board > to fill a one point eye so this brings a great deal of sanity to the > playouts. > > Don > > >> I would recommend using a board state data structure which encodes groups >> (or strings) of stones. Counting liberties recursively consumed 40% of my >> first agent's total run-time, for negligible memory gains. I did not deal >> with culling the state tree at all. >> >> Finally, (3) above is quite difficult. I am currently attempting to >> train a neural network which usefully estimates this value by means of >> temporal difference learning. >> >> For more details, feel free to check out my project write-up at >> http://woodyfolsom.net/blog/?page_id=43. I did not manage much original >> research since the whole project was done start to finish in one semester, >> but it covers the basics of MCTS and computer go. >> >> >> On Fri, Feb 8, 2013 at 4:41 PM, Don Dailey <[email protected]> wrote: >> >>> Score a go board using Chinese rules - it is trivial. >>> >>> The basic concept is that you play random moves and (usually) allow no >>> passes until there is nothing else to be done. To prevent eye filling >>> there is a fairly simply but very effective rule that prohibits filling a >>> one point eye - otherwise the game can last for hundreds of moves. >>> >>> That is the "basic" concept. These "playouts" can be greatly improved >>> on with some simple rules and patterns. But there must sitll be some >>> element of randomness and getting this right is subject to a lot of >>> research and is considered a bit of a black art. >>> >>> Even a pretty trivial (uniformly random) playout strategy with the rule >>> not to fill properly constructed one point eyes can give a reasonable >>> evaluation, especially near the end of the game if you view it >>> statistically. For example if you play 1000 of these "random" playouts >>> and black wins 950 of them, black probably really does have a won game. >>> With a little bit of intelligence added to the playout strategy it can >>> become quite good. MCTS basically integrates a best first search with >>> this concept. >>> >>> Don >>> >>> >>> >>> >>> On Fri, Feb 8, 2013 at 4:33 PM, Rémi <[email protected]> wrote: >>> >>>> surely at any time during a game of go, three passes can be made and >>>> the game can be scored... >>>> >>>> On 8 February 2013 22:31, Rémi <[email protected]> wrote: >>>> >>>>> If there really is a difference between (1) and (2) then I have always >>>>> been completely oblivious to it. For your third (3) case I again see not >>>>> what the difference is. >>>>> >>>>> >>>>> On 8 February 2013 22:02, Nick Wedd <[email protected]> wrote: >>>>> >>>>>> On 08/02/2013 20:34, Rémi wrote: >>>>>> >>>>>>> Hy, >>>>>>> >>>>>>> There are a lot of interesting papers on UCT and selection strategies >>>>>>> ... But it's harder to find information about the more 'pragmatic' >>>>>>> side >>>>>>> of computer-go. >>>>>>> >>>>>>> How do you score a go board? >>>>>>> >>>>>> >>>>>> What do you mean by "score a go board"? I can think of three >>>>>> reasonable possibilities. >>>>>> >>>>>> (1.) Count the score in a game that is over. >>>>>> >>>>>> (2.) Count the score in a game that is not over, but both players >>>>>> have passed because they think it is. >>>>>> >>>>>> (3.) Count the score in a game that is still being played. >>>>>> >>>>>> (1) is difficult but practicable. (2) is similar to (1), so long as >>>>>> you are not bothered about the result being meaningful, but just want to >>>>>> calculate the score as a referee might if asked to score a game in which >>>>>> both players have passed prematurely. (3) is as difficult as playing Go >>>>>> perfectly. >>>>>> >>>>>> Nick >>>>>> >>>>>> >>>>>> What would be a faster algorithm to score a go-board? >>>>>>> Could you pre-calculate and accumulate some information early in the >>>>>>> game (on every move), knowing you're going to evaluate the board >>>>>>> many times? >>>>>>> When do you decide to finish/score the game? >>>>>>> >>>>>>> Also, what are some of the languages used besides C(++)? Does anyone >>>>>>> work in something like java or a functional language? >>>>>>> >>>>>>> Rémi de Zoeten. >>>>>>> >>>>>>> >>>>>>> ______________________________**_________________ >>>>>>> Computer-go mailing list >>>>>>> [email protected] >>>>>>> http://dvandva.org/cgi-bin/**mailman/listinfo/computer-go<http://dvandva.org/cgi-bin/mailman/listinfo/computer-go> >>>>>>> >>>>>>> >>>>>> >>>>>> -- >>>>>> Nick Wedd >>>>>> [email protected] >>>>>> ______________________________**_________________ >>>>>> Computer-go mailing list >>>>>> [email protected] >>>>>> http://dvandva.org/cgi-bin/**mailman/listinfo/computer-go<http://dvandva.org/cgi-bin/mailman/listinfo/computer-go> >>>>>> >>>>> >>>>> >>>> >>>> _______________________________________________ >>>> Computer-go mailing list >>>> [email protected] >>>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >>>> >>> >>> >>> _______________________________________________ >>> Computer-go mailing list >>> [email protected] >>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >>> >> >> >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >> > > > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
