[computer-go] mathematical morphology

[Rémi Coulom]

Nick Knol wrote:
> Hi all,
>
> This is my first post to the list, and I'm pretty new to this, so 
> sorry if I break from etiquette.
>
> I'm currently working on my senior undergrad thesis project.  My idea 
> is to use Bouzy's dilation algorithm ( 
> http://www.gnu.org/software/gnugo/gnugo_14.html ) to find areas of the 
> board that form boundaries of influence between different groups and 
> then concentrate move searches in those areas.  After analyzing about 
> 70 dan-level games on KGS I've found a very strong correlation to the 
> number of moves made in these boundary areas.  I define these 
> boundaries (somewhat naively perhaps) as areas of the board that have 
> an absolute value of less than 4 after performing an arbitrarily large 
> number of dilations on the board (>=30 or so).
>
> I've looked around and haven't found any literature on this specific 
> use of Bouzy's algorithm, so this gives me hope that my idea has some 
> original merit.  Possible applications could include:
>
> -weighting pre-selected moves based on whether they happen to be in a 
> boundary region
> -limiting the branching factor for game tree searches (averages out to 
> be about 78 over the course of the game, still too many but a big 
> improvement from 250)
> -move ordering for game tree searches
> -possible weighting of move distributions for MC-based AI
>
> I was hoping someone more experienced than me could comment on this 
> and possibly let me know if I'm reinventing the wheel and if any of 
> these applications seem plausible.  Thank you.
>
> -Nick
>
> p.s. if anyone is interested in my data i have some matlab files and 
> graphs i could post 

Hi Nick,

welcome to the list.

Your idea is good, and already well known. I believe Bouzy himself did 
something similar to what your suggest (in his paper: History and 
territory heuristics for Monte-Carlo Go). I do it in Crazy Stone, too. 
You can read in my paper, there:
http://remi.coulom.free.fr/Amsterdam2007/
I use MC territory, not mathematical morphology, but the idea is the 
same. On page 8 (table 1) of this paper, you'll see that the "MC Owner" 
feature prefers boundary regions.

Rémi