It would be interesting to see how many playout will give the right answer. No matter how many heuristics one use, there will always be situations not covered. But the probability will get smaller. The program will get stronger, but not perfect. -----Original Message----- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thu, 26 Apr 2007 7:25 PM Subject: [computer-go] The problem with random playouts
I've attached a 9x9 game; a complex game that ended in a 2.5pt win for white (at 5.5pt komi). When I run random playouts on the terminal position (at 6.5pt komi, so actually W+3.5) the results are surprising. With 20 playouts black wins 9. When I increase to 1000 playouts black wins 564. I assumed it was due to one side doing an atari and the other side not responding. So I modified the move selection to favour ataris and saving stones in atari some of the time. As I increased the probability it actually got worse (black wins 590/1000) then back to where it started (568/1000). It seems this is just a position that monte carlo will struggle with: black has explicit eyes, white does not, so random thrashing will favour black. I realize UCT (or whatever) search from here should play correctly. But what bothers me is that when the game is being decided at move 27, UCT will be going maybe 10 moves deep, yet even if it was 30 moves deep it would still be getting the wrong answer. My conclusion is that random playouts will never produce a very strong player (within realistic resource limits); I now see why heavy playouts performed so much better in Don's experiments. I also suspect the playout style may need to be modified for stage of the game. I'd be interested to hear other opinions. I'd also be very interested to hear what people think are the quickest (in CPU time) changes required to playouts in order to get random playouts to score this position correctly (e.g. less than 10% black wins). The above results were using libego "out of the box", so it is easy to prove your theory experimentally. Darren -- Darren Cook http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary) http://dcook.org/work/ (About me and my work) http://dcook.org/work/charts/ (My flash charting demos) _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ________________________________________________________________________ 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/