Thinking about Monte Carlo playouts

   Finished my homework panic (for this particular half of this particular half of this particular week).

   Now I am reflecting on what a Monte Carlo play-out should consist of. At the moment, each empty spot on the board that isn't a living one space eye gets a number, and then those get played out until a capture happens, at which point everyone gets a new random number. Obviously there's some extraneous work being done there.

   One optimization would be instead of redoing the whole board after a capture, simply inserting new legal moves after a capture at random locations would avoid some work.

   Another would be playing known-to-be-non-capturing moves before a capture simultaneously.

   This is somewhat motivated by Hirabot 1d 19x19 repeatedly smashing me on KGS. Also, 15,000 play-outs in under thirty seconds?! In contrast, Ayabots 1k - 1d only do 1500 play-outs and are clearly over-ranked. So my bot needs to be doing 2-3 orders of magnitude more play-outs in only 30 seconds.

Otherwise, I am doing something (at school) with Geant4. I wonder if Geant4 has something to offer my Matlab go evaluation (because mex is so dependable).

Busy studying today

   I only did the first Google Code Jam problem, too. At some point I got fed up with remembering Java syntax, which in hindsight required more preparation. Next year, Python, surely.

   This weekend is dedicated to schoolwork.

   A scintillator like potassium iodide crystals will somewhat get you visible light from higher energy gamma rays, which is easier to find. My use of the term 'x-rays' might be erroneous.

Reading SGFs too

(I'm on holiday)

   Irritatingly, the move numbers I am using are MATLAB figure text. If I 'print the figure to a file', all the text becomes my current font color. If I write the board image as an image, I lose the text. I will argue that I wanted the gif to be small and in that case the numbers don't make sense. 

   The game is Rin Kaiho vs Fujisawa Hideyuki 1982.

Serializing to SGF

At the moment my bots produce stacks of boards (aimed at easily displaying the progress of a game). Also I speculate that 19^2 is small enough that passing them around will not matter a lot.

But the go world runs on Smart Game Format. I really don't write files of arbitrary strings in MATLAB a lot.


function [] = WriteSgfOfBoardStack( boardStack, fileName)
%WriteSgfOfBoardStack Writes an array of boards to an SGF.
%   V. http://www.red-bean.com/sgf/sgf4.html

LETTERS = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's','t'};

sgfText = '(;FF[4](;';

for i = 2 : length(boardStack);
    changesBoard = boardStack(:,:,i)-boardStack(:,:,i-1);
    changesBoard(changesBoard<0)=0;
   
    if mod(i-1,2) == 0
        C = 'W';
    else
        C = 'B';
    end
   
    [row, col] = find(changesBoard);
   
    moveString = strcat(';', C, '[',LETTERS{col},LETTERS{row},']');
   
    sgfText = strcat(sgfText, moveString);
end

sgfText = strcat(sgfText, '))');

f = fopen(fileName, 'w+');

fprintf(f,sgfText);

fclose(f);

end

Why is there the word imaging in the blog address

Also: Reveling in my own beautiful graphics

First Steps Heuristics

This 'bot' picks next moves by following very simple rules and starts with 1 and 2 on the board.

1. For each player, convolve kernels representing 1:3 space jumps and knights moves. (This is the interesting step).
2. Exclude the first and second line and contact moves.
3. Exclude moves only one player is interested in
4. Randomly select from the remaining moves

Go exchanges can be thought of as combinations of mainly jumps and knights' moves ('haengma' : This link could not be useful for anyone). Being able to express these different moves facilitates actual decision making, later.

ImagingBot's future

   Firstly, I uploaded 50 moves of my bot playing itself on a 19^2 board over on L19.

Because I am not building this for high performance computing, playouts are going to be fairly sparse.

Because playouts are sparse, heuristics for choosing what next moves to compare are extremely important. Initially I was hoping to avoid writing in my own heuristics and introducing bias, but I need to examine alternatives to sheer volume of playouts.

Sofaras heuristics, I want to convolve (Wikipedia) conventional 'good' (and bad) go shape kernels to find good shape candidates for next moves. But the implementation is not exceedingly clear. I am not totally sure that convolution is the fastest way of finding these. A friend tells me four channel convolution is well optimized (whereas I would normally just break a problem into 2d convolution). Semantics. Will report back.

   Aside from this, I want to utilize graphics processing (convolution on graphics processors is normal).

ImagingBot playing against itself

   I thought I better post a game. Apologies about the 'game picture' stop measure (using Drago), I have not set up an SGF viewer.

The game ended abruptly with some kind of exception that I need to think about! Black was probably contemptuous of white's last move.

   The parameters for my bot were each move to select six locations, three near enemy stones and three not near enemy stones or the edge, then play out three totally random games at each of those locations, tallying wins and choosing among the most wins for the next move.

   Obviously lots of thought and testing needs to go into what random playouts should be done and how they should be parsed. Mostly I picked small numbers because it's just my Lenovo ideapad hammering away at it.

   My code is in need of ruthless refactoring, which I am quite looking forward to.

   The bot has since been renamed ImagingBot, to reflect its use of image manipulations (and because I later want to rewrite it into C++).

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

End FOREACH

Add the friendly stones to the final image.

Swap colors and repeat.

Voila.

   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