On 4/11/07, Darren Cook <[EMAIL PROTECTED]> 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)
_______________________________________________ computer-go mailing list [EMAIL PROTECTED] http://www.computer-go.org/mailman/listinfo/computer-go/
