Sunday, April 5, 2015

MATLAB go bot

   A while ago it occurred to me that one can express go (a go wiki) rules in terms of images and morphological operations. I decided to do this as a project with a local programming (and related) club I belong to.

   Aside from executing the rules as image manipulations using MATLAB image processing toolkit, I am going to use my unstudied understanding of Monte Carlo simulations and a minimal approach to ‘common sense go’ heuristics.

   In go rules, after playing a move you remove (capture) enemy groups without liberties, and then remove friendly groups without liberties (NZ rules allow suicide, this is rarely important).

Capturing with image manipulations, in more minute detail:

Starting with the enemy color
Split the original board into two images, the friendly mask and the enemy mask.
Label 4-connected regions of the enemy mask.
FOREACH labelled region
Dilate a copy of that region
                Exclude the friendly stone mask
                If the copied region changed size, add the original labelled region to the final image
Add the friendly stones to the final image.
Swap colors and repeat.


   Figure 1 is what I look at while my bot is running (here it is only trying a hundred random games, so especially early on the moves seem very randomly selected). The columns to the left of the board are x and y coordinates relative to the middle square of the board (= 0,0) and the number of wins counted.
figure 1: Game in progress

No comments:

Post a Comment