Re: [computer-go] Re: Open source real time Go server
Even though KGS is not open, you can still reverse engineer it, right? Why not create an accessible web interface to KGS? terry mcintyre wrote: If accessibility is the only criterion, a client would do the trick; it would need an open protocol. It's been a bit of an inconvenience that KGS does not publish an open-protocol interface. As for other things we'd like to see improved, we could build a list. My pet peeve is the KGS score estimator, which is often wildly wrong. I've heard complaints about the implementation of the rules, and some have argued that it is not terribly bot-friendly. Terry McIntyre terrymcint...@yahoo.com Everyone wants to live at the expense of the state. They forget that the state wants to live at the expense of everyone. --Frederic Bastiat ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Open source real time Go server
Your point is obvious but that's a horrible proof since there are usually more than one legal moves from which to chose (that means it takes more time). steve uurtamo wrote: As for other things we'd like to see improved, we could build a list. My pet peeve is the KGS score estimator, which is often wildly wrong. an SE can't be any smarter than a computer player that runs in the amount of time that you're willing to wait for the SE to calculate*. so don't expect much. ever. recall that the SE runs locally in your client. s. * proof: if it were, then it would make a better computer player by just evaluating its score estimate at all legal board points and choosing the maximum at each move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper about Mogo's Opening Strategy
I'd like to read it, but that link doesn't work for me. Is it correct? Brian Sheppard wrote: I recommend the paper http://hal.inria.fr/docs/00/36/97/83/PDF/ouvertures9x9.pdf by the Mogo team, which describes how to use a grid to compute Mogo's opening book using coevolution. Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper about Mogo's Opening Strategy
Never mind, the problem was on my side. Michael Williams wrote: I'd like to read it, but that link doesn't work for me. Is it correct? Brian Sheppard wrote: I recommend the paper http://hal.inria.fr/docs/00/36/97/83/PDF/ouvertures9x9.pdf by the Mogo team, which describes how to use a grid to compute Mogo's opening book using coevolution. Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GoChild Web2.0 is live on Google AppEngine
Can you tell us English speakers anything about it? 幼儿围棋 wrote: Hi All, GoChild is designed for learning how to play Go efficiently. Web App - http://gochild2009.appspot.com Official site - http://www.gochildgame.com Regards, gosharplite ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GoChild Web2.0 is live on Google AppEngine
Darren Cook wrote: GoChild is designed for learning how to play Go efficiently. Here is the English link for Michael :-) http://www.gochildgame.com/en/index.htm Thanks! I know how his wife feels -- I'm also still trying to figure out what to do after Ko is created :/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fuego 04 native Windows
Jacques, It has been some time since you made this. Did you have to make changes to any of the original Fuego files? I'm asking because I'm trying to figure out what would go wrong if I dumped current Fuego files into the Windows-buildable source that you provided. Jacques Basaldúa wrote: I have made a native Windows Fuego build compiled with MS Visual Studio 2008. Thanks to the Fuego team for making such a nice program free software !! I will use it to measure some tree metrics to tune my own program and for a validation experiment for an evaluation function I have developed. I will post results when I have any. To test the binary I made it play on todays KGS tournament and won 1 game of 3 against MFOG and 1 game of 3 against Aya + all the other games. It was running on an overclocked (3.6 GHz) i7. The settings were: uct_param_search max_nodes 1250 uct_param_player reuse_subtree 1 uct_param_player ponder 1 go_rules kgs sg_param time_mode real uct_param_search number_threads 8 uct_param_search lock_free 1 uct_param_search virtual_loss 1 uct_param_search number_playouts 2 The binary does around 36k games/sec in the opening rising to 50-60k later. Which is a lot more than the 23.5K of the cygwin version. AFAIK it works Ok with multithreading with and without locking. It is also much smaller and has no .dll dependencies. If someone wants to test it more, it is here: http://www.dybot.com/fuego04nw/fuego.zip And the source code Windows developers always dreamt of but were too shy to ask ;-) (All relevant parts of boost included, 0 static lib dependencies, 0 dynamic lib dependencies, compiles with MS Visual Studio 2008 0 errors 0 warnings.) http://www.dybot.com/fuego04nw/fuego.7z (Compressed with 7z. 7z is free software available at: http://www.7-zip.org/ The command line version is the best option if you don't like programs integrating in Explorer.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] [ANNOUNCE] Computer Go 2009 - complete state of art
Very nice. Do you (or anyone) have the details of (Boon, 2009) concerning arbitrarily shaped patterns? Petr Baudis wrote: Hello! Today I held a presentation on the complete state of art in Computer Go, showing hopefully all the current widely applicable results, most successful strategies and worst current problems (in my interpretation, of course) - you can find it at: http://pasky.or.cz/~pasky/go/ The presentation has a section introducing basic Go rules and tactics so it should be suitable even for AI researches not very familiar with Go. Of course it is not perfect and some parts assume accompanying explanations and few formulas on blackboard, but I think it could still be good material to give quick overview on currently used approaches with sufficient depth to satisfy a computer science scholar, plus quick references to the papers. P.S.: One IMHO important thing I now realize I've missed in the open problems section is parallelization on GPU. P.P.S.: The presentation also shows some preliminary (noticeably positive) results of naive dynamic komi application in handicap games. I plan to publish this later in a paper when I try more approaches and do more comprehensive testing. Hope it's useful, Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go Programming Language
If you thought finding Go(game)-related stuff on the web was hard before... Ben Shoemaker wrote: Has anyone tried programming Go in the Go Programming Language? http://golang.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bitmap Go revisited and mockup implementation
I only showed the first line. There were many more. Gotta go to work though.
René van de Veerdonk wrote:
Micheal,
Is that all the output you get? Did you notice that the first line with
test-error changed ... the second number went from 31 to 32. We did
something! But not what I expected. BTW. The program does not normally
crash, it just stops after its initial testing is completed and errors
were detected. If you actually went from a gazillion line to just one,
we have hit a nerve. I you just didn't bother to copy the rest of the
output, we made no progress. But, since the output actually changed, it
would still be nice to see a few more lines and see the trend.
Thanks for helping ... debugging for someone else must not be the best
use of your time,
René
On Tue, Aug 25, 2009 at 8:03 PM, Michael Williams
michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote:
No. The code is now:
__forceinline
unsigned int bitmap_t::lowest_index () const {
const __m128i comp = _mm_cmpeq_epi32 (_mm_setzero_si128 (), board);
unsigned long m = _mm_movemask_epi8 (comp) ^ 0x;
if (!_BitScanForward (m, m)) return 127;
/* offending instruction */
//return 8*m + __lzcnt (board.m128i_u32[m/4]);
/* new code follows */
unsigned long n;
_BitScanForward (n, board.m128i_u32[m/4]);
return 8*m + (32-n);
}
Debug:
testing _BitScanForward (m, 0): 0 1099227377
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 1103042705
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
test-error [bitmap_t::lowest_index]: 0 32
Release:
testing _BitScanForward (m, 0): 0 16843009
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 4
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
test-error [bitmap_t::lowest_index]: 0 32
René van de Veerdonk wrote:
Micheal,
Your output is actually correct. The output is undefined when
the second argument to _BitScanForward is zero and that is what
I am explicitly testing for in the method
bitmap_t::lowest_index, which is supposed to return an index to
any set bit (despite the name). Your output shows that it
returns a number that is off in a very predictable way (it seems
that replacing 8*m + n with 8*m + (32-n) on the last line
may do the trick for you, but it breaks my local copy). So, now
I am positively baffled.
Help?
René
On Tue, Aug 25, 2009 at 7:25 PM, Michael Williams
michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com wrote:
Debug build:
testing _BitScanForward (m, 0): 0 842032512
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 840277132
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Release build:
testing _BitScanForward (m, 0): 0 16843009
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 4
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Sucks when they produce different results.
René van de Veerdonk wrote:
Micheal,
Thanks for trying. Could you try one or two more things?
(1) Replace the _BitScanForward in the new code to
_BitScanReverse. This probably won't help.
(2) Add this to bitmapgo.cpp:
/* sandbox */
const bool sandbox = true;
void test_sandbox () {
unsigned long m = 220;
unsigned char test_it = _BitScanForward (m, 0);
std::cout testing _BitScanForward (m, 0):
(int) test_it m \n;
test_it = _BitScanForward (m, 1);
std::cout testing _BitScanForward (m, 1):
(int) test_it m \n;
test_it = _BitScanForward (m, 256);
std::cout testing _BitScanForward (m, 256):
(int) test_it m \n;
test_it = _BitScanReverse (m, 0);
std::cout testing _BitScanReverse (m, 0):
(int) test_it m \n;
test_it = _BitScanReverse (m, 1);
std::cout testing _BitScanReverse (m, 1):
(int) test_it m \n;
test_it = _BitScanReverse (m, 256);
std::cout testing _BitScanReverse (m, 256
Re: [computer-go] Bitmap Go revisited and mockup implementation
(AMD Phenom CPU) Michael Williams wrote: It came through fine the first time. Gmail probably hid the duplicate text from you for convenience since it saw that it was text that you already sent out. Or something. I can compile the original (9x9) bitmap Go files in Windows 7 x64, but when I run it I get this: test-error [bitmap_t::lowest_index]: 0 31 test-error [bitmap_t::lowest_index]: 1 30 test-error [bitmap_t::lowest_index]: 2 29 test-error [bitmap_t::lowest_index]: 3 28 test-error [bitmap_t::lowest_index]: 4 27 test-error [bitmap_t::lowest_index]: 5 26 test-error [bitmap_t::lowest_index]: 6 25 test-error [bitmap_t::lowest_index]: 7 24 test-error [bitmap_t::lowest_index]: 8 23 test-error [bitmap_t::lowest_index]: 9 22 test-error [bitmap_t::lowest_index]: 10 21 test-error [bitmap_t::lowest_index]: 11 20 test-error [bitmap_t::lowest_index]: 12 19 test-error [bitmap_t::lowest_index]: 13 18 test-error [bitmap_t::lowest_index]: 14 17 test-error [bitmap_t::lowest_index]: 15 16 test-error [bitmap_t::lowest_index]: 16 15 test-error [bitmap_t::lowest_index]: 17 14 test-error [bitmap_t::lowest_index]: 18 13 test-error [bitmap_t::lowest_index]: 19 12 test-error [bitmap_t::lowest_index]: 20 11 test-error [bitmap_t::lowest_index]: 21 10 test-error [bitmap_t::lowest_index]: 22 9 test-error [bitmap_t::lowest_index]: 23 8 test-error [bitmap_t::lowest_index]: 24 7 test-error [bitmap_t::lowest_index]: 25 6 test-error [bitmap_t::lowest_index]: 26 5 test-error [bitmap_t::lowest_index]: 27 4 test-error [bitmap_t::lowest_index]: 28 3 test-error [bitmap_t::lowest_index]: 29 2 test-error [bitmap_t::lowest_index]: 30 1 test-error [bitmap_t::lowest_index]: 31 0 test-error [bitmap_t::lowest_index]: 32 63 test-error [bitmap_t::lowest_index]: 33 62 test-error [bitmap_t::lowest_index]: 34 61 test-error [bitmap_t::lowest_index]: 35 60 test-error [bitmap_t::lowest_index]: 36 59 test-error [bitmap_t::lowest_index]: 37 58 test-error [bitmap_t::lowest_index]: 38 57 test-error [bitmap_t::lowest_index]: 39 56 test-error [bitmap_t::lowest_index]: 40 55 test-error [bitmap_t::lowest_index]: 41 54 test-error [bitmap_t::lowest_index]: 42 53 test-error [bitmap_t::lowest_index]: 43 52 test-error [bitmap_t::lowest_index]: 44 51 test-error [bitmap_t::lowest_index]: 45 50 test-error [bitmap_t::lowest_index]: 46 49 test-error [bitmap_t::lowest_index]: 47 48 test-error [bitmap_t::lowest_index]: 48 47 test-error [bitmap_t::lowest_index]: 49 46 test-error [bitmap_t::lowest_index]: 50 45 test-error [bitmap_t::lowest_index]: 51 44 test-error [bitmap_t::lowest_index]: 52 43 test-error [bitmap_t::lowest_index]: 53 42 test-error [bitmap_t::lowest_index]: 54 41 test-error [bitmap_t::lowest_index]: 55 40 test-error [bitmap_t::lowest_index]: 56 39 test-error [bitmap_t::lowest_index]: 57 38 test-error [bitmap_t::lowest_index]: 58 37 test-error [bitmap_t::lowest_index]: 59 36 test-error [bitmap_t::lowest_index]: 60 35 test-error [bitmap_t::lowest_index]: 61 34 test-error [bitmap_t::lowest_index]: 62 33 test-error [bitmap_t::lowest_index]: 63 32 test-error [bitmap_t::lowest_index]: 64 95 test-error [bitmap_t::lowest_index]: 65 94 test-error [bitmap_t::lowest_index]: 66 93 test-error [bitmap_t::lowest_index]: 67 92 test-error [bitmap_t::lowest_index]: 68 91 test-error [bitmap_t::lowest_index]: 69 90 test-error [bitmap_t::lowest_index]: 70 89 test-error [bitmap_t::lowest_index]: 71 88 test-error [bitmap_t::lowest_index]: 72 87 test-error [bitmap_t::lowest_index]: 73 86 test-error [bitmap_t::lowest_index]: 74 85 test-error [bitmap_t::lowest_index]: 75 84 test-error [bitmap_t::lowest_index]: 76 83 test-error [bitmap_t::lowest_index]: 77 82 test-error [bitmap_t::lowest_index]: 78 81 test-error [bitmap_t::lowest_index]: 79 80 test-error [bitmap_t::lowest_index]: 80 79 test-error-1 [bitmap_t::is_one_bit]: 0 test-error-1 [bitmap_t::is_one_bit]: 1 test-error-1 [bitmap_t::is_one_bit]: 2 test-error-1 [bitmap_t::is_one_bit]: 3 test-error-1 [bitmap_t::is_one_bit]: 4 test-error-1 [bitmap_t::is_one_bit]: 5 test-error-1 [bitmap_t::is_one_bit]: 6 test-error-1 [bitmap_t::is_one_bit]: 7 test-error-1 [bitmap_t::is_one_bit]: 8 test-error-1 [bitmap_t::is_one_bit]: 9 test-error-1 [bitmap_t::is_one_bit]: 10 test-error-1 [bitmap_t::is_one_bit]: 11 test-error-1 [bitmap_t::is_one_bit]: 12 test-error-1 [bitmap_t::is_one_bit]: 13 test-error-1 [bitmap_t::is_one_bit]: 14 test-error-1 [bitmap_t::is_one_bit]: 15 test-error-1 [bitmap_t::is_one_bit]: 16 test-error-1 [bitmap_t::is_one_bit]: 17 test-error-1 [bitmap_t::is_one_bit]: 18 test-error-1 [bitmap_t::is_one_bit]: 19 test-error-1 [bitmap_t::is_one_bit]: 20 test-error-1 [bitmap_t::is_one_bit]: 21 test-error-1 [bitmap_t::is_one_bit]: 22 test-error-1 [bitmap_t::is_one_bit]: 23 test-error-1 [bitmap_t::is_one_bit]: 24 test-error-1 [bitmap_t::is_one_bit]: 25 test-error-1 [bitmap_t::is_one_bit]: 26 test-error-1 [bitmap_t::is_one_bit]: 27 test-error-1 [bitmap_t::is_one_bit]: 28 test-error-1 [bitmap_t::is_one_bit]: 29 test-error-1 [bitmap_t
Re: [computer-go] Bitmap Go revisited and mockup implementation
That doesn't seem to have any effect on the results.
René van de Veerdonk wrote:
Hi Micheal,
Thanks for the test (Intel - AMD, Windows XP - Windows 7, x32 - x64,
great, three birds with one stone!). So much for portability. But,
hooray for test-cases!
This may be related to the __lzcnt intrinsic, giving you a completely
different result, i.e., 32 - my result. Could you try replacing this
function in bitmap.cpp? I believe I tested this alternative during
development and it generates only slightly worse performing code.
__forceinline
unsigned int bitmap_t::lowest_index () const {
const __m128i comp = _mm_cmpeq_epi32 (_mm_setzero_si128 (), board);
unsigned long m = _mm_movemask_epi8 (comp) ^ 0x;
if (!_BitScanForward (m, m)) return 127;
/* offending instruction */
//return 8*m + __lzcnt (board.m128i_u32[m/4]);
/* new code follows */
unsigned long n;
_BitScanForward (n, board.m128i_u32[m/4]);
return 8*m + n;
}
René
PS. x64 ... new playground, you could use __lzcnt64 ... so many things
to try!
On Tue, Aug 25, 2009 at 5:43 PM, Michael Williams
michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote:
(AMD Phenom CPU)
Michael Williams wrote:
It came through fine the first time. Gmail probably hid the
duplicate text from you for convenience since it saw that it was
text that you already sent out. Or something.
I can compile the original (9x9) bitmap Go files in Windows 7
x64, but when I run it I get this:
test-error [bitmap_t::lowest_index]: 0 31
test-error [bitmap_t::lowest_index]: 1 30
test-error [bitmap_t::lowest_index]: 2 29
test-error [bitmap_t::lowest_index]: 3 28
test-error [bitmap_t::lowest_index]: 4 27
test-error [bitmap_t::lowest_index]: 5 26
test-error [bitmap_t::lowest_index]: 6 25
test-error [bitmap_t::lowest_index]: 7 24
test-error [bitmap_t::lowest_index]: 8 23
test-error [bitmap_t::lowest_index]: 9 22
test-error [bitmap_t::lowest_index]: 10 21
test-error [bitmap_t::lowest_index]: 11 20
test-error [bitmap_t::lowest_index]: 12 19
test-error [bitmap_t::lowest_index]: 13 18
test-error [bitmap_t::lowest_index]: 14 17
test-error [bitmap_t::lowest_index]: 15 16
test-error [bitmap_t::lowest_index]: 16 15
test-error [bitmap_t::lowest_index]: 17 14
test-error [bitmap_t::lowest_index]: 18 13
test-error [bitmap_t::lowest_index]: 19 12
test-error [bitmap_t::lowest_index]: 20 11
test-error [bitmap_t::lowest_index]: 21 10
test-error [bitmap_t::lowest_index]: 22 9
test-error [bitmap_t::lowest_index]: 23 8
test-error [bitmap_t::lowest_index]: 24 7
test-error [bitmap_t::lowest_index]: 25 6
test-error [bitmap_t::lowest_index]: 26 5
test-error [bitmap_t::lowest_index]: 27 4
test-error [bitmap_t::lowest_index]: 28 3
test-error [bitmap_t::lowest_index]: 29 2
test-error [bitmap_t::lowest_index]: 30 1
test-error [bitmap_t::lowest_index]: 31 0
test-error [bitmap_t::lowest_index]: 32 63
test-error [bitmap_t::lowest_index]: 33 62
test-error [bitmap_t::lowest_index]: 34 61
test-error [bitmap_t::lowest_index]: 35 60
test-error [bitmap_t::lowest_index]: 36 59
test-error [bitmap_t::lowest_index]: 37 58
test-error [bitmap_t::lowest_index]: 38 57
test-error [bitmap_t::lowest_index]: 39 56
test-error [bitmap_t::lowest_index]: 40 55
test-error [bitmap_t::lowest_index]: 41 54
test-error [bitmap_t::lowest_index]: 42 53
test-error [bitmap_t::lowest_index]: 43 52
test-error [bitmap_t::lowest_index]: 44 51
test-error [bitmap_t::lowest_index]: 45 50
test-error [bitmap_t::lowest_index]: 46 49
test-error [bitmap_t::lowest_index]: 47 48
test-error [bitmap_t::lowest_index]: 48 47
test-error [bitmap_t::lowest_index]: 49 46
test-error [bitmap_t::lowest_index]: 50 45
test-error [bitmap_t::lowest_index]: 51 44
test-error [bitmap_t::lowest_index]: 52 43
test-error [bitmap_t::lowest_index]: 53 42
test-error [bitmap_t::lowest_index]: 54 41
test-error [bitmap_t::lowest_index]: 55 40
test-error [bitmap_t::lowest_index]: 56 39
test-error [bitmap_t::lowest_index]: 57 38
test-error [bitmap_t::lowest_index]: 58 37
test-error [bitmap_t::lowest_index]: 59 36
test-error [bitmap_t::lowest_index]: 60 35
test-error [bitmap_t::lowest_index]: 61 34
test-error [bitmap_t::lowest_index]: 62 33
test-error [bitmap_t::lowest_index]: 63 32
test-error [bitmap_t::lowest_index]: 64 95
test-error [bitmap_t::lowest_index]: 65 94
test-error [bitmap_t::lowest_index]: 66 93
test-error [bitmap_t::lowest_index]: 67 92
test-error
Re: [computer-go] Bitmap Go revisited and mockup implementation
Debug build:
testing _BitScanForward (m, 0): 0 842032512
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 840277132
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Release build:
testing _BitScanForward (m, 0): 0 16843009
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 4
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Sucks when they produce different results.
René van de Veerdonk wrote:
Micheal,
Thanks for trying. Could you try one or two more things?
(1) Replace the _BitScanForward in the new code to _BitScanReverse. This
probably won't help.
(2) Add this to bitmapgo.cpp:
/* sandbox */
const bool sandbox = true;
void test_sandbox () {
unsigned long m = 220;
unsigned char test_it = _BitScanForward (m, 0);
std::cout testing _BitScanForward (m, 0):
(int) test_it m \n;
test_it = _BitScanForward (m, 1);
std::cout testing _BitScanForward (m, 1):
(int) test_it m \n;
test_it = _BitScanForward (m, 256);
std::cout testing _BitScanForward (m, 256):
(int) test_it m \n;
test_it = _BitScanReverse (m, 0);
std::cout testing _BitScanReverse (m, 0):
(int) test_it m \n;
test_it = _BitScanReverse (m, 1);
std::cout testing _BitScanReverse (m, 1):
(int) test_it m \n;
test_it = _BitScanReverse (m, 256);
std::cout testing _BitScanReverse (m, 256):
(int) test_it m \n;
}
and add a line something like this in the main program:
if (test sandbox) test_sandbox (); /* new line */
if (test verify) test = test_bitmap_t::test (); /* already there */
That does not solve anything, but it may tell me if those functions are
doing for you what they do for me.
My output is:
testing _BitScanForward (m, 0): 0 16843009
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 3432104
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Thanks, I really appreciate your help !
René
On Tue, Aug 25, 2009 at 6:38 PM, Michael Williams
michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote:
That doesn't seem to have any effect on the results.
René van de Veerdonk wrote:
Hi Micheal,
Thanks for the test (Intel - AMD, Windows XP - Windows 7, x32
- x64, great, three birds with one stone!). So much for
portability. But, hooray for test-cases!
This may be related to the __lzcnt intrinsic, giving you a
completely different result, i.e., 32 - my result. Could you try
replacing this function in bitmap.cpp? I believe I tested this
alternative during development and it generates only slightly
worse performing code.
__forceinline
unsigned int bitmap_t::lowest_index () const {
const __m128i comp = _mm_cmpeq_epi32 (_mm_setzero_si128 (), board);
unsigned long m = _mm_movemask_epi8 (comp) ^ 0x;
if (!_BitScanForward (m, m)) return 127;
/* offending instruction */
//return 8*m + __lzcnt (board.m128i_u32[m/4]);
/* new code follows */
unsigned long n;
_BitScanForward (n, board.m128i_u32[m/4]);
return 8*m + n;
}
René
PS. x64 ... new playground, you could use __lzcnt64 ... so many
things to try!
On Tue, Aug 25, 2009 at 5:43 PM, Michael Williams
michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com wrote:
(AMD Phenom CPU)
Michael Williams wrote:
It came through fine the first time. Gmail probably hid the
duplicate text from you for convenience since it saw that
it was
text that you already sent out. Or something.
I can compile the original (9x9) bitmap Go files in Windows 7
x64, but when I run it I get this:
test-error [bitmap_t::lowest_index]: 0 31
test-error [bitmap_t::lowest_index]: 1 30
test-error [bitmap_t::lowest_index]: 2 29
test-error [bitmap_t::lowest_index]: 3 28
test-error [bitmap_t::lowest_index]: 4 27
test-error [bitmap_t::lowest_index]: 5 26
test-error [bitmap_t::lowest_index]: 6 25
test-error [bitmap_t::lowest_index]: 7 24
test-error [bitmap_t::lowest_index]: 8 23
test-error [bitmap_t::lowest_index]: 9 22
test-error [bitmap_t::lowest_index]: 10 21
test-error [bitmap_t::lowest_index]: 11 20
test-error [bitmap_t::lowest_index]: 12 19
test-error [bitmap_t::lowest_index]: 13 18
test-error [bitmap_t::lowest_index]: 14 17
Re: [computer-go] Bitmap Go revisited and mockup implementation
No. The code is now:
__forceinline
unsigned int bitmap_t::lowest_index () const {
const __m128i comp = _mm_cmpeq_epi32 (_mm_setzero_si128 (), board);
unsigned long m = _mm_movemask_epi8 (comp) ^ 0x;
if (!_BitScanForward (m, m)) return 127;
/* offending instruction */
//return 8*m + __lzcnt (board.m128i_u32[m/4]);
/* new code follows */
unsigned long n;
_BitScanForward (n, board.m128i_u32[m/4]);
return 8*m + (32-n);
}
Debug:
testing _BitScanForward (m, 0): 0 1099227377
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 1103042705
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
test-error [bitmap_t::lowest_index]: 0 32
Release:
testing _BitScanForward (m, 0): 0 16843009
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 4
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
test-error [bitmap_t::lowest_index]: 0 32
René van de Veerdonk wrote:
Micheal,
Your output is actually correct. The output is undefined when the second
argument to _BitScanForward is zero and that is what I am explicitly
testing for in the method bitmap_t::lowest_index, which is supposed to
return an index to any set bit (despite the name). Your output shows
that it returns a number that is off in a very predictable way (it seems
that replacing 8*m + n with 8*m + (32-n) on the last line may do the
trick for you, but it breaks my local copy). So, now I am positively
baffled.
Help?
René
On Tue, Aug 25, 2009 at 7:25 PM, Michael Williams
michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote:
Debug build:
testing _BitScanForward (m, 0): 0 842032512
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 840277132
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Release build:
testing _BitScanForward (m, 0): 0 16843009
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 4
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Sucks when they produce different results.
René van de Veerdonk wrote:
Micheal,
Thanks for trying. Could you try one or two more things?
(1) Replace the _BitScanForward in the new code to
_BitScanReverse. This probably won't help.
(2) Add this to bitmapgo.cpp:
/* sandbox */
const bool sandbox = true;
void test_sandbox () {
unsigned long m = 220;
unsigned char test_it = _BitScanForward (m, 0);
std::cout testing _BitScanForward (m, 0):
(int) test_it m \n;
test_it = _BitScanForward (m, 1);
std::cout testing _BitScanForward (m, 1):
(int) test_it m \n;
test_it = _BitScanForward (m, 256);
std::cout testing _BitScanForward (m, 256):
(int) test_it m \n;
test_it = _BitScanReverse (m, 0);
std::cout testing _BitScanReverse (m, 0):
(int) test_it m \n;
test_it = _BitScanReverse (m, 1);
std::cout testing _BitScanReverse (m, 1):
(int) test_it m \n;
test_it = _BitScanReverse (m, 256);
std::cout testing _BitScanReverse (m, 256):
(int) test_it m \n;
}
and add a line something like this in the main program:
if (test sandbox) test_sandbox (); /* new line */
if (test verify) test = test_bitmap_t::test (); /* already
there */
That does not solve anything, but it may tell me if those
functions are doing for you what they do for me.
My output is:
testing _BitScanForward (m, 0): 0 16843009
testing _BitScanForward (m, 1): 1 0
testing _BitScanForward (m, 256): 1 8
testing _BitScanReverse (m, 0): 0 3432104
testing _BitScanReverse (m, 1): 1 0
testing _BitScanReverse (m, 256): 1 8
Thanks, I really appreciate your help !
René
On Tue, Aug 25, 2009 at 6:38 PM, Michael Williams
michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com
mailto:michaelwilliam...@gmail.com wrote:
That doesn't seem to have any effect on the results.
René van de Veerdonk wrote:
Hi Micheal,
Thanks for the test (Intel - AMD, Windows XP - Windows
7, x32
- x64, great, three birds with one stone!). So much for
portability. But, hooray for test-cases!
This may be related to the __lzcnt intrinsic, giving you a
completely different result, i.e., 32 - my result. Could
you try
replacing
Re: [computer-go] Bitmap Go revisited and mockup implementation
If an engine (or an engine's playout policy) needs to check the legality of every move before making a selection, this could still be a benefit. René van de Veerdonk wrote: David, Confession: I have not tested 19x19. As you have noted, and others before you over the years, a 19x19 board does not fit in one but three 128-bit registers and there would be a rather big penalty as a result, perhaps (likely?) wiping out all of the benefits of bitmaps. Antoine voiced his disappointment about the speed advantage even on 9x9 in the e-mail to the list that served as my basis. My hope, as Hideko Kato points out, is in longer registers or perhaps being able to port this to a GPU. A 64-bit OS with twice the number registers would also surely help out. Nevertheless, I was surprised that I was able to get to almost the same level of speed as Libego provides. The goals for this mockup were very humble: (1) to provide a basic implementation to see what it can do (and if I could do it), and (2) learn how to work with assembly and/or intrinsic functions (I had never done that before). It may not be too hard to try 19x19 and just see what happens. I may attempt this as a follow-up. René van de Veerdonk 2009/8/23 David Fotland fotl...@smart-games.com mailto:fotl...@smart-games.com How much would you lose for 19x19 board? A board representation is not very interesting unless it scales to 19 line boards. David *From:* computer-go-boun...@computer-go.org mailto:computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org mailto:computer-go-boun...@computer-go.org] *On Behalf Of *René van de Veerdonk *Sent:* Sunday, August 23, 2009 1:11 PM *To:* computer-go@computer-go.org mailto:computer-go@computer-go.org *Subject:* [computer-go] Bitmap Go revisited and mockup implementation Hi all, After years of reading this very interesting list, I decided to make my first contribution this week after reading once again about bitmap go. There is no freely available implementation of a bitmap based engine that I know of, so here is a start. Note that I am not a professional programmer, self-taught, and this is a part-time hobby, so do not expect perfect form. The attachment is an attempt to create an efficient implementation of a bitmap based light playout engine, following mostly the recommendations as spelled out by Antoine de Maricourt in his November 2006 message to this list. The application is single threaded and achieves around 75-80 kpps on my Centrino Duo 2.4 GHz Intel labtop. The mockup was developed in C/C++ using the Microsoft Visual Studio 2008 IDE for Windows XP (32-bit) and undoubtedly suffers from portability issues as a result. The 128-bit SSE instructions are called through intrinsic functions, hopefully at least these interfaces are the same for other compilers. The single goal of this mockup was to do some benchmarking, so there is no gtp-interface, but that would be rather easy to add for those skilled in the art. The standard rules are used with one exception, the Brown eye-rule is used. Multi-stone suicide is explicitly forbidden. No superko checks are performed during playouts, and there is no mercy-rule either. I would be particularly interested to know if a 64-bit OS will improve the performance significantly, as it does have a lot less register pressure. Moving to a 64-bit OS will also make some instructions available that allow for further simplifications/efficiency improvements in the code. As will enabling SSE3 or SSE4.1 instructions. One note, the random number generator used is from Agner Fog's public library and was not included in the attachment. You will have to provide a random number generator yourself or download the appropriate version from his well-known website (www.agner.org/optimize http://www.agner.org/optimize) I hope this is the start of a discussion about further improvements that can be made, but you may use this code as you wish with no restrictions or guarantees. See the readme.txt file included in the attachment for more details (also partially included below). Comments and feedback welcome, René van de Veerdonk Excerpts from the readme.txt file: Introduction: = Mockup of a high performance implementation of the game of Go using bitmaps as the principle datastructures. This implementation is limited to measuring the performance of the principle components by playing random playouts from an empty 9x9 board, using Chinese scoring, not allowing pass moves until no other moves are available. Suicide is not allowed, neither for single or multi-stone groups. No checks are
Re: [computer-go] Bitmap Go revisited and mockup implementation
For many people on this list, Computer Go is a hobby and that means that it is important to do whatever you find interesting and motivating, event if it may not be the best or most promising direction in order to become the next world champion program. There is room for pushing limits in all directions, IMO. Brian Sheppard wrote: Maven was fast enough, but it was clearly the slowest of all major Scrabble programs. Some programs were 5x faster than Maven. Maven was slow because it was a lot more than a move generator: it played the full game with competent positional scoring. Scoring requires much more time than move generation. So why bother optimizing move generation? I am finding that the same lesson applies to Go. But more so because Scrabble is largely first-order whereas Go is recursive. Pebbles averages ~10K trials per turn. Aya is clearly stronger at 10K trials than Pebbles. Fuego is stronger than Aya. Valkyria is stronger than Fuego, and my impression is that Zen trumps us all. Zen could be better than Pebbles + 400 rating points at 10K trials. Now look at scaling. When Fuego runs a machine that is ~20x as fast as mine, then Fuego is comparable to Zen. Valkyria plays in 19x19 tournaments running on a Pentium M, and scores 50% against much more powerful computers. My conclusion is that the analytic skills of Zen and Valkyria are worth a factor of 20, and I expect the advantage will increase with computer speeds. The crucial issue is to support intelligence. Check out David’s description of MFoG, and Remi’s papers about CrazyStone. I am sure those programs pay attention to speed, but the real issue is whether the engine can do the necessary analysis. Magnus’s posts to this list lament that Valkyria is so slow, but Magnus is clearly excited that his engine supports great analysis. So de-emphasize speed. Can you build a great pattern matcher using bit boards? Can you solve life death positions better? Can you read ladders faster or more accurately? Do bit boards make the program easier to program and debug? Pebbles started with a bit board move generator, but I have been adding other knowledge entities, like liberty counts, string iterators, and eyespace detectors. I am convinced that emphasizing domain knowledge structures will pay off. (That being said, I will borrow your intrinsic functions for my 9x9 template specialization. ☺ Every little bit helps.) Best, Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
In future papers they should avoid using a strong authority like Fuego for the training and instead force it to learn from a naive uniform random playout policy (with 100x or 1000x more playouts) and then build on that with an iterative approach (as was suggested in the paper). I also had another thought. Since they are training the policy to maximize the balance and not the winrate, wouldn't you be able to extract more information from each trial by using the score instead of the game result? The normal pitfalls to doing so do not apply here. Isaac Deutsch wrote: I admit I had trouble understanding the details of the paper. What I think is the biggest problem for applying this to bigger (up to 19x19) games is that you somehow need access to the true value of a move, i.e. it's a win or a loss. On the 5x5 board they used, this might be approximated pretty well, but there's no chance on 19x19 to do so. Am 13.08.2009 um 05:14 schrieb Michael Williams: After about the 5th reading, I'm concluding that this is an excellent paper. Is anyone (besides the authors) doing research based on this? There is a lot to do. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
After about the 5th reading, I'm concluding that this is an excellent paper. Is anyone (besides the authors) doing research based on this? There is a lot to do. David Silver wrote: Hi everyone, Please find attached my ICML paper with Gerry Tesauro on automatically learning a simulation policy for Monte-Carlo Go. Our preliminary results show a 200+ Elo improvement over previous approaches, although our experiments were restricted to simple Monte-Carlo search with no tree on small boards. Abstract In this paper we introduce the first algorithms for efficiently learning a simulation policy for Monte-Carlo search. Our main idea is to optimise the balance of a simulation policy, so that an accurate spread of simulation outcomes is maintained, rather than optimising the direct strength of the simulation policy. We develop two algorithms for balancing a simulation policy by gradient descent. The first algorithm optimises the balance of complete simulations, using a policy gradient algorithm; whereas the second algorithm optimises the balance over every two steps of simulation. We compare our algorithms to reinforcement learning and supervised learning algorithms for maximising the strength of the simulation policy. We test each algorithm in the domain of 5x5 and 6x6 Computer Go, using a softmax policy that is parameterised by weights for a hundred simple patterns. When used in a simple Monte-Carlo search, the policies learnt by simulation balancing achieved significantly better performance, with half the mean squared error of a uniform random policy, and equal overall performance to a sophisticated Go engine. -Dave ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fuego 04 native Windows
Very nice! Thank you. Jacques Basaldúa wrote: I have made a native Windows Fuego build compiled with MS Visual Studio 2008. Thanks to the Fuego team for making such a nice program free software !! I will use it to measure some tree metrics to tune my own program and for a validation experiment for an evaluation function I have developed. I will post results when I have any. To test the binary I made it play on todays KGS tournament and won 1 game of 3 against MFOG and 1 game of 3 against Aya + all the other games. It was running on an overclocked (3.6 GHz) i7. The settings were: uct_param_search max_nodes 1250 uct_param_player reuse_subtree 1 uct_param_player ponder 1 go_rules kgs sg_param time_mode real uct_param_search number_threads 8 uct_param_search lock_free 1 uct_param_search virtual_loss 1 uct_param_search number_playouts 2 The binary does around 36k games/sec in the opening rising to 50-60k later. Which is a lot more than the 23.5K of the cygwin version. AFAIK it works Ok with multithreading with and without locking. It is also much smaller and has no .dll dependencies. If someone wants to test it more, it is here: http://www.dybot.com/fuego04nw/fuego.zip And the source code Windows developers always dreamt of but were too shy to ask ;-) (All relevant parts of boost included, 0 static lib dependencies, 0 dynamic lib dependencies, compiles with MS Visual Studio 2008 0 errors 0 warnings.) http://www.dybot.com/fuego04nw/fuego.7z (Compressed with 7z. 7z is free software available at: http://www.7-zip.org/ The command line version is the best option if you don't like programs integrating in Explorer.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fuego 04 native Windows
Unpack to C:\ETC\Fuego in order for it to compile. Or modify the list of include folders in the project configuration. Jacques Basaldúa wrote: I have made a native Windows Fuego build compiled with MS Visual Studio 2008. Thanks to the Fuego team for making such a nice program free software !! I will use it to measure some tree metrics to tune my own program and for a validation experiment for an evaluation function I have developed. I will post results when I have any. To test the binary I made it play on todays KGS tournament and won 1 game of 3 against MFOG and 1 game of 3 against Aya + all the other games. It was running on an overclocked (3.6 GHz) i7. The settings were: uct_param_search max_nodes 1250 uct_param_player reuse_subtree 1 uct_param_player ponder 1 go_rules kgs sg_param time_mode real uct_param_search number_threads 8 uct_param_search lock_free 1 uct_param_search virtual_loss 1 uct_param_search number_playouts 2 The binary does around 36k games/sec in the opening rising to 50-60k later. Which is a lot more than the 23.5K of the cygwin version. AFAIK it works Ok with multithreading with and without locking. It is also much smaller and has no .dll dependencies. If someone wants to test it more, it is here: http://www.dybot.com/fuego04nw/fuego.zip And the source code Windows developers always dreamt of but were too shy to ask ;-) (All relevant parts of boost included, 0 static lib dependencies, 0 dynamic lib dependencies, compiles with MS Visual Studio 2008 0 errors 0 warnings.) http://www.dybot.com/fuego04nw/fuego.7z (Compressed with 7z. 7z is free software available at: http://www.7-zip.org/ The command line version is the best option if you don't like programs integrating in Explorer.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] RAVE problems
Although I've never done a RAVE implementation (soon, very soon), this is related in the sense that AMAF is related to RAVE: I have recently (yesterday, actually) done some experiments on AMAF with 5-vertex patterns (normal AMAF can be considered 1-vertex patterns). I was not able to observe any improvement in any of the experiments -- small/large number of playouts per move, various AMAF enhancements turned on/off. Very frustrating since it seems like such a reasonable idea. My implementation was as follows: If a playout move did NOT match the vertex's pattern at the root, normal AMAF credit was given. If a playout move DID match the vertex's pattern at root, then the credit was multiplied. So a pattern credit multiplier of 1.0 is equivalent to straight AMAF. I tried values in 1.1 to 2.0. As I said, I couldn't find any improvement. I should try 9-vertex patterns too, but I was discouraged by the 5-vertex results. Brian Sheppard wrote: I have traced many, many bad moves to RAVE failures. This post is a brain dump on what I have learned. SYMPTOMS I classify two failure modes: 1) RAVE searches a bad move because it is good later. 2) RAVE won't search the best move because it is bad later. The first failure mode causes inefficiency. That is, if RAVE Likes a move then it will be searched and accumulate actual UCT trials, and then it must be refuted before the best move can be found. If inefficiency only cost an occasional factor of 2, then I would not worry about it. Unfortunately, RAVE will probably like a move for several ply, which means that inefficiency applies recursively. If you can play several forcing moves to delay consequences, then inefficiency can be fatal. The second failure mode is more problematic, because it is not clear how many moves have to be refuted in order for RAVE to give the best move a trial. Moreover, every trial for every alternative move creates another probably bad RAVE trial for the best move. EXPLANATION IN CAUSALITY TERMS --- RAVE finds moves that correlate with winning. RAVE wants moves that *cause* winning. EXPLANATION IN DOMAIN TERMS Failure mode 1 above occurs because some moves are only playable when we win. For example, we succeed in breaking into the opponent's territory and therefore a move in that region becomes good. Failure mode 2 above occurs when a move that is vital to winning now stops being able to win in the future. For example, suppose that you have a critical semeai. If you don't play a winning move now, then all of those moves become losing moves in the future. PEBBLES vs FUEGO I suspect that RAVE problems are more severe in Pebbles than in Fuego. There are three differences: 1) Fuego has a larger exploration coefficient. (0.7 vs 0.25) 2) Fuego combines UCT and RAVE and then adds the UCT exploration term, whereas Pebbles applies separate RAVE and UCT exploration terms. 3) Fuego's RAVE bonus decreases with distance. In the first two cases, I have measured that Pebbles choices are optimal for Pebbles, despite the problems that ensue. I should test the third difference, but have not yet. WHAT I HAVE DONE ABOUT IT - I have made some headway using special cases. For example, there is a special case involving approach moves: if a move A is self-atari, and the *other* liberty B of that string is not self-atari, then the RAVE score of B will be the higher of the RAVE score of A and the RAVE score of B. (Magnus's idea, BTW.) There are also policies in the playouts that reduce RAVE failures. Fuego has clump correction, for example. RAVE receives better information when the playouts identify better local moves. I have also tested alternatives in the exploration policy. For example, a exploring positions that seem to be losing more broadly than positions that seem to be winning. And the Orego team's suggestion to use the beta distribution to measure variance. These refinements can have large benefits, but they do not completely solve the problem. WHAT SHOULD BE DONE --- IMO, we have to redesign RAVE. I have been slow to do so because RAVE is so powerful. Really, our programs would not play well at all without RAVE. Still, as it is presently conceived, RAVE places a scalability limit on the program. It will have to be addressed eventually. Hillis has proposed that moves have context codes that we can compare against the current context, and only score RAVE if the codes match. My instinct is that this is the right direction. Dave Fotland said that testing 3x3 neighborhoods yielded no benefit. My inference is that contexts should not limit RAVE collection too much. I think that Hillis and Dailey reported tests that allowed RAVE matching against the opponent's moves, with results that were possibly beneficial. Most likely the
Re: [computer-go] Double/Triple Ko situation
You should set the limit to whatever yields the highest ELO in YOUR program. Harry Fearnley wrote: Darren Cook wrote: The largest nakade shape is the rabbity six. My wild guess would be to outlaw self-atari for groups of 7+ stones. The fun thing about computer go is how hard it is to make hard and fast rules: http://senseis.xmp.net/?BiggestKnownEyeSpaceForWhichThereIsANakade Outlawing self-atari of 18+ stones is probably okay, but not quite so useful :-). http://www.dgob.de/dgoz/trmdpe/ Shows where not defending 20 stones in atari is best. This position is easily modified to give a position where self atari is best. Clearly this, as well as the 18-stone nakade, is pathological and will _never_ occur in a real game ... :-) I would guess that there will be a fair number of self-atari of up to 11 stones (especially on the edge, or in the corner, and where there are cutting points) where the self-atari would be the best move. Harry -+-+-+-+-+-+ ha...@goban.demon.co.uk38 Henley St, Oxford, OX4 1ES, UK http://www.goban.demon.co.ukTel: +44 1865 248775 http://harryfearnley.com *** NEW site *** Oxford Go Club:http://www.britgo.org/clubs/oxford_c.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
If your weights are all between 0 and 1: do double r = rand(0 to 1) int i = rand(0 to weightCount - 1) until weight[i] r I think that's right. Mark Boon wrote: When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Big trees
If I think something will overflow a 4-byte, I use an 8-byte. Yeah, I should add the ability to write out an SGF for a part of the tree. Jason House wrote: What do use for your counters? 32 bit numbers max out at 4 billion, and you're already beyond that. Is it possible to generate an SGF file showing the dominant variations with the number of wins and losses? It'd be interesting to see what the bot considers to be the best sequences are... Sent from my iPhone On Jul 10, 2009, at 10:10 PM, Michael Williams michaelwilliam...@gmail.com wrote: Now that I have this system of generating really big game trees, what sort of interesting things could I do with it? The exact number of nodes I can store is not exact because I'm doing various things to reduce each node's footprint when it goes to disk. I'm currently building a tree that is bushy at the root (heavy exploration term) and normal UCT beneath that. It is at 28 billion nodes now and projecting a capacity of 122 billion. The current node rate is about 130k per second (on 1 Core2 core). This is on a 9x9 board. I'm still using Libego for playouts. And I'm deleting symmetrically-equivalent moves from the tree. That is all that gets pruned. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] GTP commands for CGOS
The CGOS page should have a list of the GTP commands required by CGOS. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Big trees
Now that I have this system of generating really big game trees, what sort of interesting things could I do with it? The exact number of nodes I can store is not exact because I'm doing various things to reduce each node's footprint when it goes to disk. I'm currently building a tree that is bushy at the root (heavy exploration term) and normal UCT beneath that. It is at 28 billion nodes now and projecting a capacity of 122 billion. The current node rate is about 130k per second (on 1 Core2 core). This is on a 9x9 board. I'm still using Libego for playouts. And I'm deleting symmetrically-equivalent moves from the tree. That is all that gets pruned. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Big trees
So far, E5 and E6 are neck-and-neck for the favored opening move (E5 was leading almost the whole time until recently). The deepest part of the tree is 35 ply. About 18% of run time is spent swapping to disk. 40% is traversing the tree. 14% is Libego. Michael Williams wrote: Now that I have this system of generating really big game trees, what sort of interesting things could I do with it? The exact number of nodes I can store is not exact because I'm doing various things to reduce each node's footprint when it goes to disk. I'm currently building a tree that is bushy at the root (heavy exploration term) and normal UCT beneath that. It is at 28 billion nodes now and projecting a capacity of 122 billion. The current node rate is about 130k per second (on 1 Core2 core). This is on a 9x9 board. I'm still using Libego for playouts. And I'm deleting symmetrically-equivalent moves from the tree. That is all that gets pruned. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Prediction
Prediction: First, developers and algorithm gurus will expend huge amounts of effort to parallelize code to take advantage of multi-core chips. Then, hardware engineers and physics gurus will give us light-based CPUs and orders of magnitude improvement in single-core performance. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Really basic question
That's the beauty of MC! It really is a beautiful system. Initially, they were totally random playouts. But the more powerful MC Go engines do not do completely random playouts; they do heavy playouts. But if you were to look at a heavy playout, it would still look like a very weak Go player's game. In addition to heavy playouts, there is the tree aspect, which you did not mention. One way to catagorize and MC engine would be whether or not it is MCTS (MC Tree Search). If so, it will play much stronger and can make statements about scalability. Pure MC does not use a tree. Fred Hapgood wrote: I have a really basic question about how MC works in the context of Go. Suppose the problem is to make the first move in a game, and suppose we have accepted as a constraint that we will abstain from just copying some joseki out of a book -- we are going to use MC to figure out the first move de novo. We turn on the software and it begins to play out games. My question is: how does the software pick its first move? Does it move entirely at random? Sometimes it sounds that way MC works is by picking each move at random, from the first to the last, for a million games or so. The trouble is that the number of possible Go games is so large that a million games would not even begin to explore the possibilities. It is hard to imagine anything useful emerging from examining such a small number. So I'm guessing that the moves are not chosen at random. But even if you reduce the possibilities to two options per move, which would be pretty impressive, you'd still run out of your million games in only twenty moves, after which you would be back to picking at random again. What am I missing?? http://www.BostonScienceAndEngineeringLectures.com http://www.pobox.com/~fhapgood ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
I thought you had really heavy nodes? Like 1k bytes or so? But no 8 byte pointers to children? Peter Drake wrote: Well, there is one slight catch... Nodes do not contain pointers to their children. To find the node after making a move, I make the move on the board, then use the Zobrist hash of the new board as a key to search for the child node in the hash table. So traversing the tree would involve re-playing all of the moves from the root. Worse, in the interest of speed, my play code (modeled on LibEGO) doesn't support undoing. To do a recursive traversal like this, I therefore have to perform a board copy every time I backtrack. On the other hand, I think I could get away with only traversing the part of the tree that is still relevant (probably a small fraction of the nodes in use), then traversing the set of nodes linearly to rebuild the free list. In other words, I would perform a mark-and-sweep garbage collection. Peter Drake http://www.lclark.edu/~drake/ On Jul 6, 2009, at 8:02 PM, Michael Williams wrote: If you are talking about 128k nodes, I don't think traversing them will take very long. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Complicated seki with Ko
Suicide? Do you mean self-atari? But there must be more to it than that because you don't have a rule that prevents all self-atari, right? David Fotland wrote: X can't fill J6 because that would be suicide. For the moment, H5 is an eye. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Brian Sheppard Sent: Wednesday, July 01, 2009 4:09 AM To: computer-go@computer-go.org Subject: [computer-go] Complicated seki with Ko With X to move, Many Faces immediately gives about a 1% win rate, and after a few seconds, resigns, showing 23742 playouts with 0.5% win rate. 10 ply principal variation, staring with A7. I don't have any special code to detect superko or give-2, get-1 in playouts, but the playouts don't generate self- atari moves in a seki, so I think it never tries J6 for either side. How does MF recognize that it is a seki without analyzing what happens in the ko? The eye on H5 is false if X can fill J6, so it is premature to use the both sides have an eye with only shared liberties rule. 1 2 3 4 5 6 7 8 9 A - O - O X - - X - B - X O - O X - O O C - O O - O - X O - D X X X O O O O O O E - O X X X O X O O F - - O X O X X X X G - - X X O O X X - H - O X O - O O X X J - O X O O - X - X X to play. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: fuego strength
Turn off Windows update or put the CGOS connect script in the startup folder and set an automatic login. David Fotland wrote: I can have a reduced version of Many Faces up all the time on an old computer, but I don't monitor it, so someone would have to email and remind me when it goes down (usually because of a Microsoft automatic reboot :( ) David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Magnus Persson Sent: Wednesday, June 24, 2009 5:55 AM To: computer-go; Don Dailey Subject: Re: [computer-go] Re: fuego strength On 9x9 I have been worrying of the lack of strong anchors but not enough to complain about. What I think is more important is that stronger programs are actually active on CGOS for longer periods of time. I tried to contribute more by having versions of Valkyria online with a fixed number of playouts. The nice part of that is that I can then run other tests on the same machine that all uses fixed number of playouts and still get proper results. If I run a full strength version of Valkyria on CGOS I cannot have anything else running. So, I think if more people with strong programs had reduced versions running, we could have many middle strength programs it would also become more meaningful to play with full strength programs. I am looking forward to the new server because I think everyone would/should be eager to login to it. Magnus Quoting Don Dailey dailey@gmail.com: 2009/6/24 Christian Nentwich christ...@modeltwozero.com Don, you might have your work cut out if you try to control inflation directly, that can turn into a black art very quickly. Multiple anchors would be preferable. An offline, X * 1000 game playoff between gnugo and another candidate anchor would be enough to fix their rating difference. If their bilateral winnings drift away during continuous play, the anchor rating could be tweaked. It's all a black art anyway. The anchor itself absorbs (or gives away) rating points into the pool. There is not much difference if I just use it to monitor the inflation/deflation and control it directly - except that I have the ability to control the magnitude of this adjustment. And the advantage is that the anchor player becomes a monitor of the inflation level. Don't worry, I don't plan to change it from what I'm doing.The anchor can still monitor inflation if I track what adjustment I would normally make to it if it were not an anchor. For instance if the opponent adjustments tended to be more negative than positive it would indicate that the entire pool was overrated. A way to help compensate is to adjust the initial rating of new players. However, the first game against a brand new player is not rated for the established player and the K constant is so low (for the new players opponents) that it hardly matters. Each player starts with a high K and it gradually drops to 3. But this K is modified from 0% to 100% depending on the opponents K - so the first game against a player a new player is effectively not rated for his opponent.But I think the initial value does have an impact on deflation/inflation of the entire pool. I'm not sure if the worries voiced on this list about anchors are not somewhat overdone. I'm pretty sure it's overdone, but I reserve judgment. I know the phenomenon of self-play intransitivity exists, but it's minor. This is something that can easily be tested privately with a 100,000 games or so to get the amount nailed down - at least for specific trio's of players. I think I may try gnugo vs fuego at 2 different levels. I think that MCTS are all similar and that this is the bigger issue. And as you say, gnugo introduces bias too, it's unavoidable. Other bots, with improvements, may do just as well against an old version of Fuego as the full Fuego does, we don't know. Maybe they would do better than new versions of Fuego. All this reliance on gnugo introduces bias, too, and after all the anchor player is not a single control variable that determines the destiny of the server. Players will still play many different opponents. If Fuego keeps beating the anchor player but losing to everybody else, it still won't get a higher rank. For me, gnugo as an anchor is fine, as I am still experimenting around a low ELO level. For authors of strong programs: I am quite surprised that you are not insisting on a much more highly rated anchor. I remember when KGS was anchored in the kyu ranks, many years ago. I found myself 7 dan one day, until somebody intervened and reanchored the server. The territory far above a single anchor player is unsafe. The thought has occured to me that I should not worry about low resource anchors and that I should simply bite the bullet and insist, as you say, on much stronger anchor players. But the tone of these discussions indicate that
Re: [computer-go] CGOS 19x19 anchor
Fuego gets an advantage because when it plays the anchor, it is playing a version of itself. That's bad for the same reason that it's bad to test against a version of your own program -- inflated results. But I don't think it's a big deal. What about using both Fuego and Mogo as anchors? Don't they both satisfy those requirements? Don Dailey wrote: On Tue, Jun 23, 2009 at 10:10 AM, Hiroshi Yamashita y...@bd.mbn.or.jp mailto:y...@bd.mbn.or.jp wrote: I restarted the 19x19 server. Thank you. I started my bot. I'm thinking about making some specified version of fuego I think using Fuego for anchor is good idea. One problem is maybe latest Fuego will be overrated from weak Fuego anchor. Can you explain this? I don't understand what you are saying. - Don Regards, Hiroshi Yamashita ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: fuego strength
If it were me, I'd run all anchor candidates against the current CGOS to determine the anchor value to use for that anchor candidate. Hideki Kato wrote: I'm running Fatman1, GNU Go and GNU Go MC version for 9x9 and two instances of GNU Go for 13x13, five programs in total, on a dual-core Athlon at home. I strongly believe current anchors are resource friendly enough for older pentium 3, 4 or even Celeron processors and not necessary being changed. Changing anchors is a big problem, similar to changing the International prototypes. Also, GNU Go is used as a reference in almost every computer-go research these days. I'm against that idea, especially for 19x19. Hideki Don Dailey: 5212e61a0906231524k4f068be1q50a2f2806b678...@mail.gmail.com: I'm trying now to get a rough idea about the strength of fuego and it's suitablity as the anchor player. Right now the numbers are very rough as I need more samples. I'm currently looking at: 1. 9x9 fuego at 1000 simulations 2. 19x19 fuego at 3000 simulations. I'm testing against the current CGOS anchors, so FatMan vs fuego at 9x9 and gnugo-3.7.10 at 19x19. At 9x9 fuego appears to be substantially stronger than FatMan, perhaps 100-200 ELO. It also is far faster at 1000 simulation than fatman which requires many more simulations to reach anchor strength. So there is no questions about fuego being a capable anchor for small boards. At this level on 9x9 FatMan is also stronger than gnugo, so fuego is far stronger than gnugo on 9x9 and is very resource friendly too. At 19x19 the story is a bit different. gnugo appears to be significantly stronger, but about twice as slow. There is not enough data to narrow this down much, but it appears to be over 200 ELO weaker at this level. Since fuego is using only about half the CPU resources of gnugo, I can increase the level.I've only played 30 games at 19x19, so this conclusion is subject to signficant error, but it's enough to conclude that it's almost certainly weaker at this level but perhaps not when run at the same CPU intensity as gnugo. Of course at higher levels yet, fuego would be far stronger than gnugo-3.7.10 as seen in the 19x19 cgos tables. But I'm hoping not to push the anchors too hard - hopefully they can be run on someones older spare computer or set unobtrusively in the background on someones desktop machine. - Don inline file ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 1x1 patterns?!
I had never considered using AMAF with larger pattern. That's an interesting idea. Perhaps a 5-vertex cross-shaped pattern or a 3x3 pattern. Has anyone tried this? Magnus Persson wrote: Probably 1x1 patterns implies that different priorities are assigned to the absolute position of empty moves. AMAF can be seen this way. AMAF learns statistics of 1x1 patterns if the move is played in the playout but ignores all information surrounding the move at the time it is played. Another example would be to have lower priorities for the moves at the first and second line. -Magnus Quoting Peter Drake dr...@lclark.edu: I've seen reference in some papers to 1x1 patterns. What does that even mean? A point is either black, white, or vacant, and it's illegal to play there unless it's vacant. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 1x1 patterns?!
Why not start with the 5-vertex cross pattern? Going from 1x1 to 3x3 is a huge jump in complexity and debugability. With 5-vertex patterns, you can enumerate the patterns on paper (there are around 3^4 == 81 of them, ignoring symmetries) to sanity-check the details and see if the general idea works at all. There are too many to enumerate with 9-vertex 3x3 patterns (around 3^8 == 6561, ignoring symmetries). dhillism...@netscape.net wrote: Yes. I think it's a good idea, but the devil is in the details. I've become pretty disenchanted with trying to use 3x3 or 5x5 patterns. Currently, I have about 300 1x1 patterns (I call them context codes) that I'm playing around with. You can also do the same for RAVE without needing any more memory. You only adjust the RAVE values, at a node, after filtering out moves, in the playouts, that don't match the context/pattern for that position at that node. - Dave Hillis -Original Message- From: Michael Williams michaelwilliam...@gmail.com To: computer-go computer-go@computer-go.org Sent: Mon, Jun 22, 2009 3:02 pm Subject: Re: [computer-go] 1x1 patterns?! I had never considered using AMAF with larger pattern. That's an interesting idea. Perhaps a 5-vertex cross-shaped pattern or a 3x3 pattern. Has anyone tried this? Magnus Persson wrote: Probably 1x1 patterns implies that different priorities are assigned to the absolute position of empty moves. AMAF can be seen this way. AMAF learns statistics of 1x1 patterns if the move is played in the playout but ignores all information surrounding the move at the time it is played. Another example would be to have lower priorities for the moves at the first and second line. -Magnus Quoting Peter Drake dr...@lclark.edu mailto:dr...@lclark.edu: I've seen reference in some papers to 1x1 patterns. What does that even mean? A point is either black, white, or vacant, and it's illegal to play there unless it's vacant. ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Save energy, paper and money -- *get the Green Toolbar http://toolbar.aol.com/green/download.html?ncid=emlweusdown0037.* ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Havannah - Go - LittleGolem
Are the games archived? Does the public have access to those archives? Ingo Althöfer wrote: Hello, some time ago I had asked if discussions on computer Havannah were welcome here in the list. The reactions were positive, but (by different reasons) actors preferred not to use the opportunity. In the meantime a computer Havannah scene has developed on the game server http://www.littlegolem.net There it is possible to play Havannah on many different board sizes (side lengths 4, 5, 6, 7, 8, 9, 10). Active programmers are Thomas Reinhardt (D, with TOBRT), Richard Lorentz (US, with Wanderer), Richard Pijl (NL, with gambler), ab (=anonymous, D, with havai). On small boards (4 and 5) the computers are doing really well in the meantime, but from size 6 on their games look strange. It is also possible to run *** GO bots *** there, for instance Gnugo is doing so. Some more information on LittleGolem: * Registration is required, but it is without cost, easy, and without complications. * Thinking time per move is 36 hours in the average (with a buffer of 240 hours; and 20 days of vacation per year). * It is good style to choose names of the type xxx_c for computer accounts. If you do not do this, you should write at least in the profile that a computer is playing. * Some participants on LittleGolem are not playing, but only participating in the interesting fora (one general forum; one special forum for each game). For new players it reqires to have some games completed, otherwise you can not write, but only read. (This is a measure against spam bots.) * At the moment there is, for each player, only one go rating (showing performance on 9, 13, 19) and only one Havannah performance, mixed over all board sizes. But I think there is some hope that this general rating will be split in size-dependent ratings again. Feel free to join LittleGolem. Ingo. PS: My account on Little Golem is Ingo Althofer. http://www.littlegolem.net/jsp/info/player.jsp?plid=11860 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper: Beta Distribution
Section 3.2 describes a pair of tests that took about 4.2 minutes each (if my calculations are correct). Why not play more games and have each game contain more simulations? Writing the code and the paper is the hard part, waiting for a computer to run your code is easy. Peter Drake wrote: An improvement on the UCB/UCT formula: Stogin, J., Chen, Y.-P., Drake, P., and Pellegrino, S. (2009) “The Beta Distribution in the UCB Algorithm Applied to Monte-Carlo Go”. In Proceedings of the 2009 International Conference on Artificial Intelligence, CSREA Press. http://webdisk.lclark.edu/drake/publications/BetaDistribution.pdf Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New CGOS - need your thoughts.
I vote for 2 venues, each optional. Separate rating pools is a must. Łukasz Lew wrote: Maybe we could agree that 1 day out of 7 in a week would be played on 6 times faster time controls. The same bots, connections, logins, the same number of games per week. Different rating of course. This would be a problem only for hardcoded bots with no time control. The advantage would be that we would see how different algorithms (bots) scale. If the ratings would be very similar for most bots, it would mean that we can get faster testing of new ideas. We would know which ideas can be tested of fast time control. Lukasz 2009/6/16 Don Dailey dailey@gmail.com: From what I can see, there is resistance to this idea - so what I'm going to do is to provide venues which are standalone but makes it possible later to add a time control.In other words for now there will be only 1 time control per board size but the server will be flexible enough that other venues can be added if the server ever gets popular enough that we have 40 or 50 players always on line. But they will be separate venues scheduled independently. - Don On Tue, Jun 16, 2009 at 8:08 AM, Isaac Deutsch i...@gmx.ch wrote: I'm voting for 2 time settings: One normal and one fast (so maybe 5 min and 1 min on 9x9). -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Core i7 performance in computer-go
i always buy at the low end because you get so much better of a deal. But I'd guess the i7 is as excellent at Go as it is at everything else. Łukwasz Lew wrote: Hi I have few days to buy a computer for Monte-carlo Go program. There is not enough money for a multi processor, so I have to decide between - core i7 2.66 GHz - some core2 quad both subjected to over-clocking. Have you observed that Monte-Carlo Go program is faster on core i7 than on core2 ? Lukasz PS Or have you found some cheap solutions for shared memory dual processor? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tweak to MCTS selection criterion
Another strategy to be considered is to not allow the thinking to cease until the maximum win rate and the maximum visit count agree on the same move. Obviously this requires some extra code to make sure you don't lose on time, etc. Brian Sheppard wrote: When a UCT search is completed, the usual selection criterion is choose the move that has the most trials. This is more stable than choosing the move that has the highest percentage of wins, since it is possible to have an unreliably high percentage if the number of trials is small. I have a small tweak to that criterion. Pebbles uses choose the move that has the most wins. This rule selects the same move as the conventional criterion in almost every case. The reason why Pebbles' rule is superior is revealed in the case where the moves differ. When Pebbles chooses a different move than the conventional criterion, it is because Pebbles move has more wins in fewer trials. When that happens, Pebbles move would inevitably become the move with the most trials if searching were to continue. So there is actually no downside. Of course, the upside is minor, too. For validation, Pebbles has been using both strategies on CGOS games. At present, the conventional selection strategy has won 341/498 = 68.47%. Pebbles strategy has won 415/583 = 71.18%. This isn't statistically conclusive or anything (0.7 standard deviations; we would need 4 to 8 times as many trials for strong statistical evidence). But Pebbles' strategy should be better by a small amount, and it has been, so I present it to you with confidence. Best, Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Łukasz Lew wrote: On Wed, Jun 3, 2009 at 00:56, Michael Williams michaelwilliam...@gmail.com wrote: Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). This is quite similar to epsilon trick described here: http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf in short when you calculate best UCT child you visit it max(best.visit_count * epsilon, 1) times with epsilon = 0.05 for instance It works well both for new and old nodes, but you have to keep the counter of visits. The soft way would be to recalculate best child with probability min(1, 1/(best.visit_count*epsilon)). Both variants of ET can give you some guarantees about the way the tree is explored. Łukasz I switched to this method. Thanks, Lukasz. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
I mean SSD. Michael Williams wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). Jason House wrote: That sounds like a good optimization. What did you do? Sent from my iPhone On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go
Re: [computer-go] UCT tree pruning
Jason House wrote: On Jun 2, 2009, at 6:56 PM, Michael Williams michaelwilliam...@gmail.com wrote: Two things: Firstly, I'm storing (only in RAM) the precalculated Winrate and InvSqrtVisits and keeping them updated. So my UCT formula went from Wins / Visits + sqrt(lnParentVisits / Visits) to WinRate + sqrtLnParentVisits * InvSqrtVisits; Which equations do you use for the incremental updates? Or do you just recompute the values? It's not incremental. WinRate = Wins / Visits; InvSqrtVisits = 1 / sqrt(Visits); This has a memory cost, but I don't care so much about RAM since I can send the nodes to disk. And the second thing is to store in the parent node a reference to what is likely the UCT-best child node. If the parent has been visited 100*boardspaces times, I will go directly to the likely-best child with probability 2047/2048. Anytime a proper UCT loop occurs, the likely-best reference is updated (about 90% of the time there is no change, so I think it's safe). What is a proper UCT loop? By that I meant finding the the child that maximizes the UCT formula. Jason House wrote: That sounds like a good optimization. What did you do? Sent from my iPhone On Jun 2, 2009, at 3:16 PM, Michael Williams michaelwilliam...@gmail.com wrote: Update: After concentrating on tightening the UCT loop, I've optimized myself back into needing the SDD :/ But now I should be able to get to 20B nodes in just one day. (still only doing 7x7 Go) Michael Williams wrote: Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go
Re: [computer-go] UCT tree pruning
I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
Yes, when memory is full, I save and free all leaf nodes (which is the vast majority). Nodes are loaded as needed. Don Dailey wrote: On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I've optimized my disk access to the point where I'm mostly CPU limited now, even when using a standard hard disk instead of an SSD. I can now create trees of up to about 30 billion nodes, which would take about a week. The simulation rate is continuously going down because so much time is spent in UCT loops in the huge tree. That's impressive. Are you doing things which move parts of the tree onto the disk and back when needed? I'm curious about the details! - Don Don Dailey wrote: On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch mailto:i...@gmx.ch wrote: Well, I'll take that over crashing with an out-of-memory error. :) Still, pruning seems better to me and has the same effect. ;p But is it better? I think it's not so obvious without thorough testing. Pruning throw away information that is lost forever and may need to be recalculated. Requiring more simulations does not throw out results, but results in some inefficiencies. So it's not clear to me which is better - it may even be that it depends on how much you push it. I am just guessing but I would guess that pruning is better in the short term, worse in the longer term. Imagine a search at a corespondence level, where the computer thinks for 24 hours. Which method is best there? Could you use hard disk or SSD? Using some kind of caching system, where you relegate the oldest unvisited nodes to the hard dirve. It may be that nodes you might normally prune are unlikely to get used again but if they do you still have the data.This is no good unless you can guarantee that the disk is used very infrequently - but with SSD it may be more practical. - Don -- Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Extended AMAF
Back in the days of Don's reference bot, I made some similar modifications to them and posted the results (slight improvement). The postings were around 10/28/08. Ingo Althöfer wrote: Hello, maybe this is old stuff for the insiders. In my lecture today a clever student (Hagen Riedel) brought up the following idea to extend AMAF. He counts in four ways moves on a specific square: (1) How often did player A make this move in random games which he won? (2) How often did player A make this move in random games which he lost? (3) How often did opponent B make this move in random games which A won? (4) How often did opponent B make this move in random games which A lost. Let n(1), ... n(4) be these numbers, and q(1), ..., q(4) the respective quota. Would it make sense to combine them by a linear combination, like lamda(1)*q(1) + lamda(2)*q(2), where the lamda's are appropriate positve or negative weights. Any comments, experiences, ...? Ingo. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go + code + environment
MoGo was inspired by Crazy Stone? I've never heard that before. Ian Osgood wrote: On May 23, 2009, at 3:17 AM, Joshua Shriver wrote: I know with the Chess community, it's looked down upon to use others code w/ respect to competing in tournaments. I'm curious, how is it with Go? Even more so. A decade ago, a couple of North Korean programs were alleged to have been plagiarized from the successful Chinese program Handtalk. The stigma was so strong that a decade later one of the programs, KCC Igo, was refused entry to the 2008 Computer Olympiad. From my understanding, many projects are inter-linked, and even some of the highest programs are derivatives of other engines. In the chess world that would be considered a clone and instantly banned and looked down upon. Perhaps I'm mistaken in my reading, but isn't Mogo a clusterized and highly tuned version of gnugo? Things like that made me want to make this post. As I find the Go programming community more open to sharing ideas and code than my chess world counter part. You are thinking of the cluster research program SlugGo. That developer and the GNU Go team have the friendly agreement not to both compete in the same tournament at the same time. GNU Go only participated in the 2008 US computer Go championship when SlugGo could not get its new cluster working in time to participate. MoGo itself was inspired by French compatriot Crazy Stone. Both of these programs are academic research projects which publish their research (though they don't share code as far as I know). The field of Computer Go owes them and the Indigo team a great debt for publishing their Monte Carlo tree search results. Early Go programmers Bruce Wilcox, David Fotland, and Mark Boon were also very generous to explain the internals of their programs in great detail. Will gladly stand corrected w/ Mogo if i'm wrong. Though curious to hear everyones input. -Josh ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reflections on a disaster
Cool idea. Magnus Persson wrote: Valkyria computes AMAF win rates for all moves including those that are pruned or illegal in the position. What I noticed is that in cases of critical semeais the AMAF values of moves that are for example illegal can get very high since they only get legal when you win the semeai and thus win the game Therefore Valkyria takes the AMAF values of moves that cannot be played yet, and try to find approach moves that will enable playing them and replaces the AMAF values of the approach move with the AMAF value of the illegal move if it is higher. This is a costly computation so it is only done if the position has been visited several times. Without this AMAF-hack Valkyria sometimes has a problem finding F1. It also seems to take a longer time to find F1 in all cases where does find it. I have not yet tested the effect on the playing strength from this. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 7x7 komi
What was the consensus on 7x7 komi? It was discussed back during Don's scalability study, but I couldn't find the number itself. Was it 9.0? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Libego compiling
Michael Williams wrote: Ben Shoemaker wrote: Success! I was able to build on WinXP using Scons and minGW (with gcc4.3.3). Here's what (finally) worked for me: 1. Install Python 2.6.2 http://www.python.org/ftp/python/2.6.2/python-2.6.2.msi 2. Install minGW (using TDM's installer on empty minGW directory) http://downloads.sourceforge.net/tdm-gcc/tdm-mingw-1.902.0-f1.exe ... Is there a nice installer like this anywhere for 64-bit (Windows 7)? I'm just using the 32-bit version. But something is not right: g++.exe -o example.exe ego/ego.cpp example/main.cpp -O3 -Iego -fomit-frame-pointer -ffast-math -frename-registers -march=i686 In file included from ego/ego.cpp:49: ego/fast_random.cpp: In member function 'void FastRandom::test()': ego/fast_random.cpp:76: error: 'printf' was not declared in this scope ego/fast_random.cpp: In member function 'void FastRandom::test2(uint, uint)': ego/fast_random.cpp:90: error: 'printf' was not declared in this scope In file included from example/main.cpp:27: example/uct.cpp: In member function 'std::string Stat::to_string(bool)': example/uct.cpp:82: error: 'sprintf' was not declared in this scope example/main.cpp: In function 'int main(int, char**)': example/main.cpp:51: error: 'stdout' was not declared in this scope example/main.cpp:51: error: 'setbuf' was not declared in this scope example/main.cpp:52: error: 'stderr' was not declared in this scope It's like it can't find stdio. Any ideas? Process Monitor says that it is getting BUFFER OVERFLOW when accessing that file. I don't know what that means so it may or may not be normal. But probably not. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Digital Mars
Ben Shoemaker wrote: Success! I was able to build on WinXP using Scons and minGW (with gcc4.3.3). Here's what (finally) worked for me: 1. Install Python 2.6.2 http://www.python.org/ftp/python/2.6.2/python-2.6.2.msi 2. Install minGW (using TDM's installer on empty minGW directory) http://downloads.sourceforge.net/tdm-gcc/tdm-mingw-1.902.0-f1.exe ... Is there a nice installer like this anywhere for 64-bit (Windows 7)? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
C# does. It should only take 30 bytes per node to store the information I need to have. But somehow that turns into 50 bytes. Byte alignment plus class overhead, I guess. Matthew Woodcraft wrote: Michael Williams wrote: I want to correct that last statement. With about 350M nodes currently in the tree (~30M of which fit into memory), I am averaging 0.06 disk reads per tree traversal. What makes the nodes so big? -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
It's on my list of things to improve. Michael Williams wrote: C# does. It should only take 30 bytes per node to store the information I need to have. But somehow that turns into 50 bytes. Byte alignment plus class overhead, I guess. Matthew Woodcraft wrote: Michael Williams wrote: I want to correct that last statement. With about 350M nodes currently in the tree (~30M of which fit into memory), I am averaging 0.06 disk reads per tree traversal. What makes the nodes so big? -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
I am not using rave yet. Also on list. David Fotland wrote: Are you not using rave? If you keep rave counters for each legal move in the node it should be much bigger than this. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Michael Williams Sent: Thursday, May 14, 2009 7:08 AM To: computer-go@computer-go.org Subject: Re: [computer-go] Implications of a CPU vs Memory trend on MCTS C# does. It should only take 30 bytes per node to store the information I need to have. But somehow that turns into 50 bytes. Byte alignment plus class overhead, I guess. Matthew Woodcraft wrote: Michael Williams wrote: I want to correct that last statement. With about 350M nodes currently in the tree (~30M of which fit into memory), I am averaging 0.06 disk reads per tree traversal. What makes the nodes so big? -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
Plus, they are both made out of the same stuff so one would expect them to scale at about the same rate. Mark Boon wrote: I'm a bit late reading this thread and the discussion seems to have veered from the original topic a bit. As to the CPU vs. memory discussion, it's not so clear-cut to me that CPU speeds are improving faster than memory. Twenty years ago you had CPUs in the 4-8Mhz range and around 1Mb of memory. Today both are about 1000 times higher. CPU speeds are not necessarily only represented by hertz of course, but both CPU and memory seemed to have progressed with roughly the same speed. The thing is, they don't progress evenly. So maybe at the moment CPUs are going a bit faster than memory. But this could be temporary, not necessarily a sustainable trend. Also, CPU speeds of a single processor has stalled for a few years now. Using multiple CPUs or cores you get easy doubles by going to two and four. But it also gets more and more expensive. And doubling the CPUs doesn't double the power really. A bit over ten years ago we made a tsume-go program using PN search. There we also had problems keeping the tree in memory, so we designed a tree-structure that would automatically swap part of the tree out to disk. But after that there was a period that this code seemed to have become superfluous, as memory suddenly became abundant. If we now have a memory shortage with respect to CPU power it's quite possible this is something cyclical. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
I want to correct that last statement. With about 350M nodes currently in the tree (~30M of which fit into memory), I am averaging 0.06 disk reads per tree traversal. Must less than several. In hindsight, several wasn't a good guess. The 0.06 number will get a little worse as the tree gets bigger, but probably not much. Michael Williams wrote: Those numbers are the average after the tree has grown to 1B nodes. I'm sure the cache hates me. Each tree traversal will likely make several reads from random locations in a 50 GB file. Don Dailey wrote: So you are saying that use disk memory for this? This could be pretty deceiving if most of your reads and writes are cached.What happens when your tree gets much bigger than available memory? - Don On Tue, May 12, 2009 at 1:18 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: In my system, I can retrieve the children of any node at a rate of about 100k nodes/sec. And I can save nodes at a rate of over 1M nodes/sec (this is much faster because in my implementation, the operation is sequential on disk). Those numbers are from 6x6 testing. Don Dailey wrote: This is probably a good solution. I don't believe the memory has to be very fast at all because even with light playouts you are doing a LOT of computation between memory accesses. All of this must be tested of course. In fact I was considering if disk memory could not be utilized as a kind of cache. The secret would be to store complete trees in disk memory, trees that are not likely to be utilized but can be utilized in a pinch. The tree store and retrieved must outweigh by a large factor the amount of time spent creating the tree in the first place in order for this to pay off. My guess is that this is impractical, but it's fun to think about how it might be done. I'm not sure how to do it without having a caching nightmare. - Don On Tue, May 12, 2009 at 12:41 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite.What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes and adjustments. I seem to be able to solve (there are lots of definitions) 6x6 Go in that when I use a komi of 3.5, it is unable to find a winning line for white and when I use 4.5, it is unable to find a winning line for black. ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Fuego project site
The Projects link (http://fuego.sourceforge.net/projects.html) on the Fuego site (http://fuego.sourceforge.net/) is broken. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite.What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes and adjustments. I seem to be able to solve (there are lots of definitions) 6x6 Go in that when I use a komi of 3.5, it is unable to find a winning line for white and when I use 4.5, it is unable to find a winning line for black. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
It depends on how you use it and how much you pay for it. If you get a high-end Intel SSD, you can treat it however you like. But I can't afford that. I got a cheap SSD and so I had shape my algorithm around which kind of disk operations it likes and which ones it doesn't. steve uurtamo wrote: is the ssd fast enough to be practical? s. On Tue, May 12, 2009 at 12:41 PM, Michael Williams michaelwilliam...@gmail.com wrote: Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite.What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes and adjustments. I seem to be able to solve (there are lots of definitions) 6x6 Go in that when I use a komi of 3.5, it is unable to find a winning line for white and when I use 4.5, it is unable to find a winning line for black. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
Those numbers are the average after the tree has grown to 1B nodes. I'm sure the cache hates me. Each tree traversal will likely make several reads from random locations in a 50 GB file. Don Dailey wrote: So you are saying that use disk memory for this? This could be pretty deceiving if most of your reads and writes are cached.What happens when your tree gets much bigger than available memory? - Don On Tue, May 12, 2009 at 1:18 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: In my system, I can retrieve the children of any node at a rate of about 100k nodes/sec. And I can save nodes at a rate of over 1M nodes/sec (this is much faster because in my implementation, the operation is sequential on disk). Those numbers are from 6x6 testing. Don Dailey wrote: This is probably a good solution. I don't believe the memory has to be very fast at all because even with light playouts you are doing a LOT of computation between memory accesses. All of this must be tested of course. In fact I was considering if disk memory could not be utilized as a kind of cache. The secret would be to store complete trees in disk memory, trees that are not likely to be utilized but can be utilized in a pinch. The tree store and retrieved must outweigh by a large factor the amount of time spent creating the tree in the first place in order for this to pay off. My guess is that this is impractical, but it's fun to think about how it might be done. I'm not sure how to do it without having a caching nightmare. - Don On Tue, May 12, 2009 at 12:41 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite.What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes and adjustments. I seem to be able to solve (there are lots of definitions) 6x6 Go in that when I use a komi of 3.5, it is unable to find a winning line for white and when I use 4.5, it is unable to find a winning line for black. ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
That's basically what I'm doing. Except that there is no depth limit and only the parts of the tree that you need get loaded back into memory. It's not a playing engine yet so it can't build the tree as it plays games. Currently it just ponders the empty board. terry mcintyre wrote: Are we approaching a point where it would be practical to precompute the opening tree to some depth, cache the results on SSD, and incrementally improve that knowledge based upon subsequent games? Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 *From:* Michael Williams michaelwilliam...@gmail.com *To:* computer-go computer-go@computer-go.org *Sent:* Tuesday, May 12, 2009 10:18:28 AM *Subject:* Re: [computer-go] Implications of a CPU vs Memory trend on MCTS In my system, I can retrieve the children of any node at a rate of about 100k nodes/sec. And I can save nodes at a rate of over 1M nodes/sec (this is much faster because in my implementation, the operation is sequential on disk). Those numbers are from 6x6 testing. Don Dailey wrote: This is probably a good solution. I don't believe the memory has to be very fast at all because even with light playouts you are doing a LOT of computation between memory accesses. All of this must be tested of course.In fact I was considering if disk memory could not be utilized as a kind of cache. The secret would be to store complete trees in disk memory, trees that are not likely to be utilized but can be utilized in a pinch. The tree store and retrieved must outweigh by a large factor the amount of time spent creating the tree in the first place in order for this to pay off. My guess is that this is impractical, but it's fun to think about how it might be done. I'm not sure how to do it without having a caching nightmare. - Don On Tue, May 12, 2009 at 12:41 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite.What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes and adjustments. I seem to be able to solve (there are lots of definitions) 6x6 Go in that when I use a komi of 3.5, it is unable to find a winning line for white and when I use 4.5, it is unable to find a winning line for black. ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Implications of a CPU vs Memory trend on MCTS
It often gets interrupted by me so that I can change some code, etc. And I often break backwards compatibility, so I have to delete the file and start from scratch. In the past it has run for up to around 24 hours, but that was an older, slower version. I just kicked-off a 7x7 run. I expect it will reach it's current capacity of around 2B nodes in about 12 hours. terry mcintyre wrote: How long has it been pondering? Terry McIntyre terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 *From:* Michael Williams michaelwilliam...@gmail.com *To:* computer-go computer-go@computer-go.org *Sent:* Tuesday, May 12, 2009 1:09:41 PM *Subject:* Re: [computer-go] Implications of a CPU vs Memory trend on MCTS That's basically what I'm doing. Except that there is no depth limit and only the parts of the tree that you need get loaded back into memory. It's not a playing engine yet so it can't build the tree as it plays games. Currently it just ponders the empty board. terry mcintyre wrote: Are we approaching a point where it would be practical to precompute the opening tree to some depth, cache the results on SSD, and incrementally improve that knowledge based upon subsequent games? Terry McIntyre terrymcint...@yahoo.com mailto:terrymcint...@yahoo.com On general principles, when we are looking for a solution of a social problem, we must expect to reach conclusions quite opposed to the usual opinions on the subject; otherwise it would be no problem. We must expect to have to attack, not what is commonly regarded as objectionable, but what is commonly regarded as entirely proper and normal. – John Beverley Robinson, 1897 *From:* Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com *To:* computer-go computer-go@computer-go.org mailto:computer-go@computer-go.org *Sent:* Tuesday, May 12, 2009 10:18:28 AM *Subject:* Re: [computer-go] Implications of a CPU vs Memory trend on MCTS In my system, I can retrieve the children of any node at a rate of about 100k nodes/sec. And I can save nodes at a rate of over 1M nodes/sec (this is much faster because in my implementation, the operation is sequential on disk). Those numbers are from 6x6 testing. Don Dailey wrote: This is probably a good solution. I don't believe the memory has to be very fast at all because even with light playouts you are doing a LOT of computation between memory accesses. All of this must be tested of course.In fact I was considering if disk memory could not be utilized as a kind of cache. The secret would be to store complete trees in disk memory, trees that are not likely to be utilized but can be utilized in a pinch. The tree store and retrieved must outweigh by a large factor the amount of time spent creating the tree in the first place in order for this to pay off. My guess is that this is impractical, but it's fun to think about how it might be done. I'm not sure how to do it without having a caching nightmare. - Don On Tue, May 12, 2009 at 12:41 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: Don Dailey wrote: On Tue, May 12, 2009 at 12:16 PM, Michael Williams michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com mailto:michaelwilliam...@gmail.com wrote: I have a trick ;) I am currently creating MCTS trees of over a billion nodes on my 4GB machine. Ok, I'll bite.What is your solution? I use an SSD. There are many details, of course. But it's still in the works and I'm still making lots of changes
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
Where does your 99% figure come from? Dave Dyer wrote: Storing an opening book for the first 10 moves requires 331477745148242200 nodes. Even with some reduction for symmetry, I don't see that much memory becoming available anytime soon, and you still have to evaluate them somehow. Actually storing a tree, except for extremely limited special cases, is not even conceptually possible, and doesn't save much time. Consider that if you store the tree you saw at the previous move, by the time you get to use the stored tree 99% of it is useless because your opponent chose his move. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Implications of a CPU vs Memory trend on MCTS
You have made the assumption that the move that your opponent selected was on average explored equally as much as all of the other moves. That seems a bit pessimistic. One would expect that the opponent selected a strong move and one would also expect that your tree explored that strong move more than it did other moves. I'm not saying keeping the tree is a huge benefit. I'm just saying that I don't think your 99% number is fair. Dave Dyer wrote: At 02:13 PM 5/12/2009, Michael Williams wrote: Where does your 99% figure come from? 1/361 1% by endgame there are still easily 100 empty spaces on the board. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Mogo on supercomputer
When Mogo runs on the supercomputer with long-ish time limits, how big does the search tree get? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Fuego save uct tree as sgf
Does anyone know how to interpret the data at each node of a SGF created by the Fuego command uct_savetree? It looks like this: MoveCount 35955 PosCount 35963 Mean 0.50 Rave: D4 0.50 (31635.70) B2 0.50 (27049.71) C2 0.50 (28288.84) D2 0.50 (29368.09) E2 0.50 (27690.41) F2 0.50 (27246.91) G2 0.50 (28080.39) H2 0.50 (27464.24) ... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fuego Binary for Intel Mac
The Fuego documentation doesn't seem to contain any information about command-line options (if there are any). Ian Osgood wrote: On May 8, 2009, at 11:57 AM, Ech Naton wrote: Hello I made a binary of Fuego 0.3.2 for Intel Mac. It is build on OS X 10.4. So I don't know if it runs also under 10.5. But since it is not that easy to build, maybe somebody is interested in a ready executable. Simply unzip the files in a directory and call fuego032 from your GTP client. There is no need for library installation or root rights. Regards Patrick fuego.zip Thank you very much! Works fine under Sente Goban (tested on OS X 10.4). 1. Preferences Players New Player Program (GTP) Give path to fuego032, and any arguments for setting number of threads and such. (Can you set any of the GTP settings from the command line?) (You can create multiple instances with different settings if you wish.) There is no interface for editing the name (Anonymous), so quit and edit the prefs by hand. a. quit and edit ~/Library/Preferences/ch.sente.Goban.plist b. edit Players (class GobanGTPPlayer) object name c. change string to Fuego 0.3.2 d. save and restart Goban 2. New Info Rules and Players You can change the players at the bottom as well as the board size, handicap, and komi. (Rules are stuck on Japanese and time controls are disabled for some reason) These settings are retained for subsequent games. Ian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Fuego technical report
What is the meaning of the value returned by uct_score? Martin Mueller wrote: How do you set the number of threads that you want Fuego to use? E.g. for 4 threads uct_param_search number_threads 4 This can go e.g. in a config file, or you can set it in GoGui in the Uct Param Search dialog. You could also play with pondering on, and reuse the subtree from the previous search. Also, if you have memory, you can increase the node limit. uct_param_player ponder 1 uct_param_player reuse_subtree 1 uct_param_search max_nodes 1000 Does the windows version support multiple threads? It should. Please test and report. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Fuego technical report
Once again, I found it right after sending that. Copied here if anyone else cares: Score position with all stones safe and only simple eyes. This is a fast scoring function (e.g. suitable for Monte-Carlo), that can be used if playing continues as long as there are legal moves which do not fill the player's single point eyes. All stones are considered safe, all empty points must be single empty points surrounded by one color. The score is counted using 1 point for all black stones or empty points with only black stones adjacent, and -1 point for white stones or empty points with only white stones adjacent. Komi of board is taken into account. Michael Williams wrote: What is the meaning of the value returned by uct_score? Martin Mueller wrote: How do you set the number of threads that you want Fuego to use? E.g. for 4 threads uct_param_search number_threads 4 This can go e.g. in a config file, or you can set it in GoGui in the Uct Param Search dialog. You could also play with pondering on, and reuse the subtree from the previous search. Also, if you have memory, you can increase the node limit. uct_param_player ponder 1 uct_param_player reuse_subtree 1 uct_param_search max_nodes 1000 Does the windows version support multiple threads? It should. Please test and report. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fuego technical report
I found an error in the documentation: === void GoUctCommands::CmdParamPlayer ( GtpCommand cmd ) === Get and set GoUctPlayer parameters. This command is compatible with the GoGui analyze command type param. Parameters: auto_param See GoUctPlayer::AutoParam early_pass See GoUctPlayer::EarlyPass ignore_clock See GoUctPlayer::IgnoreClock reuse_subtree See GoUctPlayer::ReuseSubtree use_root_filter See GoUctPlayer::UseRootFilter max_games See GoUctPlayer::MaxGames resign_min_games See GoUctPlayer::ResignMinGames resign_threshold See GoUctPlayer::ResignThreshold search_mode playout|uct|one_ply See GoUctPlayer::SearchMode === The last line should read: search_mode playout_policy|uct|one_ply See GoUctPlayer::SearchMode Martin Mueller wrote: Our technical report describing the Fuego framework is now available on http://www.cs.ualberta.ca/research/techreports/2009/TR09-08.php I will probably make at least one more revision, so all feedback and suggestions are welcome. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Fuego on a small board
After starting Fuego and issuing these commands: boardsize 4 komi 1.5 book_clear go_param timelimit 600 uct_param_search number_threads 1 go_param_rules ko_rule pos_superko uct_param_search max_nodes 3000 reg_genmove_toplay I get this result: SgRandom::SetSeed: 1241728335 SgDefaultTimeControl: timeLeft=600/1 remaining=1 timeMove=600 SgUctSearch: move cannot change anymore Count 8.64857e+06 Nodes 11566693 Time 3.9e+02 GameLen19.8 dev=nan min=7.0 max=47.0 InTree 19.6 dev=nan min=0.0 max=38.0 Aborted0% Games/s22214.2 Value 0.68 Sequence B2 C3 B3 C2 C4 B1 D3 A2 D2 C1 A4 PASS D4 PASS PASS TimeRootFilter 0.00 = B2 For the same commands but with a second thread: boardsize 4 komi 1.5 book_clear go_param timelimit 600 uct_param_search number_threads 2 go_param_rules ko_rule pos_superko uct_param_search max_nodes 3000 reg_genmove_toplay I get this result: SgRandom::SetSeed: 1241729082 SgDefaultTimeControl: timeLeft=600/1 remaining=1 timeMove=600 [0] SgUctSearch: move cannot change anymore [1] SgUctSearch: move cannot change anymore Count 1.03816e+07 Nodes 17472903 Time 5e+02 GameLen20.9 dev=nan min=7.0 max=48.0 InTree 20.5 dev=nan min=0.0 max=42.0 Aborted0% Games/s20593.9 Value 0.21 Sequence B2 C3 C2 B3 B4 A2 D3 D2 D1 C4 B1 A3 A1 A4 D2 PASS PASS TimeRootFilter 0.00 = B2 Using a second thread has negatively affected the evaluation of the position. The position is won for black. Also, I think the documentation could be improved by indicating what the defaults are for various parameters. For instance, I don't know whether the statement above that sets the ko rule was necessary or if it already defaults to pos_superko. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fuego technical report
How do you set the number of threads that you want Fuego to use? Does the windows version support multiple threads? Michael Williams wrote: Very nice. I do have one suggestion for Fuego. Make use of the ability to filter certain root moves out of the UCT tree to remove symmetrically equivalent moves. Or if it is not cost-prohibitive, throughout the tree. Martin Mueller wrote: Our technical report describing the Fuego framework is now available on http://www.cs.ualberta.ca/research/techreports/2009/TR09-08.php I will probably make at least one more revision, so all feedback and suggestions are welcome. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Fuego technical report
Thanks. Yes, it works in Windows. Martin Mueller wrote: How do you set the number of threads that you want Fuego to use? E.g. for 4 threads uct_param_search number_threads 4 This can go e.g. in a config file, or you can set it in GoGui in the Uct Param Search dialog. You could also play with pondering on, and reuse the subtree from the previous search. Also, if you have memory, you can increase the node limit. uct_param_player ponder 1 uct_param_player reuse_subtree 1 uct_param_search max_nodes 1000 Does the windows version support multiple threads? It should. Please test and report. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Fuego technical report
Is there a way to get Fuego to do a certain number of playouts per turn? uct_param_search number_playouts N looked promising, but that is something different I think. Martin Mueller wrote: How do you set the number of threads that you want Fuego to use? E.g. for 4 threads uct_param_search number_threads 4 This can go e.g. in a config file, or you can set it in GoGui in the Uct Param Search dialog. You could also play with pondering on, and reuse the subtree from the previous search. Also, if you have memory, you can increase the node limit. uct_param_player ponder 1 uct_param_player reuse_subtree 1 uct_param_search max_nodes 1000 Does the windows version support multiple threads? It should. Please test and report. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Fuego technical report
I found it right after sending that (of course): uct_param_player max_games N Michael Williams wrote: Is there a way to get Fuego to do a certain number of playouts per turn? uct_param_search number_playouts N looked promising, but that is something different I think. Martin Mueller wrote: How do you set the number of threads that you want Fuego to use? E.g. for 4 threads uct_param_search number_threads 4 This can go e.g. in a config file, or you can set it in GoGui in the Uct Param Search dialog. You could also play with pondering on, and reuse the subtree from the previous search. Also, if you have memory, you can increase the node limit. uct_param_player ponder 1 uct_param_player reuse_subtree 1 uct_param_search max_nodes 1000 Does the windows version support multiple threads? It should. Please test and report. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fuego technical report
Very nice. I do have one suggestion for Fuego. Make use of the ability to filter certain root moves out of the UCT tree to remove symmetrically equivalent moves. Or if it is not cost-prohibitive, throughout the tree. Martin Mueller wrote: Our technical report describing the Fuego framework is now available on http://www.cs.ualberta.ca/research/techreports/2009/TR09-08.php I will probably make at least one more revision, so all feedback and suggestions are welcome. Thank you Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Monte Carlo on GPU
Michael Williams wrote: See the April 30 2009 posting: http://www.tobiaspreis.de/ The CUDA SDK also comes with a sample called Monte-Carlo Option Pricing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Monte Carlo on GPU
See the April 30 2009 posting: http://www.tobiaspreis.de/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
I wish I was smart :(
David Silver wrote:
Hi Remi,
I understood this. What I find strange is that using -1/1 should be
equivalent to using 0/1, but your algorithm behaves differently: it
ignores lost games with 0/1, and uses them with -1/1.
Imagine you add a big constant to z. One million, say. This does not
change the problem. You get either 100 or 101 as outcome of a
playout. But then, your estimate of the gradient becomes complete noise.
So maybe using -1/1 is better than 0/1 ? Since your algorithm depends
so much on the definition of the reward, there must be an optimal way
to set the reward. Or there must a better way to define an algorithm
that would not depend on an offset in the reward.
There is still something wrong that I don't understand. There may be a
way to quantify the amount of noise in the unbiased gradient estimate,
and it would depend on the average reward. Probably setting the
average reward to zero is what would minimize noise in the gradient
estimate. This is just an intuitive guess.
Okay, now I understand your point :-) It's a good question - and I think
you're right. In REINFORCE any baseline can be subtracted from the
reward, without affecting the expected gradient, but possibly reducing
its variance. The baseline leading to the best estimate is indeed the
average reward. So it should be the case that {-1,+1} would estimate
the gradient g more efficiently than {0,1}, assuming that we see similar
numbers of black wins as white wins across the training set.
So to answer your question, we can safely modify the algorithm to use
(z-b) instead of z, where b is the average reward. This would then make
the {0,1} and {-1,+1} cases equivalent (with appropriate scaling of
step-size). I don't think this would have affected the results we
presented (because all of the learning algorithms converged anyway, at
least approximately, during training) but it could be an important
modification for larger boards.
-Dave
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
David Silver wrote: Hi Michael, But one thing confuses me: You are using the value from Fuego's 10k simulations as an approximation of the actual value of the position. But isn't the actual value of the position either a win or a loss? On such small boards, can't you assume that Fuego is able to correctly determin who is winning and round it's evaluation to the nearest win/loss? i.e. if it evaluates the position to 0.674, that gets rounded to 1. If such an assumption about Fuego's ability to read the position on a small board is valid, then it should improve the results of your balanced simulation strategy, right? Or am I missing something? It's true that 5x5 Go is solved, so in principle we could have used the true minimax values. However we chose to use an approach that can scale to larger boards, which means that we should treat the expert evaluations as approximate. And in fact Fuego was not always accurate on 6x6 boards, as we used only 10k simulations in our training set. Also, I think it really helps to have soft rather than hard expert evaluations. We want a simulation policy that helps differentiate e.g. a 90% winning position from an 85% winning position. Rounding all the expert evaluations to 0 or 1 would lose much of this advantage. -Dave By this argument (your last paragraph), you need to do some magical number of simulations for the training data. Not enough simulations and you have too much noise. And infinite simulations gives you hard 0 or 1 results. But I can't argue with your results. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Justification for c==0
I will ignore Magnus's comments about AMAF while I respond directly to your comments. If you do one or two simulations from a leaf node and they happen to result in losses, you would never simulate that node again? And never expand it into it's child nodes? It is very possible that the winning move will result in a playout loss the first time it is tried. Brian Sheppard wrote: The Mogo team has published that their UCT exploration coefficient is zero, and further state that this is the optimal setting for Mogo. Other studies have confirmed that finding. Yet, the suspicion persists that this result is somehow related to Mogo's structure, perhaps because it runs massively parallel or because of some twist in its internals. This post provides theoretical and heuristic justification for c==0. First the theoretical: Theorem: In a finite game tree with no cycles, with binary rewards, the UCT algorithm with c==0 converges (in the absence of computational limitations) to the game theoretic optimal policy. The proof is by induction on the depth of the tree. The base case is one ply before a terminal state. In the base case, UCT will eventually try a winning move if one exists. Thereafter, UCT will repeat that move indefinitely because there is no exploration. It follows that the UCT value of the base case will converge to the game theoretic value for both winning and losing states. For the induction step, assume that we have N 1 plies remaining. Each trial produces a node at depth N-1 at most. (Note: for this to be true, we have to count ply depth according to the longest path to terminal node.) With sufficient numbers of trials, each of those nodes will converge to the game-theoretic value. This implies that if there is a winning play, it will eventually be discovered. Note that the binary rewards condition is required. Without it, the UCT policy cannot know that winning is the best possible outcome, so it would have to explore. The point of this theorem is that Mogo's is safe; its exploration policy does not prevent it from eventually playing perfectly. Now, there is no implication in this proof that the c==0 policy is computationally optimal, or even efficient. But we do have Mogo's experimental result, so it is worthwhile to speculate whether c==0 should be optimal. Some heuristic reasoning follows. If UCT has to choose between trying a move that wins 55% and a move that wins 54%, then why *shouldn't* it try the move that wins more frequently? What we are trying to do (at an internal node) is to prove that our opponent's last play was losing, and we would do this most efficiently by sampling the move that has the highest success. Another angle: at the root of the tree, we will choose the move that has the largest number of trials. We would like that to be a winning move. From the theorem above, we know that the value of the moves will converge to either 0 or 1. By spending more effort on the move with higher reward, we provide the maximum confirmation of the quality of the chosen move. If the reward of that move starts to drift downward, then it is good that we spent the effort. Another angle: we can spend time on either move A or move B, with A higher. If A is winning, then it is a waste of time to search B even one time. So in that case c==0 is optimal. The harder case is where A is losing: we have spent more time on A and it has a higher win rate, so we would choose move A unless something changes. There are two strategies: invest in A to prove that it is not as good as it looks, or invest in B to prove that it is better than it seems. With only two move choices, these alternatives are probably about equal. But what if we had hundreds of alternatives? We would have a hard time guessing the winning play. So even when move A is losing we might be better off investing effort to disprove it, which would allow an alternative to rise. One more thought: Suppose that move A wins 56 out of 100 trials, and move B wins 5 out of 9. Which represents better evidence of superiority? Move A is more standard deviations over 50%. Does that suggest a new exploration policy? OK, so you don't have to worry if you set c==0. It might even be best. Just a note: in very preliminary experiments, c==0 is not best for Pebbles. If longer experiments confirm that, I presume it is because Pebbles runs on a very slow computer and searches only small trees. So your mileage may vary. But if c==0 tests well, then there is no reason not to use it. Best, Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
Finally! I guess you can add this technique to your list, Lukasz. David Silver wrote: Hi everyone, Please find attached my ICML paper with Gerry Tesauro on automatically learning a simulation policy for Monte-Carlo Go. Our preliminary results show a 200+ Elo improvement over previous approaches, although our experiments were restricted to simple Monte-Carlo search with no tree on small boards. Abstract In this paper we introduce the first algorithms for efficiently learning a simulation policy for Monte-Carlo search. Our main idea is to optimise the balance of a simulation policy, so that an accurate spread of simulation outcomes is maintained, rather than optimising the direct strength of the simulation policy. We develop two algorithms for balancing a simulation policy by gradient descent. The first algorithm optimises the balance of complete simulations, using a policy gradient algorithm; whereas the second algorithm optimises the balance over every two steps of simulation. We compare our algorithms to reinforcement learning and supervised learning algorithms for maximising the strength of the simulation policy. We test each algorithm in the domain of 5x5 and 6x6 Computer Go, using a softmax policy that is parameterised by weights for a hundred simple patterns. When used in a simple Monte-Carlo search, the policies learnt by simulation balancing achieved significantly better performance, with half the mean squared error of a uniform random policy, and equal overall performance to a sophisticated Go engine. -Dave ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
My favorite part: One natural idea is to use the learned simulation policy in Monte-Carlo search, and generate new deep search values, in an iterative cycle. But one thing confuses me: You are using the value from Fuego's 10k simulations as an approximation of the actual value of the position. But isn't the actual value of the position either a win or a loss? On such small boards, can't you assume that Fuego is able to correctly determin who is winning and round it's evaluation to the nearest win/loss? i.e. if it evaluates the position to 0.674, that gets rounded to 1. If such an assumption about Fuego's ability to read the position on a small board is valid, then it should improve the results of your balanced simulation strategy, right? Or am I missing something? David Silver wrote: Hi everyone, Please find attached my ICML paper with Gerry Tesauro on automatically learning a simulation policy for Monte-Carlo Go. Our preliminary results show a 200+ Elo improvement over previous approaches, although our experiments were restricted to simple Monte-Carlo search with no tree on small boards. Abstract In this paper we introduce the first algorithms for efficiently learning a simulation policy for Monte-Carlo search. Our main idea is to optimise the balance of a simulation policy, so that an accurate spread of simulation outcomes is maintained, rather than optimising the direct strength of the simulation policy. We develop two algorithms for balancing a simulation policy by gradient descent. The first algorithm optimises the balance of complete simulations, using a policy gradient algorithm; whereas the second algorithm optimises the balance over every two steps of simulation. We compare our algorithms to reinforcement learning and supervised learning algorithms for maximising the strength of the simulation policy. We test each algorithm in the domain of 5x5 and 6x6 Computer Go, using a softmax policy that is parameterised by weights for a hundred simple patterns. When used in a simple Monte-Carlo search, the policies learnt by simulation balancing achieved significantly better performance, with half the mean squared error of a uniform random policy, and equal overall performance to a sophisticated Go engine. -Dave ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Digital Mars
According to my math, that comes out to around 205 cycles per playout move. Pretty damn good, I'd say. Łukasz Lew wrote: On Fri, Apr 24, 2009 at 01:52, Łukasz Lew lukasz@gmail.com wrote: I get g++-4.1 35 kpps/GHz g++-4.2 45 kpps/GHz g++-4.3 40 kpps/GHz I'm happy it's quite consistent on core2 I'm curious about 4.4 as well. g++-4.4 45 kpps/GHz package gcc-snapshot on ubuntu $ /usr/lib/gcc-snapshot/bin/g++ --version g++ (Ubuntu 20081024-0ubuntu1) 4.4.0 20081024 (experimental) [trunk revision 141342] so quite old. Lukasz Lukasz PS On Fri, Apr 24, 2009 at 01:29, Adrian Grajdeanu adria...@cox.net wrote: I have two benchmarks: On an: Intel(R) Core(TM)2 CPU T7200 @ 2.00GHz stepping 06 g++ --version g++ (GCC) 4.1.2 20070925 (Red Hat 4.1.2-33) I had to modify SConstruct to refer to the default g++, not g++.4.2 and had to remove -march=native = Benchmarking, please wait ... = 20 playouts in 2.72759 seconds 73.3249 kpps 36.5657 kpps/GHz (clock independent) 105316/94359 (black wins / white wins) = 20 playouts in 2.73858 seconds 73.0304 kpps 36.4108 kpps/GHz (clock independent) 104924/94746 (black wins / white wins) = 20 playouts in 2.72858 seconds 73.2981 kpps 36.5291 kpps/GHz (clock independent) 105097/94582 (black wins / white wins) = 20 playouts in 2.76258 seconds 72.3961 kpps 36.1141 kpps/GHz (clock independent) 105139/94547 (black wins / white wins) = 20 playouts in 2.74358 seconds 72.8974 kpps 36.3124 kpps/GHz (clock independent) 104896/94794 (black wins / white wins) = Try 'help' on an: Intel(R) Core(TM)2 Quad CPUQ9650 @ 3.00GHz stepping 0a g++ --version g++ (GCC) 4.3.0 20080428 (Red Hat 4.3.0-8) (with -march=native flag) = Benchmarking, please wait ... = 20 playouts in 1.65575 seconds 120.791 kpps 40.2566 kpps/GHz (clock independent) 105316/94359 (black wins / white wins) = 20 playouts in 1.65275 seconds 121.011 kpps 40.3069 kpps/GHz (clock independent) 104924/94746 (black wins / white wins) = 20 playouts in 1.65375 seconds 120.937 kpps 40.2789 kpps/GHz (clock independent) 105097/94582 (black wins / white wins) = 20 playouts in 1.65475 seconds 120.864 kpps 40.2917 kpps/GHz (clock independent) 105139/94547 (black wins / white wins) = 20 playouts in 1.65175 seconds 121.084 kpps 40.3084 kpps/GHz (clock independent) 104896/94794 (black wins / white wins) = Try 'help' I'd be curious g++ 4.4 what gives? Cheers, Adrian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Digital Mars
I do have a core2, but it complained about that switch:
ego/ego.cpp:1: error: bad value (core2) for -march= switch
ego/ego.cpp:1: error: bad value (core2) for -mtune= switch
example/main.cpp:1: error: bad value (core2) for -march= switch
example/main.cpp:1: error: bad value (core2) for -mtune= switch
When using i686, it did not complain, and I get these results:
23.0972 kpps/GHz
Łukasz Lew wrote:
2009/4/22 Michael Williams michaelwilliam...@gmail.com:
This worked for me:
C:\Libego\lukaszlew-libego-476a46885f80e1f4d83494bb632398b3974e901bg++ -o
engine.exe ego/ego.cpp example/main.cpp -O3 -Iego -fomit-frame-pointer
-ffast-math -frename-registers
(I removed the -march switch)
22.5101 kpps/GHz
No too much :)
Can you try -march=i686 and -march=core2 (if you have core2) ?
And I was able to create a DLL like this:
C:\Libego\lukaszlew-libego-476a46885f80e1f4d83494bb632398b3974e901bg++
-shared -o libego.dll ego/eg
o.cpp exported.cpp -O3 -Iego -fomit-frame-pointer -ffast-math
-frename-registers
46274.8727441 pps
SUCCESS! Thanks for everyone's help.
Here are the contents of exported.cpp:
This is almost the same as Benchmark::do_playout in benchmark.cpp
#include ego/ego.h
__declspec(dllexport) void DoPlayouts(int playout_cnt, int * blackWins, int
* whiteWins)
{
SimplePolicy policy;
Board board [1];
Board mc_board [1];
PlayoutSimplePolicy playout(policy, mc_board);
for (int i = 0; i != playout_cnt; i++) {
mc_board-load(board);
playout_status_t status = playout.run ();
if (status != too_long)
{
int score = mc_board - score ();
if (score 0)
{
(*blackWins)++;
}
else
{
(*whiteWins)++;
}
}
}
}
Łukasz Lew wrote:
Please download newest version, I made some ifdefWIN 32 ... to aid
mingw porting.
http://github.com/lukaszlew/libego/zipball/master
Under linux I can cross compile to windows binary with a following command
$ i586-mingw32msvc-g++ -o engine.exe ego/ego.cpp example/main.cpp -O3
-march=native -Iego -fomit-frame-pointer -ffast-math
-frename-registers
It might just work :)
FYI
$ i586-mingw32msvc-g++ --version
i586-mingw32msvc-g++ (GCC) 4.2.1-sjlj (mingw32-2)
And the performance I get is around 32 kpps/GHz
Lukasz
2009/4/22 Michael Williams michaelwilliam...@gmail.com:
Ok, I have Mingw installed now. That sounds like the way to go. But I
still don't know how to compile it :/
According to the SConstruct file, I should be doing something like this
to
build, but it complains:
C:\Libego g++ /Fobuild\ego\dbg\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3
-Wall
-Wextra -Wswitch-enum -fno-inline /nologo /Iego
g++: /Fobuild\ego\dbg\ego.obj: No such file or directory
g++: /c: No such file or directory
g++: /nologo: No such file or directory
g++: /Iego: No such file or directory
In file included from ego\ego.h:27,
from ego\ego.cpp:47:
ego\gtp.h:73: warning: `class Gtp' has virtual functions but non-virtual
destructor
In file included from ego\ego.cpp:54:
ego\player.cpp: In constructor `Player::Player()':
ego\player.cpp:27: warning: converting of negative value `-0x1'
to
`uint'
In file included from ego\ego.cpp:55:
ego\color.cpp: In constructor `Color::Color()':
ego\color.cpp:27: warning: converting of negative value `-0x1' to
`uint'
I also tried the build command for the optimized version:
C:\Libego g++ /Fobuild\ego\opt\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3
-Wall
-Wextra -Wswitch-enum -O3 -march=native -fomit-frame-pointer -ffast-math
-frename-registers /nologo /Iego
g++: /Fobuild\ego\opt\ego.obj: No such file or directory
g++: /c: No such file or directory
g++: /nologo: No such file or directory
g++: /Iego: No such file or directory
ego\ego.cpp:1: error: bad value (native) for -march= switch
ego\ego.cpp:1: error: bad value (native) for -mtune= switch
Sorry for my ignorance.
Łukasz Lew wrote:
2009/4/21 Łukasz Lew lukasz@gmail.com:
mingw rules!
I compiled libego with it and got a decent 32kpps / GHz ( native g++
was 44kpps / GHz)
I used wine to run resulting exe on linux:)
Lukasz
2009/4/21 Don Dailey dailey@gmail.com:
I use mingw to produce cros platform executables. I can build
executables
for linux, win32 and win64, which for my chess program is a must since
it's
64 bit.
- Don
On Tue, Apr 21, 2009 at 5:33 AM, Łukasz Lew lukasz@gmail.com
wrote:
On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote:
I forgot about cygwin indeed. It is a good idea.
But can you ran the binary on a system without cygwin?
We can run the binary on a system without cygwin if we provide
cygwin1.dll.
That is great.
Another good idea is mingw.
BTW
I would like to recommend stackoverflow.com for programming
questions.
I asked this question there
http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw
and got few good answers within a minute.
Lukasz
___
computer-go mailing list
computer-go
Re: [computer-go] Digital Mars
After I used a better MinGW build, with a newer gcc (the one Ben suggested), I
get must better results with no compiler warnings:
40.0609 kpps/GHz
Lukasz, the march options of native, i686 and core2 all worked and came out to
similar results with i686 being slightly faster for me.
Łukasz Lew wrote:
2009/4/22 Michael Williams michaelwilliam...@gmail.com:
This worked for me:
C:\Libego\lukaszlew-libego-476a46885f80e1f4d83494bb632398b3974e901bg++ -o
engine.exe ego/ego.cpp example/main.cpp -O3 -Iego -fomit-frame-pointer
-ffast-math -frename-registers
(I removed the -march switch)
22.5101 kpps/GHz
No too much :)
Can you try -march=i686 and -march=core2 (if you have core2) ?
And I was able to create a DLL like this:
C:\Libego\lukaszlew-libego-476a46885f80e1f4d83494bb632398b3974e901bg++
-shared -o libego.dll ego/eg
o.cpp exported.cpp -O3 -Iego -fomit-frame-pointer -ffast-math
-frename-registers
46274.8727441 pps
SUCCESS! Thanks for everyone's help.
Here are the contents of exported.cpp:
This is almost the same as Benchmark::do_playout in benchmark.cpp
#include ego/ego.h
__declspec(dllexport) void DoPlayouts(int playout_cnt, int * blackWins, int
* whiteWins)
{
SimplePolicy policy;
Board board [1];
Board mc_board [1];
PlayoutSimplePolicy playout(policy, mc_board);
for (int i = 0; i != playout_cnt; i++) {
mc_board-load(board);
playout_status_t status = playout.run ();
if (status != too_long)
{
int score = mc_board - score ();
if (score 0)
{
(*blackWins)++;
}
else
{
(*whiteWins)++;
}
}
}
}
Łukasz Lew wrote:
Please download newest version, I made some ifdefWIN 32 ... to aid
mingw porting.
http://github.com/lukaszlew/libego/zipball/master
Under linux I can cross compile to windows binary with a following command
$ i586-mingw32msvc-g++ -o engine.exe ego/ego.cpp example/main.cpp -O3
-march=native -Iego -fomit-frame-pointer -ffast-math
-frename-registers
It might just work :)
FYI
$ i586-mingw32msvc-g++ --version
i586-mingw32msvc-g++ (GCC) 4.2.1-sjlj (mingw32-2)
And the performance I get is around 32 kpps/GHz
Lukasz
2009/4/22 Michael Williams michaelwilliam...@gmail.com:
Ok, I have Mingw installed now. That sounds like the way to go. But I
still don't know how to compile it :/
According to the SConstruct file, I should be doing something like this
to
build, but it complains:
C:\Libego g++ /Fobuild\ego\dbg\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3
-Wall
-Wextra -Wswitch-enum -fno-inline /nologo /Iego
g++: /Fobuild\ego\dbg\ego.obj: No such file or directory
g++: /c: No such file or directory
g++: /nologo: No such file or directory
g++: /Iego: No such file or directory
In file included from ego\ego.h:27,
from ego\ego.cpp:47:
ego\gtp.h:73: warning: `class Gtp' has virtual functions but non-virtual
destructor
In file included from ego\ego.cpp:54:
ego\player.cpp: In constructor `Player::Player()':
ego\player.cpp:27: warning: converting of negative value `-0x1'
to
`uint'
In file included from ego\ego.cpp:55:
ego\color.cpp: In constructor `Color::Color()':
ego\color.cpp:27: warning: converting of negative value `-0x1' to
`uint'
I also tried the build command for the optimized version:
C:\Libego g++ /Fobuild\ego\opt\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3
-Wall
-Wextra -Wswitch-enum -O3 -march=native -fomit-frame-pointer -ffast-math
-frename-registers /nologo /Iego
g++: /Fobuild\ego\opt\ego.obj: No such file or directory
g++: /c: No such file or directory
g++: /nologo: No such file or directory
g++: /Iego: No such file or directory
ego\ego.cpp:1: error: bad value (native) for -march= switch
ego\ego.cpp:1: error: bad value (native) for -mtune= switch
Sorry for my ignorance.
Łukasz Lew wrote:
2009/4/21 Łukasz Lew lukasz@gmail.com:
mingw rules!
I compiled libego with it and got a decent 32kpps / GHz ( native g++
was 44kpps / GHz)
I used wine to run resulting exe on linux:)
Lukasz
2009/4/21 Don Dailey dailey@gmail.com:
I use mingw to produce cros platform executables. I can build
executables
for linux, win32 and win64, which for my chess program is a must since
it's
64 bit.
- Don
On Tue, Apr 21, 2009 at 5:33 AM, Łukasz Lew lukasz@gmail.com
wrote:
On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote:
I forgot about cygwin indeed. It is a good idea.
But can you ran the binary on a system without cygwin?
We can run the binary on a system without cygwin if we provide
cygwin1.dll.
That is great.
Another good idea is mingw.
BTW
I would like to recommend stackoverflow.com for programming
questions.
I asked this question there
http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw
and got few good answers within a minute.
Lukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go
[computer-go] Libego benchmarking
Here is my full set of numbers. I wonder why the known kpps/GHz but unknown kpps. = Benchmarking, please wait ... = 20 playouts in 0 seconds 1.#INF kpps 40.0245 kpps/GHz (clock independent) 105316/94359 (black wins / white wins) = 20 playouts in 0 seconds 1.#INF kpps 40.0721 kpps/GHz (clock independent) 104924/94746 (black wins / white wins) = 20 playouts in 0 seconds 1.#INF kpps 40.0454 kpps/GHz (clock independent) 105097/94582 (black wins / white wins) = 20 playouts in 0 seconds 1.#INF kpps 40.0458 kpps/GHz (clock independent) 105139/94547 (black wins / white wins) = 20 playouts in 0 seconds 1.#INF kpps 40.082 kpps/GHz (clock independent) 104896/94794 (black wins / white wins) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reply to Lukasz and Don + Roadmap 2020
Mention the program so that the author can either refute your claim or fix the bug. terry mcintyre wrote: Is it reasonable to expect pro players to use 6-dan programs as a tool for analysis? The pro players are markedly better - at a rough guess, a pro player could give a 6 dan amateur human or program a 3 stone handicap. On the other end of the scale, beginning players and mid kyu players could indeed make good use of an analysis mode by a program which is better than themselves. Lastly, an analysis mode would be helpful to developers, methinks. After winning a game, I like to back up a few moves and find out when the program realized that it was behind. This often happens several moves after the fatal blow has already been struck. I know the feeling too well, when stronger players deftly skewer my group and I only discover the problem five moves later. What do they know that I don't? What do they know that the program doesn't? We have a saying, you learn the most from reviewing games which you have lost. An analysis mode can help developers to discover when their pride and joy first begins to miss the target. Lately, I have been playing quite a bit with a commercially available program. An almost-ladder which has an extra liberty will apparently be evaluated the same as a true ladder, and the program can be tricked into trying to capture my ladder-like position. This sort of predictable flaw might provide a clue to improve the next version. Terry McIntyre terrymcint...@yahoo.com Government is an association of men who do violence to the rest of us. - Leo Tolstoy ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Digital Mars
Ok, I have Mingw installed now. That sounds like the way to go. But I still don't know how to compile it :/ According to the SConstruct file, I should be doing something like this to build, but it complains: C:\Libego g++ /Fobuild\ego\dbg\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3 -Wall -Wextra -Wswitch-enum -fno-inline /nologo /Iego g++: /Fobuild\ego\dbg\ego.obj: No such file or directory g++: /c: No such file or directory g++: /nologo: No such file or directory g++: /Iego: No such file or directory In file included from ego\ego.h:27, from ego\ego.cpp:47: ego\gtp.h:73: warning: `class Gtp' has virtual functions but non-virtual destructor In file included from ego\ego.cpp:54: ego\player.cpp: In constructor `Player::Player()': ego\player.cpp:27: warning: converting of negative value `-0x1' to `uint' In file included from ego\ego.cpp:55: ego\color.cpp: In constructor `Color::Color()': ego\color.cpp:27: warning: converting of negative value `-0x1' to `uint' I also tried the build command for the optimized version: C:\Libego g++ /Fobuild\ego\opt\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3 -Wall -Wextra -Wswitch-enum -O3 -march=native -fomit-frame-pointer -ffast-math -frename-registers /nologo /Iego g++: /Fobuild\ego\opt\ego.obj: No such file or directory g++: /c: No such file or directory g++: /nologo: No such file or directory g++: /Iego: No such file or directory ego\ego.cpp:1: error: bad value (native) for -march= switch ego\ego.cpp:1: error: bad value (native) for -mtune= switch Sorry for my ignorance. Łukasz Lew wrote: 2009/4/21 Łukasz Lew lukasz@gmail.com: mingw rules! I compiled libego with it and got a decent 32kpps / GHz ( native g++ was 44kpps / GHz) I used wine to run resulting exe on linux:) Lukasz 2009/4/21 Don Dailey dailey@gmail.com: I use mingw to produce cros platform executables. I can build executables for linux, win32 and win64, which for my chess program is a must since it's 64 bit. - Don On Tue, Apr 21, 2009 at 5:33 AM, Łukasz Lew lukasz@gmail.com wrote: On Tue, Apr 21, 2009 at 11:23, elife elife2...@gmail.com wrote: I forgot about cygwin indeed. It is a good idea. But can you ran the binary on a system without cygwin? We can run the binary on a system without cygwin if we provide cygwin1.dll. That is great. Another good idea is mingw. BTW I would like to recommend stackoverflow.com for programming questions. I asked this question there http://stackoverflow.com/questions/771756/what-is-the-difference-between-cygwin-and-mingw and got few good answers within a minute. Lukasz ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Digital Mars
I got Libego compiled to a Windows DLL using Visual Studio and was able to call it, but I was only getting around 5k pps on my Core2. So I wanted to try another compiler. Has anyone used the Digital Mars C++ compiler? Or is there another compiler I should try? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tree Contention
You can change the value all you want. You just can't change the key. Jason House wrote: On Apr 14, 2009, at 7:57 PM, Rémi Coulom remi.cou...@univ-lille3.fr wrote: Jason House wrote: Out of curiosity, how do you intelligently delete old nodes? Reference counting won't always work due to cycles, and a nieve scan of the tree could block all threads. I store a date of birth in every node. At the beginning of a new search, I increment time, and refresh the date of birth of all the descendants of the new root. When allocating a new node, I can reuse old hash entries. Reuse hash entries? I assume you don't mean reuse entries because a later hash value matches (should be quite rare, even with 32 bit hash codes). The lockless hash you gave links to does not handle ever changing a hash value once it's set. If you CAS the tombstone value before the key, I guess it'd be reasonably safe, but not guaranteed. Did you add any new states to guarantee safety? Or am I thinking about this the wrong way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tree Contention
I think your hash value is your first-try index into the hash table. So a 32-bit hash would be a 4E9 sized table. Probably too big for Remi's computer. I'd guess that he's using something between 16 and 32 bits in his hash hey. Jason House wrote: On Apr 15, 2009, at 6:50 PM, Michael Williams michaelwilliam...@gmail.com wrote: You can change the value all you want. You just can't change the key. Right... That's the design in the google talk. Remi said he can reuse cache entries and so avoids resizing / copying (greatly simplifying the algorithm). I find that 32 bit zobrist hashing takes a few minutes before reusing a single hash value. That's too infrequent to use in place of real cleanup. Smaller hashes (such as 16 bit) would have too much ovelap to be useful... So rejecting that possibility leaves me clueless about what reusing a hash entry could mean besides replacing a complete slot in the table. Jason House wrote: On Apr 14, 2009, at 7:57 PM, Rémi Coulom remi.cou...@univ-lille3.fr wrote: Jason House wrote: Out of curiosity, how do you intelligently delete old nodes? Reference counting won't always work due to cycles, and a nieve scan of the tree could block all threads. I store a date of birth in every node. At the beginning of a new search, I increment time, and refresh the date of birth of all the descendants of the new root. When allocating a new node, I can reuse old hash entries. Reuse hash entries? I assume you don't mean reuse entries because a later hash value matches (should be quite rare, even with 32 bit hash codes). The lockless hash you gave links to does not handle ever changing a hash value once it's set. If you CAS the tombstone value before the key, I guess it'd be reasonably safe, but not guaranteed. Did you add any new states to guarantee safety? Or am I thinking about this the wrong way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Tree Contention
What tricks are people doing to minimize the performance degradation due to multiple threads contending for access to the tree (in MCTS)? Do you only lock a portion of the tree? How would that work? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tree Contention
I considered something similar. But instead of using a win count and a loss count, I use a win count and a simulation count. In that scenario, you would update the simulation count immediately, and then maybe update the wincount once you know the result. But I haven't tried it either. Álvaro Begué wrote: I haven't implemented this successfully, so I probably shouldn't be giving advice to anyone, but what I was trying to do when we stopped developing dimwit was the following: * When a thread enters a node of the UCT tree, increment the number of losses (This will discourage other threads from entering the same branch). * When you want find out if the playout was actually a win or a loss, increment the wins counter and decrement the losses counter. All the manipulations can be done without locks with a tiny little bit of assembly or with intrinsic functions. If you need details, I can try to get you sample code for Mac OS X or Linux (both on x86). Álvaro. On Mon, Apr 13, 2009 at 6:08 PM, Rémi Coulom remi.cou...@univ-lille3.fr wrote: Michael Williams wrote: What tricks are people doing to minimize the performance degradation due to multiple threads contending for access to the tree (in MCTS)? Do you only lock a portion of the tree? How would that work? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ If you are motivated, you can try a completely lockless solution: http://computer-go.org/pipermail/computer-go/2008-March/014537.html It scales well up to 16 cores: http://computer-go.org/pipermail/computer-go/2008-March/014547.html Using a single global lock is really very inefficient, especially for 9x9 or if you have many cores. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT-MC process
no. just don't prune the tree. or allow unpruning. compgo...@aol.com wrote: Following is a description of the nature and process of the UCT-MC method. For a given Go board position P, let Np denote the total number of all possble end of game positions. Let Ei denote each of the end of game position (i=1,...,Np). Let Mip denote all possible move sequences that starts from the position P and ends at position Ei. Assume the most simple MC simulation is used and there is no prunning at all except the detection of the end of the game. Then the average of N number of MC simulation gives the following ratio. F=(sum of Mip where black wins)/(sum of all Mip) Now the question is for F 0.5 does it mean that P is a wnning position for black? The anwser is not necessarily. Statistically for more than 50% of the cases it's true. This is the reason why the MC evaluation works. It's also the reason why MC alone cannot be used to evaluate the game. The reason above happens is that there exist narrow paths in the game space. The searching part of the UCT-MC method is actually trying to identify these narrow paths. With the so called heavy playout the situationis a little dfferent. Here the playout itself gets involved in the identifcation of the narrow paths. In most of the cases the rules used in the heavy playout are not perfect. This results in the incorrect prunning even in small number of the cases. Generally the searching part of the UCT-MC method can compensate for this error. However, one has to be carefull here, because it's not guaranted. For example, it can hapen if the playout and the searching part uses the same prunning rules. Could it be true that for more powerful computers one should use lighter playout? DL Check all of your email inboxes from anywhere on the web. Try the new Email Toolbar now http://toolbar.aol.com/mail/download.html?ncid=txtlnkusdown0027! ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Libego for Windoze
If I have only that file in the project, and fix some header includes, I am
left with many errors still. The first few are complaining about this block:
uint64 FastTimer::get_cc_time () volatile {
uint64 ret;
__asm__ __volatile__(rdtsc : =A (ret) : :);
return ret;
}
Łukasz Lew wrote:
I might have back to revert to make/cmake (from scons) after all.
There is some hope in google software construction toolkit and in
scons on google summer of code.
In libego a lot have changed. Now ego is truely a library and is
compiled separately.
ego/ego.cpp is enough to compile library. Then example/main.cpp is an
gtp engine.
Lukasz
On Fri, Apr 10, 2009 at 04:34, Darren Cook dar...@dcook.org wrote:
Has anyone created VC++ project files for Libego? Or any Libego Windows
build?
Have you tried starting a new project and dragging in main.cpp and
gtp.cpp, then seeing if it compiles?
(I've only compiled on linux; the libego I have on my development
machine is from June 2007, presumably before scons support as I wrote my
own makefile, but main.cpp and gtp.cpp seem to be the only top-level files.)
Darren
P.S. I used scons for a couple of years, but got frustrated by how hard
it made trying to do something they'd not allowed for (e.g. having my
unit tests compile and run in a specific order). I've also used jam and
ant, but the past 3 or 4 years my make replacement of choice is... drum
roll please... make. It turns out despite its poor design decisions
(such as treating tab and space differently), at least I can always get
the job done with it.
--
Darren Cook, Software Researcher/Developer
http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
open source dictionary/semantic network)
http://dcook.org/work/ (About me and my work)
http://dcook.org/blogs.html (My blogs and articles)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
