Playout Analysis
What is better for programming Go ?
- Minimax search or
-
Playout Analysis
A brief description of Playout Analysis:
Place the stone on the board you want to find the value for. This is now your beginning board position.
Play a series of random moves (presented from a move generator) from your beginning board position. Evaluate the board. Return to the beginning board postion and repeat the play of series a dozen times, summing the board evaluations.
Go back to the initial board, and place a new stone, then do the play a new series from that position, and again for the next stone, and again, and again....
Kjeld Petersen The opponents responce could also be weighted, so that the better responce would be more likely to choose in the random function. This could result in slowly building a tree for the best responces. The most likely moves.
Find the stone that had the best sum. Play this move.
JG There was some discussion on Playout Analysis in the computer go mailing list starting in August 2004. See the messages about SlugGo in
http://computer-go.org/mailman/listinfo/computer-go/
Bill: I would think that there need not be a requirement for random play. If you want no search at all, you could still use heuristics, which should produce a better result than random play.
Kjeld Petersen How about extending this algorithm. First place more than 1 stone on the board (say 20 stones, 10 black and 10 white). Then "shake" each stone at a time, to see if it makes the influence of all stones better. Repeat shaking for some while, then mark the postion of the stones, and start over.
After some run it should be clear that some postions are being marked more frequently, so somewhere around those positions must be good strategically.
That could make over playout analysis better.
Woody Folsom: This sounds like simulated annealing, which was used to determine the playout policy in Brügmann's 1993 paper "Monte Carlo Go".