-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Jason House wrote: > On Sun, 2007-09-30 at 12:41 -0400, Don Dailey wrote: >>>> 4. correctness of random move selection strategy. >>> Pick a random empty position. If illegal or eye-filling, remove from >>> consideration the list and repeat. >> Same basic idea. I start by taking all filled points and removing them >> from consider but I reinitialize after a capture. > > The wording sounds like it may be wrong, and the implementation may be > tricky. You start will all points and remove the filled points? If a > selected move is illegal due to suicide, will you consider it again on > later moves prior to a capture? Rejecting eye-filling moves from future > consideration seems ok, but only if it's rejected for only a single move > color... It could be the key capture play later. Hi Jason, My description was greatly simplified, but I do it correctly. Here is the deal: Essentially I have 3 lists, but they are all subsets of 1 master list and maintained together as 1 list. The master list is all 81 points (on 9x9 board that is.) The 3 sub-lists appear in this order: 1. A list of occupied points - always unplayable 2. A list of unoccupied points that have been tried on a given move 3. The rest of the unoccupied points These 3 lists are constantly being maintained. They are all part of the large 81 point master list and 2 pointers track where one ends and the next one begins. To make a random legal move, list 2 starts out as a null list and I choose a point randomly from list 3. Most of these moves are playable, but if one of these moves is illegal due to ko, or eye-filling then I "put the move away" temporarily and do the required swap and bump housekeeping to add this move to list 2 (which reduces list 3 by 1 point via a pointer increment.) In this way, I only try any move 1 time, and I only try moves of unoccupied points. When I run out of unoccupied points to try, then a pass move is generated for this side. However, the opponent may still have moves so after 2 consecutive passes, the game is over. Please note that once a legal move is found and executed, the pointer is reset so that list 2 is once again NULL and list 3 contains ALL unoccupied points so that all unoccupied points once again come under consideration, even if they were previously rejected. But any occupied points are considered permanently unusable and never again considered (until a capture move changes this that is.) When a capture move is made, the list has to reorganized because some of the occupied points are now unoccupied. I do this the "hard" way, I traverse the whole list and rebuild. Even with this expensive operation the program is 2X faster than the more naive approach of not maintaining a separate list of unoccupied points. - - Don -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHARYBDsOllbwnSikRAvovAJ98xpop2o100mncuvdAYVUSgGzbGgCeO6qB R7HG0v2keJd+wLMxQ4AVIKU= =cZrT -----END PGP SIGNATURE----- _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
