Here is what I do, don't know if it's best .... Basically you want a list of empty points, since most of them are legal. When I apply a move to the board I then do any needed legality testing.
At the beginning I start with a list of ALL points on the board. When a non-empty point is encountered I "put it away", placing it behind a point in the list that represents all the occupied points. To find a random move I choose an index at random among the set of untested points. If that point is occupied, it gets put away, if it's not it's the next move (and it still get's put away since it will not be occupied.) If the point is not occupied but illegal, it gets "set aside" until a legal move is found - then it is good again. When a capture occurs, I have found nothing much faster than just starting all over, due to my very simplistic data structure. One could take the time to restore those points but this is expensive with naive data structures. It's often not productive to play to points that have been captured - often a complete waste of time for either side. There may be some enhancements where this fact is used to advantage, but I'm not sure how to reliably test when this should and shouldn't be done. Lukasz Lew does something far more sophisticated and very fast using the concept of pseudo liberties which you might want to look into. - Don On Sun, 2007-05-27 at 13:21 -0400, Jason House wrote: > As I get into the home stretch of rewriting the core of my bot, I want > to add a monte carlo player. I've realized that picking a random move > to play is non-trivial since it's such a key element in playout speed. > > An array of legal positions has easy lookup, but may not be easy to > maintain... I guess it'd require storing a mapping between board > position and index into the legal positions array so that a move that > becomes illegal can be quickly removed (by moving the item from the tail > of the array into the empty location). > > Looking at libego, I see it does a variant on this where it maintains > an array of empty points. If the random index it picks is disallowed, > it'll scan through the array (with wrapping around the end) until it > either finds an allowed move or returns to its starting point. > > Which methods have people tried and what works best? > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
