Re: computer-go: unmake move?

["Tristan Cazenave" <cazenave@xxxxxxxxxxxxxxxxx>]

>I don't think I could make a specialized 2 ladder searcher that was 10
times
>faster than my tactical search.  My current search spends about half
>its time making and unmaking moves, so a faster move generator can
>only speed it up by a factor of two.  My tactical make/unmake only
>changes the data structures that are needed for tactics (liberty count,
>string combine and split, adjacent enemy strings, etc.), and I think it
would
>have to be the same for 2 liberty searches.
>

The 2 liberty search is my QS search. The reason why I was not
considering taking adjacent strings in atari is because I did
not use the same move generator and I did not made and unmade
moves in my 2 liberty search so as to be faster (an idea that
comes from Mark Boon and that Bruno Bouzy told me). By not
updating strings in the 2 liberty search you can be
faster but the inconvienent is that you cannot easily look
some moves as in the example I gave. But maybe it is possible,
Mark have you some special tricks for that ? I personnaly use
a bit array of the intersections of the board, initially marked
with the stones of the string to capture, and I verify that
during the ladder, it does not connect to another string,
I verify that it is a ladder simply by counting the number
of empty intersections at each 'move'...
However, as David pointed it, I am not sure it has a lot
of impact on the search speed (I find roughly the same time
with optimizations or without them and more interesting moves
 considered ).


>Does anyone else do this kind of two stage tactical search (iterative
>deepening on liberty count rather than on search depth)?
>
>The move generator looks at features of each plausible move and assigns
>values
>to them, and adds them up, then selects the top few cantidates.  So yuo
>could say that every move choice is due to some heuristic :)
>


In my playing program, I have something similar but more
simple that makes the search twice as fast...
Have you tried it ? What is the speed-up ?

Tristan.
(very happy to participate to a thread on tactical search...)