[computer-go] Re: libego feedback

[Łukasz Lew]

On 4/11/07, Darren Cook <darren at dcook.org> wrote:
> Hi Lucasz,

Hi,

> I spent some time studying your libego code today. It was educational
> (I'd thought you were getting the speed by using assembler in key
> functions, so I was surprised and pleased it is all pure C++).

I'm happy I refrained for going into asm (I was considering HLA). :)

> I've some
> questions and comments. If you want to reply to any of these on the
> computer go mailing list that is fine by me.

OK :)

>
>
> OPTIMIZATION
>
> * In a few places you use a 1 element array. E.g. in class uct_t: tree_t
> tree[1]; Is this faster than simply using tree_t tree; ? Is there a
> standard name for this type of optimization?

Some time ago I was programming in C with g++ compiler style.
So I used no references. It was convenient convention for me to
declare every complex variable as one element array to have pointed
bind to the name. And I used those pointers
everywhere. I took this idea from Fruit (chess program) source.

>
> * In a couple of places in class uct_t you use the trick of moving a
> parameter to be a template parameter. This is one of the nice things
> about C++ and I use it a lot (when I care about speed). I wondered why
> you didn't use it more?

I tried to have two board_t::play functions - separate for black and white.
This way I could avoid some branches, but unfortunately it turned out
the it is slower.
I guess it's because jump prediction worked not good when it had to
deal with twice as big code. (code cache-swapping  could be a reason
too)

>
> * uct.cpp, Many node_t functions can be marked const.

I have not tried to optimize uct yet.

>
>
> ACCURACY
>
> * In uct_t::do_playout(), when two passes in a row then you break and
> score the game at that point. However I don't see anything to stop the
> two passes happening anywhere in the tree, which would upset accuracy.

They can happen anywhere in the tree, pass is just another move.
I do not see why it should upset the accuracy.


>
> Why not do simple_playout::run() after the two passes to make sure the
> board is settled?  BTW, the only other exit point from that loop already
> does this, so simple_playout::run() could be moved out of the loop to
> just before the call to play_board->winner().

Because of seki :)

>
> Note: I believe two UCT pass nodes in a row in a UCT tree is quite rare,
> so while it will make little difference to playing strength, it should
> also make little difference to speed, and code complexity stays
> basically the same.
>

Because my own Go research goes in other direction and I get no
feedback about UCT
in libego therefore uct.cpp is just proof-of-concept by now.


>
> UCT GENERALLY
>
> * Is the use of is_mature() (to require 100 playouts before expanding
> out a UCT node) simply to save memory (and some speed)? Or does it also
> increase playing strength as well? I know this was discussed on the
> computer go list, but only remember it for saving memory.
>

UCT adds one node each time it makes a new playout. Equally well it
could be 2 nodes or one node for each 2 playouts. It's arbitrary.
I chosen one node for each 100 playouts because it gets about 100*n
playouts to get each child visited n times.


>
> * In a real game, the tree (i.e. the uct_t object) is thrown away by
> each call to genmove. Wouldn't it be better to make this a global, and
> then when a move is chosen just delete the sub-trees for the moves that
> weren't chosen.
>
> Pros: It will start with a more informative tree, instead of having to
> build it from scratch each time. This should be the equivalent of an
> extra 20-50% playouts, for free.
>
> Cons: More code complexity. Also, the program can start playing more
> weakly if the user uses undo_move() a lot (not weaker than without the
> idea, but it may be more confusing).
>
> Note: More memory usage, but no different to if number of playouts were
> increased, so I don't think this is a con.

It's a good idea, It was a next thing on my UCT to-do list. But as I
said before.
uct.cpp is very far in quality from the rest of libego library.

>
>
> Darren
>
> P.S. Thanks very much for this library. It allows me to immediately
> experiment with some UCT ideas without having to spend a month
> developing, debugging and optimizing my own code. (If those ideas turn
> out to be good then of course afterwards I will spend that month writing
> my own version. But for the moment I can work on the fun bit!) If my
> experiments work out well I'll let you know.

Thanks for Your thanks and remarks. That's my motivator ;)

Regards,
Łukasz Lew

PS
Can You connect MLSN to all those dictionaries that Wakan uses?
http://wakan.manga.cz/
(EDICT primarily)

>
>
> --
> Darren Cook
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/work/charts/  (My flash charting demos)
>