Actually, that sounds almost exactly like what I do (if you reverse the order of your lists). I use an array with index numbers, but the same logic applies, complete with swap and bump of counters. On a capture, I don't do brute force, but rather append the captured points to my list of empty points. List 1 (occupied points) serves no useful purpose for me, so I overwrite it without regard for maintaining the data.
When I implemented the empty point tracking, I kept a second structure to map points on the board back to their respective positions in the empty list. That's probably unneeded overhead... but it did give me a very easy method to test for bugs in how I maintained stuff incrementally. To get rid of it, I'd have to couple the final selected move with the position it came from in the list of empty points. On 10/1/07, Don Dailey <[EMAIL PROTECTED]> wrote: > > -----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/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
