Re: [computer-go] Go hardware?
interestingly, this is the premise upon which i wrote my genetic board evaluator. for what it's worth, writing good go programs using a specialized 'go instruction set' isn't any easier or more intuitive than using, say, 80386 instructions. it just makes certain operations take less 'instruction lines' of code to complete. that's all. not clock cycles. this will reduce the search space for a genetically-evolved system, which is nice, but (obviously) doesn't change the speed. now, when my board evaluator is good enough to actually do something meaningful, i'll be happy to have someone drop it into an ASIC to see how much differently it performs. :) if you don't have the board-evaluation function written in advance, having access to specialized hardware that performs go functions faster won't make your code any better. just maybe a little bit faster. s. Never miss an email again! Yahoo! Toolbar alerts you the instant new Mail arrives. http://tools.search.yahoo.com/toolbar/features/mail/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] March KGS bot tournament results
The problem in Computer Go is the search of the best move that can be found. First, Since a computer prgram, or a player cannot consider every possible moves, they usually has a move selecting function which select a sub set of the all possible moves. The moves for consideration selected by a computer program, by a player, or by a pro player may not contain the true best move. In general, the move selected is not the true best move even by a pro player. Thus, on average a move selected has a probability associated with it. This probability tells how good the move selection is. Let's call it the move merit probability. It's higher for pro players and lower for lower rank players. The population distribution of moves with different merit probability is not uniform. The lower is the merit probability, the larger is the number of moves. The move selecting function has its own merit probability. Let's call it the function merit probability. The second reason the elected move may not be the true best move is that the evaluation function used by a computer program, a player, or a pro player is not perfect. Otherwise, the Go game is solved. Here, again, the evaluation function has a merit probability, a third one. let's call it the evaluation merit probability. Thus, one starts with an imperfect subset of moves and an imperfect evaluation function and feed them to a search algorithm (alpha-beta, for example). In general, the higher are the merit probabilities, the more effective is the search. Here one faces a question. How much search should be performed? In general, more search means better probability of findng the best move available in this scope. The merit probability function of the selected move is just the move merit probability. Thus, the move merit probablility is a function of three variables: the function merit probability, the evaluation merit probability, and the serach scope (or search time). Postulation: For a given function merit probability and a given evaluation merit probability the move merit probability function approaches a constant value for large enough search scope. That is beyond certain value of the search scope, the move merit probabability function won't improve anymore. Above discussion should be able to be formulated in a complete mathematical form. The exact mathematical form of the move merit probability function can be derived. It's possible that the MC-UCT method is based on this statistical nature of Go game. It's success is due to its suitability for such a statistical process. This last sentence may be wrong. Daniel Liu AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] when to stop searching
If it's true, it's an indication of the properties of the game tree distrubution. If a first move is good, it leads to a favorable geometric position. Starting from a geometricaly favorable position more good random playing lines exist than bad random playing line(the number of the good random playing lines plus the number of the bad random playing lines equal to the total number of all possible playing lines). Actually the ladder may not be an exception. At each step of a ladder there are only two possible moves. One good and one may not be good. The chance is 50% or larger. Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Sun, 11 Mar 2007 2:03 PM Subject: [computer-go] when to stop searching On 3/11/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: But to pick the best move, it's only necessary to recognize the weaknesses in all the other moves. In many cases these weaknesses can be recognized using move sequences that are far less than perfect play. The tricky part seems to be sequences can only be evaluated with perfect play for many moves such as ladders. It's unclear how often such perfection is required to pick the best move. Thus, one starts with an imperfect subset of moves and an imperfect evaluation function and feed them to a search algorithm (alpha-beta, for example). In general, the higher are the merit probabilities, the more effective is the search. With UTC, if I understand correctly, it would eventually try every possible sequence, but of course not within the time limit, so it isn't clear that it starts with an imperfect subset of moves that is separate from the other factors. AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] when to stop searching
I would add 4. The program tries to identify good moves, and only tries moves that it thinks might be good. If it is goal-directed, the good moves are good for a reason, and if the reason is not satisfied, they are discarded. This is the way Many Faces works. It's very similar to 3, but it's a different way of thinking about the problem (adding good moves rather than deleting bad ones). You are correct that this approach is inadmissible, and is self limiting. I like it because when I add new knowledge I know I'm making the program stronger. I don't like tuning parameters or algorithms and then playing hundreds of games to get statistically significant data on the better value. I'm not saying my approach better, just that I prefer it :) David 3. selective in the true sense. Such a program tries to identify bad moves and prune them from the tree, but they are pruned permanently. NO matter how deep or long you search they will never be considered. I think true selective programs, unless the pruning criteria is fully admissible, is self limiting. You can probably build a strong program but you will be bound strictly to the quality of your selective algorithm. Such an algorithm would play imperfectly even on an infinte speed computer. UCT is admissible - it will ALWAYS find a winning move if you are in a winning position. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
