Re: [computer-go] Zobrist hashing with easy transformation comparison
Hi Erik And what distinguishes database look up from things like transposition table look up? Why wouldn't one use database look up during tree search? The interest in rotation/mirror. In database search, what is good for a position is good for the mirror/rotation. In tree search, rotation of the full board does not happen, and if it does (in a very simple position) its pointless to detect because it is not the same position. 4. The analysis based on uniform distributions are fundamentally flawed because the move sequences are not random in go, particularly, the BWBWBW sequence can only be avoided by pass moves which do not occur in real games globally before the end of the game. So? Of course. The most important superko that really happens in strong games is triple ko. Detecting triple ko with probability=1 and a 32 bit hash is not a trivial question. And it requires B keys to have some difference with W keys. Note that to be _sure_ that a move is legal, you only have to check 6x32 bit keys. That would be impossible if the hashes were pure random. You simply cannot control any combination of 19x19x2=722 hashes of length 6, but you can control BWBWBW even of length 7. Since the test is faster than any another and is also, unlike the others, with error probability=0 it is simply the best. Of course, it does not consider board repetitions of longer cycles. I have searched for (the possibility of) such cycles in my 50K games database and did not find any. I would love to see a game where both players are at least shodan, in which a superko other than triple ko limits the legal options. If someone has such a game, please post it. I'm speculating here because I seem to be missing some context, but AFAICS almost any Go-specific application will have more legal moves hash keys than bits for the hash. Of course. That's because full global search is intractable. But local search with 16 empty cells (which can be either B or W, and therefore you only have 32 keys) is not. That's what I mean when I say when it makes sense. Again, I do use 64 bit hashes. And my favorite: if the hash calculation is a major factor in the performance of your program, you should seriously consider adding some knowledge. We have seen this when talking about programming language. Each time someone cares about details and builds programs that are optimized from the day of their birth, they are: a. Dirty and hard to maintain. (IMO only patched programs are hard to maintain and they are patched because important issues were thought too late.) b. Caring about stupid issues == ignoring Big Algorithmic Improvements. (IMO If you don't really care about details you don't really control the big picture. And more important, you only have to do it once, if you do it well. That will give you a lot of time for thinking about algorithms.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bit Twiddling Hacks
On 2/12/07, Phil G [EMAIL PROTECTED] wrote: For those doing a lot of bit logic in their computer go programs, you might be interested in this collection of highly optimized methods for doing things with bits (like counting bits sets in parallel and computing the minmum or maximin of two integers without branching): http://graphics.stanford.edu/~seander/bithacks.html Seen it before, but still a very nice site with lots of clever tricks. I have some improved bit counters, if anyone is interested... Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach
The following code did not hurt the strength against self-play in over 2000 games at boardsize 8x8 (faster games) with 10k playouts per move: moveEval[m] = (float)wins[m]/nGames[m] + points[m]/(nGames[m]*Board-Spaces*100) where points[m] is accumulated only for wins. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bit Twiddling Hacks
Erik, I am. Jim - Original Message From: Erik van der Werf [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, February 13, 2007 3:37:13 PM Subject: Re: [computer-go] Bit Twiddling Hacks On 2/12/07, Phil G [EMAIL PROTECTED] wrote: For those doing a lot of bit logic in their computer go programs, you might be interested in this collection of highly optimized methods for doing things with bits (like counting bits sets in parallel and computing the minmum or maximin of two integers without branching): http://graphics.stanford.edu/~seander/bithacks.html Seen it before, but still a very nice site with lots of clever tricks. I have some improved bit counters, if anyone is interested... Erik ___ 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] Effective Go Library v0.101
Does anyone know what find-union algorithms Lukasz is referring to in the README file? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Effective Go Library v0.101
On 2/13/07, Heikki Levanto [EMAIL PROTECTED] wrote: On Sun, Feb 04, 2007 at 02:13:33PM +0100, ?ukasz Lew wrote: Optimizing and refactoring became my hobby, but it's too absorbing :) It's time to add some features now. Just one question: Is the gtp support sufficient to play against other machines (if we ignore the rather trivial genmove code :-)? If not, adding the missing commands, even as dummies, would be a help for beginning programmers. Yes it is. Also, I notice that I can not use quarry (graphical interface for Go and Try GoGui. other games) to play against 'engine_opt'. Presumably it needs a few more gtp commands implemented. I will look into this, because if I am to write any sort of engine, I will want to be able to play agaist it. Will make a good warming-up exercise. Thanks again for a good, useful library. I have started to look into it, and once I got aroundthe namespaces and short names within, it looks reasonably clear. I will experiment with some ideas, and if anything useful comes out of them, I let you know. If I run into obvious improvements, I may even send a patch. Thanks :) Łukasz Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach
On 2/9/07, Weston Markham [EMAIL PROTECTED] wrote: I don't seem to have any numbers on this anymore, but I should be able to try some experiments this weekend. I do have some code that does what I describe below. It is also using an all moves as first heuristic. According to my notes, I made this change in an attempt to avoid severely conservative (in my non-expert opinion) moves near the beginning of the game, which seem to be preferred when using all-moves-as-first. It specifically aims for a 30-point lead at the beginning of the game, and reduces this by one point for each turn into the game. I should point out that I am not averaging scores, but simply changing which games I count as wins for the evaluation of a move. This is perhaps not quite what Steve Uurtamo had in mind when he was originally musing about being greedy at the beginning of the game. Nevertheless, it is a very similar sort of idea to what he described, so I thought that I would mention it. Weston On 2/8/07, Chris Fant [EMAIL PROTECTED] wrote: On 2/8/07, Weston Markham [EMAIL PROTECTED] wrote: I believe that I have had some success with an approach like this, actually. I believe that I initially only tally games that are won by a certain margin, and reduce that margin to zero as the game progresses. I am pretty sure that this improves upon straight Monte Carlo. I think that I can get some numbers on it, if anyone is interested. Weston Yes, please. I did run some tests over the weekend, but they did not complete as quickly as I had expected. Anyway, I have enough data at this point to say that although there is nothing spectacular to show one way or the other, I was probably wrong that the code was an improvement. Playing against gnugo 3.7.10, komi 7.5, playing black in 50% of the games: 86/732 games won baseline (11.7%) 106/1000 games won after enabling logic described above. (10.6%, a slight degradation) I also tried a version that dynamically adjusts an expected score, and tallies the number of games where the score exceeds this. It appears to give an improvement: 12.8% of the games were won, out of 1000. Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bit Twiddling Hacks
Here's a link: http://erikvanderwerf.tengen.nl/pubdown/bitcounters.c Have fun, Erik On 2/13/07, Jim O'Flaherty, Jr. [EMAIL PROTECTED] wrote: Erik, I am. Jim - Original Message From: Erik van der Werf [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Tuesday, February 13, 2007 3:37:13 PM Subject: Re: [computer-go] Bit Twiddling Hacks On 2/12/07, Phil G [EMAIL PROTECTED] wrote: For those doing a lot of bit logic in their computer go programs, you might be interested in this collection of highly optimized methods for doing things with bits (like counting bits sets in parallel and computing the minmum or maximin of two integers without branching): http://graphics.stanford.edu/~seander/bithacks.html Seen it before, but still a very nice site with lots of clever tricks. I have some improved bit counters, if anyone is interested... Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
