|
mingwu wrote: This is highly dependent on the program. You can evaluate fast if you don't care about the quality of the evaluation and don't mind having a crummy program. There is a general feeling that GO requires much smarter evaluation than what we have now and many are working on improving that. Of course this implies that current evaluation is much slower than it should be because strength and speed are highly correlated.Hi, I read on the web, and some other places that most Go programs can only evaluate "a dozen" of moves per second. Is this still true today on a typical machine, say, single 2GHz CPU, 2GB memory? I don't really understand what a dozen evaluations per second really means. I think MFGO does a shallow global search but at end nodes calls a special evaluation function that is relatively slow. However, this evaluation function has a search component inside of it - routines that check for life and death by doing ladder searches and such. All programs do a global search with some kind of static evaluation at end nodes. It is customary in computer go not to call it "global search" if the program just does a fixed 1 ply search. Perhaps the feeling is that if you don't actually call the evaluation function recursively it's not a search, but whatever the case it is just semantics. There are many who believe a 1 ply fixed depth search is the only number that works (which is nonsense.) Nevertheless, even the older classic programs do at least a 1 ply search. They call the search "selective" if you only consider a subset of the moves. However, even the subset not "considered" is evaluated in some sense to determine that it should not be considered! It is just evaluated less thoroughly, perhaps being quickly rejected by a simple pattern lookup or some other system. There is such a think called a "static evaluation function", which is a non-recursive version of an evaluation function. Most programs give their evaluation function a name like "search()" or evaluate() or something similar. A recursive evaluation function tries to evaluate positions by moving pieces around on the board to see what happens - more like what humans do.And if this is still true, how can we make it faster? Since recursive functions must have a termination condition, at some point you must stop and the general method is via a "static evaluation function", a routine that evaluates the position without moving pieces around. Having said that, it's true that many programs still move pieces around by further calling goal specific routines designed to discover something about the position via a goal specific search, such as determining if a specific group will live or die. To answer your question about how to make it faster, I think the answer is to find ways to replace the recursive components with static components. This falls into many categories:
At some point we all have to stop thinking of evaluation and search as two different things. This in my opinion is the biggest stumbling block in our way. You can find heated arguments going back 30 years or more on the subject of search vs evaluation showing how most people have partitioned these two things into separate unrelated concepts. In some ways, computer go is ahead of chess in this regard. Chess programmers think the two things are different but many good go programs use local searches to discover things about the position - nicely and properly blurring the distinction between the two. You can look at ANY good game playing program and easily see that it's all about doing as much useful work as you can, in as little time as possible. Probably the biggest source of misconceptions are articles you can find on the web that claim search is out of the question for computer go. These well-meaning articles are misleading and imply that searching 1 ply with an incredible static evaluation function is the "one true way." They generally make the all or nothing assumption that you either don't use search at all, or you must design a program with a brain-dead but super-fast static evaluation function and then try to search 100 full-width ply deep to make up for this. So these articles have kept computer go in the dark ages longer than necessary and are written in an incredibly naive style showing a lack of understanding of the general principles of how to evaluate a position. Of course you can now see strong programs based on using the search component much more heavily in the evaluation process. Aya is one example for instance, which is based on alpha/beta searching (they now have a monte carlo version) but other examples are based on best first searching, such as CrazyStone and Mogo and many others. I think I am going to write a nice blog about this somewhere (other than just here :-), to try to counteract all the well meaning but naive and misleading literature and web site postings on the subject. - Don To make the question more precise, I define a board updates as: suppose the program places a new move on an existing board, and then update all the blocks, dragons, eyes, connections, territory ... info, and output the evaluation as a score (e.g. B leads by 15.5 points). I also read that UTC programs choose a move by running lots of simulations, are their update speed any faster? Or they evaluation lots of boards, but for each move they only calculate some very simple information (to me, it will still be a surprise, because to evaluate a Go board, one at least have to know the life/death of each dragon, that would require lots of computation, which I think is the primary reason that why Go programs is slow compared to Chess programs that can evaluate thousands or even millions of boards per second). I'm just curious, any info / thoughts / comments is appreciated. |
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
