Re: [Computer-go] Quantum computing
IBM's computer only stores 5 qubits. The biggest quantum computers only store 1000 qubits. No. For now. MW Is it time to start developing the next generation of game playing algorithms? http://www.research.ibm.com/quantum/ ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Finding Alphago's Weaknesses
One question is whether Lee Sedol knows about these weaknesses. Another question is whether he will exploit those weaknesses. Lee has a very simple style of play that seems less ko-oriented than other players, and this may play into the hands of Alpha. Michael Wing I was surprised the Lee Sedol didn't take the game a bit further to probe AlphaGo and see how it responded to [...complex kos, complex ko fights, complex sekis, complex semeais, ..., multiple connection problems, complex life and death problems] as ammunition for his next game. I think he was so astonished at being put into a losing position, he wasn't mentally prepared to put himself in a student's role again, especially to an AI...which had clearly played much weaker games just 6 months ago. I'm hopeful Lee Sedol's team has been some meta-strategy sessions where, if he finds himself in a losing position in game two, he turns it into exploring a set of experiments to tease out some of the weaknesses to be better exploited in the remaining games. On Thu, Mar 10, 2016 at 8:16 AM, Robert Jasiek wrote: On 10.03.2016 00:45, Hideki Kato wrote: such as solving complex semeai's and double-ko's, aren't solved yet. To find out Alphago's weaknesses, there can be, in particular, - this match - careful analysis of its games - Alphago playing on artificial problem positions incl. complex kos, complex ko fights, complex sekis, complex semeais, complex endgames, multiple connection problems, complex life and death problems (such as Igo Hatsu Yoron 120) etc., and then theoretical analysis of such play - semantic verification of the program code and interface - theoretical study of the used theory and the generated dynamic data (structures) -- robert jasiek ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go [1] Links: -- [1] http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo won first game!
In my opinion, the thing that programs do worst is ko. Lee did not play any kos, except one minor irrelevant one in the lower left. This game was so simple that the program could accurately model the whole board. If Lee wants to win, he needs to start 2 or 3 simultaneous kos. Michael Wing Congratulations, AlphaGo and team. And by resignation! That's fantastic! Anyone know where the tipping point was? Did Sedol get the end game order just slightly off and AlphaGo took advantage? Or was their an earlier poor move by Sedol and/or surprising (and good) move by AlphaGo? I'm WAY too weak a player to even make stupid guesses. Any links to in depth analysis would be greatly appreciated! On Wed, Mar 9, 2016 at 1:46 AM, René van de Veerdonk wrote: wow .. congrats to the AlphaGo team!! On Tue, Mar 8, 2016 at 11:43 PM, Hiroshi Yamashita wrote: AlphaGo won 1st game against Lee Sedol! Hiroshi Yamashita ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go [1] ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go [1] Links: -- [1] http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[computer-go] some benchmarks
I have ported my go board engine from my laptop to a desktop, and I wanted to pass on these benchmarks. Laptop T2300@ 1.67G 533MHz memory - Cygwin/Windows Desktop 920-i7@ 2.67 G 1066 MHz memory - Ubuntu After factoring out cpu-speed, my go code runs about 1.25 times as fast on the new processor. Since it mostly fits in cache, some is probably due to the improved cache and the rest is the improved CPU. This means that cpus haven't improved that much in the last 3 years. I ran multiple copies of the benchmark at once: 1 copies: 100% 2 copies: 100% 100% 4 copies: 100% 100% 67% 67% 8 copies: 67% 67% 67% 67% 67% 67% 67% 67% Hyper-threading works pretty well on the i7. So, with little cache conflict, you should expect about 5.33 times as much work, as a single processor, which is useful to know. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
In the cgbg framework, arrays and lists are unsorted. But, there are many reasonable variations. You will just have to jump in and read some code or write your own to fully understand. I recommend reading the gnugo source, which is pretty darn good. Michael Wing > How do these link list of liberties and array of liberties variants work? Are > they sorted lists/arrays? I considered bitmaps but it seemed in many ways a bit wasteful i.e. in most cases for a given group the bitmap probably is extremely sparse. Also if you are trying to identify individual bits I cannot think of any techniques to do this quickly. --- On Sat, 8/15/09, w...@swcp.com wrote: > From: w...@swcp.com > Subject: Re: [computer-go] representing liberties > To: "computer-go" > Date: Saturday, August 15, 2009, 10:54 AM > I tested bit maps in the cgbg > framework, and they perform > slower than other techniques. However, I wrote the code in > C which > does not use the built-in hardware bit tests and sets nor > use SIMD > to merge or clear sets. If you do it in assembler, bitmaps > might work > much better. > > There are various ways that bit test could be combined with > other > techniques such as linked list. However, as far as I know, > these > combinations have not been extensively explored. > > Part of the reason is that the average number of liberties > in a chain > during an insert (when running MC playouts) is only about > 1.3. > > Michael Wing > > > I've seen bit-maps mentioned many times, but is there > any evidence > > it's faster than a 'traditional' implementation? > > > > You can also use board-sized bitmaps. Merging is > a trivial OR > > > operation. > > ___ > 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] representing liberties
I tested bit maps in the cgbg framework, and they perform slower than other techniques. However, I wrote the code in C which does not use the built-in hardware bit tests and sets nor use SIMD to merge or clear sets. If you do it in assembler, bitmaps might work much better. There are various ways that bit test could be combined with other techniques such as linked list. However, as far as I know, these combinations have not been extensively explored. Part of the reason is that the average number of liberties in a chain during an insert (when running MC playouts) is only about 1.3. Michael Wing > I've seen bit-maps mentioned many times, but is there any evidence > it's faster than a 'traditional' implementation? > > You can also use board-sized bitmaps. Merging is a trivial OR > > operation. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
There are many ways to track the liberties of a chain
And there are many different implementations of each:
* none
* count pseudo liberties
* simple count
* do count, sum, and sum squared, which can detect atari
* array of liberties
* store all liberties
* store first k liberties
* linked list of liberties
* doubly linked list, fixed locations for liberties (needs many nodes)
* doubly linked list, also store liberty (needs only 1600 nodes)
After fairly extensive performance testing on an Intel Core chip,
I find that most reasonable techniques perform within a factor
of 1.5 or 2.0 of the best, so as a practical matter, it doesn't
really matter that much. Yet, 2 performance results stand out:
* for doing pure MC, use simple pseudo liberties
* for doing board analysis (like reading ladders), use arrays of liberties.
I am in the middle of porting this to the i7 core architecture. because
of the larger, faster L2 cache doubly linked lists may work well.
I have a code generator that makes it (somewhat) easy to try this out:
http://pages.swcp.com/~wing/cgbg/
Of course, writing out the different implementations yourself is a good
exercise to help understand what happens.
Michael Wing
> Thanks both. I guess reading over my message it was a bit ambiguous since I
> could have meant
either liberty counts i.e.. |liberty| or the actual contents of the liberty
set. I actually meant the latter.
>
> When it comes to liberty counts- the only system I know of (which I read
> about here) was to not
have precise liberty counts but rather have a situation which you guarantee
that the liberties reach 0
at the same time a liberty count would. I think the term used here was
pseudo-liberties. This makes
merging easy but I am curious how are merges handled if you have precise
liberty counts.
>
> I assume that one would have to walk the stones in a given chain after you
> perform the addition
and subtract one for each duplicate.
>
> --- On Fri, 8/14/09, Don Dailey wrote:
>
> > From: Don Dailey
> > Subject: Re: [computer-go] representing liberties
> > To: "computer-go"
> > Date: Friday, August 14, 2009, 6:16 PM
> > I'm not sure I understand your
> > question. But I'll try to explain it a little
> > better.
> >
> > Basically, you keep a C structure or the equivalent which
> > tracks each individual chain. On your board array you
> > put the index of that structure (or a pointer to it.)
> >
> >
> > The structure will look something like this:
> >
> > typedef struct
> > {
> > int color;
> > int stone_count;
> > int head_stone;
> > int liberty_count;
> >
> > } chain_t;
> >
> > And perhaps other crap you may want to keep.
> >
> >
> > So lets say you have an array of these, one for each chain
> > on the board with room to grow.
> >
> > When you place a stone on the board, you look at the 4
> > neighbors to see if this is going to be a new chain of 1, or
> > connect to an existing chain. If it's an existing
> > chain, you will need to create a brand new entry, set the
> > stone_count to 1, the liberty count to 1, 2, 3 or 4 (by
> > looking at the 4 surrounding points) and set the
> > head_stone to the location of the new stone. the
> > head_stone can be ANY stone in the group - it's just a
> > way to quickly reference one of the stones in the group.
> >
> >
> > Your board of course will have the index of the
> > chain_t. I start at 1 and make zero mean empty but you
> > could use -1 to represent empty squares if you want to.
> > So if the value of the board array is 5, it means it is
> > the 5th chain in the chain_t array and you can immediately
> > see how many stones are there, how many liberties etc.
> >
> >
> > The logic for updating the liberty count is pretty basic.
> > When you place a stone next to an existing group, you know
> > that group loses 1 liberty, so you subtract 1 from ANY group
> > of either color that touches it (there can only be 4 at
> > most.) But then you must check to see if the stone
> > you just placed created liberties for the group it belongs
> > to. So you count the empty points around the new stone
> > that do not already belong to that same group.
> > (There is also the case where 2 chains must be merged, but
> > we will ignore that for now.)
> >
> >
> > When a group is captured, you must do a bit more
> > housekeeping. You need to delete it's entry somewhow
> > in the chain array and you will have to recalcula
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
£ukasz, My code is online in the directory: http://pages.swcp.com/~wing/cgbg/ The file cgbg is a ruby program, which generates a C program, as well as a performance test. So the only difference is the desired distinction. My implementation of dense links is similar to, but not identical to the gnugo version. The file README has instructions. The functional test are broken. (Sorry) Use the config file call "config" to compare liberty representations. The other config files compare a wide variety of other go board representation attributes. Let me know if you want a specific data structure tested, and I can help write the performance test. Michael Wing > Can you give some more info about experimental setup and the > algorithms you used? > > On Thu, Apr 9, 2009 at 01:42, wrote: > > Lukasz, > > > > My performance test suite did 7 ways of tracking liberties: > > * dense linked lists, (where 4 * number of positions are allocated) > I guess this is what gnugo-montecarlo implemented? > > * sparse linked lists, (where 256 * number of positions are allocated) > ? > > * arrays of liberties, (256 * number of positions are allocated) > Is it like regular gnugo board implementation. > > * trivial pseudo-liberties > like libego I guess. > > * boesch computation for pseudo-liberties > an link? > > * bitsets > one bit per board location per string? > > * bitsets, with each bit in a separate word. > ? > > > > I tested all of them using 2 techniques: > > * simple mc, (which never asked for the list of liberties for a group) > > Note that it also tests reseting the board in 3 ways. > one playout over and over again, or many randomized playouts? (you > mention 324 moves) > > * ladder reading exercises, which asked for the liberties of a group > > and used undo. > > > > > Results are were pretty striking. Below is raw data. > > Tests were on a 3 year old Core2. > > * for pure mc: simple pseudo liberties was by far the fastest. > > * for ladder reading: arrays of liberties was by far the fastest. > > * as noted in other emails, linked lists have horrible cache behavior. > can you elaborate on that? > Does it apply to dense lists? > > In general I'm about to implement dense lists. > What is slow about them in your implementation? > (in playouts) > > > * So, as far as I can see the only question is whether you will > > do any classic reading or not, which will determine the > > best implementation. > > > > > > Michael Wing > > > > --- > > > > DENSE LINKS > > normal 324 moves: total 3000 ms, each game 0.30 ms, .33 games/sec > > undo 324 moves: total 3860 ms, each game 0.386000 ms, 2590.673575 games/sec > > reset 324 moves: total 3062 ms, each game 0.306200 ms, 3265.839321 games/sec > > ladder: total 3469 ms, each ladder 0.346900 ms, 2882.675123 ladders/sec > > > > SPARSE LINKS > > normal 324 moves: total 7109 ms, each game 0.710900 ms, 1406.667604 games/sec > > undo 324 moves: total 7703 ms, each game 0.770300 ms, 1298.195508 games/sec > > reset 324 moves: total 10890 ms, each game 1.089000 ms, 918.273646 games/sec > > ladder: total 8062 ms, each ladder 0.806200 ms, 1240.387001 ladders/sec > > > > BOESCH PSEUDO LIBERTIES > > normal 324 moves: total 2281 ms, each game 0.228100 ms, 4384.042087 games/sec > > undo 324 moves: total 3422 ms, each game 0.342200 ms, 2922.267680 games/sec > > reset 324 moves: total 2532 ms, each game 0.253200 ms, 3949.447077 games/sec > > ladder: total 5797 ms, each ladder 0.579700 ms, 1725.030188 ladders/sec > > > > SIMPLE PSEUDO LIBERTIES > > normal 324 moves: total 1985 ms, each game 0.198500 ms, 5037.783375 games/sec > > undo 324 moves: total 2328 ms, each game 0.232800 ms, 4295.532646 games/sec > > reset 324 moves: total 1922 ms, each game 0.192200 ms, 5202.913632 games/sec > > ladder: total 4890 ms, each ladder 0.489000 ms, 2044.989775 ladders/sec > > > > ARRAYS > > normal 324 moves: total 2578 ms, each game 0.257800 ms, 3878.975950 games/sec > > undo 324 moves: total 3313 ms, each game 0.331300 ms, 3018.412315 games/sec > > reset 324 moves: total 2703 ms, each game 0.270300 ms, 3699.593045 games/sec > > ladder: total 2703 ms, each ladder 0.270300 ms, 3699.593045 ladders/sec > > > > BITSET > > normal 324 moves: total 3453 ms, each game 0.345300 ms, 2896.032436 games/sec > > undo 324 moves: total 4203 ms, each game 0.420300 ms, 2379.252915 games/sec > > reset 324 moves: total 3828 ms, each game 0.382800 ms, 2612.330199 games/sec > > ladder: total 6735 ms, each ladder 0.
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Lukasz, My performance test suite did 7 ways of tracking liberties: * dense linked lists, (where 4 * number of positions are allocated) * sparse linked lists, (where 256 * number of positions are allocated) * arrays of liberties, (256 * number of positions are allocated) * trivial pseudo-liberties * boesch computation for pseudo-liberties * bitsets * bitsets, with each bit in a separate word. I tested all of them using 2 techniques: * simple mc, (which never asked for the list of liberties for a group) Note that it also tests reseting the board in 3 ways. * ladder reading exercises, which asked for the liberties of a group and used undo. Results are were pretty striking. Below is raw data. Tests were on a 3 year old Core2. * for pure mc: simple pseudo liberties was by far the fastest. * for ladder reading: arrays of liberties was by far the fastest. * as noted in other emails, linked lists have horrible cache behavior. * So, as far as I can see the only question is whether you will do any classic reading or not, which will determine the best implementation. Michael Wing --- DENSE LINKS normal 324 moves: total 3000 ms, each game 0.30 ms, .33 games/sec undo 324 moves: total 3860 ms, each game 0.386000 ms, 2590.673575 games/sec reset 324 moves: total 3062 ms, each game 0.306200 ms, 3265.839321 games/sec ladder: total 3469 ms, each ladder 0.346900 ms, 2882.675123 ladders/sec SPARSE LINKS normal 324 moves: total 7109 ms, each game 0.710900 ms, 1406.667604 games/sec undo 324 moves: total 7703 ms, each game 0.770300 ms, 1298.195508 games/sec reset 324 moves: total 10890 ms, each game 1.089000 ms, 918.273646 games/sec ladder: total 8062 ms, each ladder 0.806200 ms, 1240.387001 ladders/sec BOESCH PSEUDO LIBERTIES normal 324 moves: total 2281 ms, each game 0.228100 ms, 4384.042087 games/sec undo 324 moves: total 3422 ms, each game 0.342200 ms, 2922.267680 games/sec reset 324 moves: total 2532 ms, each game 0.253200 ms, 3949.447077 games/sec ladder: total 5797 ms, each ladder 0.579700 ms, 1725.030188 ladders/sec SIMPLE PSEUDO LIBERTIES normal 324 moves: total 1985 ms, each game 0.198500 ms, 5037.783375 games/sec undo 324 moves: total 2328 ms, each game 0.232800 ms, 4295.532646 games/sec reset 324 moves: total 1922 ms, each game 0.192200 ms, 5202.913632 games/sec ladder: total 4890 ms, each ladder 0.489000 ms, 2044.989775 ladders/sec ARRAYS normal 324 moves: total 2578 ms, each game 0.257800 ms, 3878.975950 games/sec undo 324 moves: total 3313 ms, each game 0.331300 ms, 3018.412315 games/sec reset 324 moves: total 2703 ms, each game 0.270300 ms, 3699.593045 games/sec ladder: total 2703 ms, each ladder 0.270300 ms, 3699.593045 ladders/sec BITSET normal 324 moves: total 3453 ms, each game 0.345300 ms, 2896.032436 games/sec undo 324 moves: total 4203 ms, each game 0.420300 ms, 2379.252915 games/sec reset 324 moves: total 3828 ms, each game 0.382800 ms, 2612.330199 games/sec ladder: total 6735 ms, each ladder 0.673500 ms, 1484.780995 ladders/sec BITSET IN WORDS normal 324 moves: total 6172 ms, each game 0.617200 ms, 1620.220350 games/sec undo 324 moves: total 7203 ms, each game 0.720300 ms, 1388.310426 games/sec reset 324 moves: total 10157 ms, each game 1.015700 ms, 984.542680 games/sec ladder: total 7172 ms, each ladder 0.717200 ms, 1394.311210 ladders/sec > What other methods have you tried? > > Lukasz > > On Thu, Apr 2, 2009 at 17:14, wrote: > > Isaac, > > > > I implemented about 6 way to track liberties, > > a couple years ago, and measured the running > > performance, and by far the best is also the > > simplest: keep an array of liberties for each > > chain, and do a simple linear search. > > > > This may seem slow, but it has a couple real > > advantages. First, it works with the cache > > to maximize locality. Second it is very simple. > > > > Michael Wing > > > >> > Many Faces also counts real liberties, and is quite fast enough. > >> > > >> > >> > > I can confirm, with a bit of optimization, counting real liberties is > >> > > only marginally slower than counting pseudo-liberties. So there's > >> > > really no benefit that I can see from using pseudo liberties. > >> > > > >> > > Mark > >> > > > >> > >> > > > When John Tromp and I were thinking about these things in 2007 we > >> > > > decided to switch to counting real liberties instead of > >> > > > pseudo-liberties. Someone (Rémi?) told us that in the end the > >> > > > performance difference wasn't very large, and we verified this. > >> > > > > >> > > > Álvaro. > >> > > > > >> > >> Thanks. What is a fast way to track libe
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Isaac, My numbers were extracted from the insert() function, so my numbers don't say how long the average search. would be. When you place a stone on the board, you immediately add up to 4 adjacent liberties, one at a time. Never-the-less, it does say something. I have intended to measure the distributions of all set operations in the board funcions, but I have not finished them. Space is also very significant when choosing a representation. Another issue is whether the board can undo or rewind to saved positions. The arrays that store liberties take 19*19*256 shorts or 184832 bytes. (A chain can only have about 2/3 of the locations on the board as liberties, if you follow the usual rules.) This overwhelms all other data in the board. Michael Wing > I made some artificial tests where I do x inserts, 1 delete, 10 counts and > 1 merge. For x=4 inserts, linear arrays are about 4 times faster. For x=8 > inserts, linear arrays are about 3 times faster. From your data I calculated > an average liberty count of 2.8 (which seems low to me). This means that for > the used board sizes, the constant time merge does not pay off vs. the > constant time count. > > So I can confirm that the linear arrays do seem to be faster, however I > haven't tested how they compare to pseudo libs. For heavier playouts, I > reckon that true liberties might be a bit faster and more useful. > > Isaac > > Original-Nachricht > > Datum: Fri, 3 Apr 2009 10:22:37 MDT > > Von: w...@swcp.com > > An: "computer-go" > > Betreff: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties? > > > Isaac, > > > > Most groups have only say 4 to 8 liberties. This is why simple arrays of > > liberty locations work so well. The new Intel CPUs have instructions > > that can search strings 16 bytes at a time, so it could run even faster. > > > > Bit vectors also work, but if you want a true liberty count, then you have > > to avoid counting (1 or 1) as 2, which is the pseudo liberty problem, and > > which takes more code to write and more time to compute. > > > > When I started, I wanted to find a better implementation than gnugo, and > > I was unable to do so. Of course one can refine or simplify the gnugo code > > in many different ways, but gnugo has all of the good ideas. > > > > Michael Wing > > > > > > > > PS: Here is the data for how many times the program tried to insert > > a stone into a chain that has x liberties or x adjacencies. It was taken > > from a run that combined monte carlo simulations and ladder reading > > exercises. Note that there are only 2% as many liberties/adjacencies > > of size 8 as there are of size 0. Chains with liberties/adjacency lists > > of size 16 are so few as to be irrelevant. > > > >data here. > > > > > > >> On Thu, Apr 2, 2009 at 5:14 AM, wrote: > > >>> Isaac, > > >>> > > >>> I implemented about 6 way to track liberties, > > >>> a couple years ago, and measured the running > > >>> performance, and by far the best is also the > > >>> simplest: keep an array of liberties for each > > >>> chain, and do a simple linear search. > > >>> > > >>> This may seem slow, but it has a couple real > > >>> advantages. First, it works with the cache > > >>> to maximize locality. Second it is very simple. > > >>> > > > > > > This *does* seem slow, even when caching the number of liberties. You > > > mentioned that you did this a couple years ago, do you think it still > > holds > > > true? Thank you for the information. > > > > > >> This is what I do too. I never bothered with bit-arrays but possibly > > >> that's simply because I fail to see how you can merge two chains and > > >> count liberties in O(1). > > > > > > Merging would be a simple OR operation. Counting can be done, for > > example, > > > with some kind of binary search. Counting the bits set has been well > > > researched and many different algorithms exist. > > > > > > > > ___ > > computer-go mailing list > > computer-go@computer-go.org > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > -- > Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 > ___ > 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] Pseudo liberties: Detect 2 unique liberties?
Isaac, Most groups have only say 4 to 8 liberties. This is why simple arrays of liberty locations work so well. The new Intel CPUs have instructions that can search strings 16 bytes at a time, so it could run even faster. Bit vectors also work, but if you want a true liberty count, then you have to avoid counting (1 or 1) as 2, which is the pseudo liberty problem, and which takes more code to write and more time to compute. When I started, I wanted to find a better implementation than gnugo, and I was unable to do so. Of course one can refine or simplify the gnugo code in many different ways, but gnugo has all of the good ideas. Michael Wing PS: Here is the data for how many times the program tried to insert a stone into a chain that has x liberties or x adjacencies. It was taken from a run that combined monte carlo simulations and ladder reading exercises. Note that there are only 2% as many liberties/adjacencies of size 8 as there are of size 0. Chains with liberties/adjacency lists of size 16 are so few as to be irrelevant. 0 => 4662825 1 => 3524214 2 => 2323725 3 => 1167185 4 => 368184 5 => 245659 6 => 167392 7 => 117655 8 => 84715 9 => 61126 10 => 44407 11 => 32309 12 => 24105 13 => 17639 14 => 13111 15 => 9935 16 => 7378 17 => 5417 18 => 3975 19 => 2900 20 => 2111 21 => 1566 22 => 1055 23 => 783 24 => 616 25 => 399 26 => 290 27 => 221 28 => 174 29 => 127 30 => 95 31 => 71 32 => 60 33 => 44 34 => 15 35 => 4 36 => 2 37 => 1 38 => 1 39 => 0 40 => 0 41 => 0 42 => 0 >> On Thu, Apr 2, 2009 at 5:14 AM, wrote: >>> Isaac, >>> >>> I implemented about 6 way to track liberties, >>> a couple years ago, and measured the running >>> performance, and by far the best is also the >>> simplest: keep an array of liberties for each >>> chain, and do a simple linear search. >>> >>> This may seem slow, but it has a couple real >>> advantages. First, it works with the cache >>> to maximize locality. Second it is very simple. >>> > > This *does* seem slow, even when caching the number of liberties. You > mentioned that you did this a couple years ago, do you think it still holds > true? Thank you for the information. > >> This is what I do too. I never bothered with bit-arrays but possibly >> that's simply because I fail to see how you can merge two chains and >> count liberties in O(1). > > Merging would be a simple OR operation. Counting can be done, for example, > with some kind of binary search. Counting the bits set has been well > researched and many different algorithms exist. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Isaac, I implemented about 6 way to track liberties, a couple years ago, and measured the running performance, and by far the best is also the simplest: keep an array of liberties for each chain, and do a simple linear search. This may seem slow, but it has a couple real advantages. First, it works with the cache to maximize locality. Second it is very simple. Michael Wing > > Many Faces also counts real liberties, and is quite fast enough. > > > > > > I can confirm, with a bit of optimization, counting real liberties is > > > only marginally slower than counting pseudo-liberties. So there's > > > really no benefit that I can see from using pseudo liberties. > > > > > > Mark > > > > > > > > When John Tromp and I were thinking about these things in 2007 we > > > > decided to switch to counting real liberties instead of > > > > pseudo-liberties. Someone (Rémi?) told us that in the end the > > > > performance difference wasn't very large, and we verified this. > > > > > > > > Álvaro. > > > > > > Thanks. What is a fast way to track liberties? > > I thought about bit arrays. Merging to groups would take O(1), counting > takes O(1)-ish, and memory required would be small. > > Of course I could also use STL's "set" structure, but I found it to be > quite slow - it implements a set using a RB-tree. This was actually the > reason I switched to pseudo libs. > > -ibd. > -- > Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 > ___ > 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] 19x19 MC improvement
Eric Boesch This is probably massive overkill, but one of the most successful techniques for multi-parameter optimization is Taguchi methods. http://en.wikipedia.org/wiki/Taguchi_methods However, in my experience, starting with the decisions that make the biggest difference, and then adding in the next-biggest decision, and so on, usually gets close enough to optimal. In my cgbg performance tests, most reasonable decisions affect total program performance by a factor of 2 at most, which translates to 1 rank at most. Likewise, I doubt that tweaking of existing MC parameters will bring more than 1 rank. Further improvement will require new ideas. Michael Wing > By the way, does anybody know of any nifty tools or heuristics for > efficient probabilistic multi-parameter optimization? In other words, > like multi-dimensional optimization, except instead of your function > returning a deterministic value, it returns the result of a Bernoulli > trial, and the heuristic uses those trial results to converge as > rapidly as possible to parameter values that roughly maximize the > success probability. The obvious approach is to cycle through all > dimensions in sequence, treating it as a one-dimensional optimization > problem -- though the best way to optimize in one dimension isn't > obvious to me either -- but just as with the deterministic version of > optimization, I assume it's possible to do better than that. It might > be fun problem to play with, but if good tools already exist then it > wouldn't be very productive for me to waste time reinventing the > broken wheel. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Triple-Ko Detection
Michael,
Your code works just fine as far as it is concerned,
provided that the board already prevents simple-kos,
and detects 2 passes as end of game and that you
repeat the triple ko twice. This is your code:
if(move[n-1] == move[n- 7] &&
move[n-2] == move[n- 8] &&
move[n-3] == move[n- 9] &&
move[n-4] == move[n-10] &&
move[n-5] == move[n-11] &&
move[n-6] == move[n-12])
{ triple ko }
However if you play a triple ko once (6 moves), then
play away, then play the triple ko again, it will not
be detected.
The following code will detect triple ko the first
time. This requires that ko locations be kept along
with the move locations. If there is any form of undo,
then the ko info is already being kept.
if(move[n ] == ko[n-3] &&
move[n-1] == ko[n-4] &&
move[n-2] == ko[n-5] &&
move[n-3] == ko[n-6])
{ triple ko }
Michael Wing
> Michael Williams:
>
> You might be speaking in general terms, I'm talking about a
> specific test for full-board repetition due to triple ko.
> In this case the sequences that you are comparing would be
> the same length. So the test would look something like this
> (forgive me if I screw up the indexes):
> if (move[n-1]==move[n-7] && move[n-2]==move[n-8] &&
> move[n-3]==move[n-9] && move[n-4]==move[n-10] &&
> move[n-5]==move[n-11] && move[n-6]==move[n-12])
> {
> // We have seen this board before
> // Let's abort the playout and score it as-as.
> }
> Note that I'm only talking about this in the context of
> playouts, so it is ok if a position repeated and this test
> didn't catch it. This is just a possible way to shorten the
> playouts. I haven't tried this to see if it matters, I'm
> just thinking out loud here.
> The question is, does the test above ever cause a
> false-positive? In other words, is the first comment line
> ever incorrect?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Jacques, (Offline) Are you saying that you copy the whole board for each move, when you have a "stack of boards"? Thanks, Michael Wing > Well, every implementation is different. In its slowest > mode, my board stores information about neighbor stones > in each cell. It has a stack of boards and each board has > a pointer to its parent. In that mode superko can be > detected. There is also a faster mode for MC playouts > that does not support superko. But it could also be > possible to maintain a stack of previous hashes i.o. > complete boards, that would not be very expensive. > > Another cost is undo. Superko requires undo, unless > > you want store a hash value with each chain of stones. > > I am not sure exactly what undo costs, but lets say > > 5% to 10%. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Jacques Basaldúa, I say that adding superko adds 6% or so for 2 reasons. About 2% is adding it to the hash table. About 4% is computing the zobrist hash, which is mainly used for superko. Another cost is undo. Superko requires undo, unless you want store a hash value with each chain of stones. I am not sure exactly what undo costs, but lets say 5% to 10%. I do local analysis, so I pay for undo anyways. But, if you were doing MC only, then you could go 5% to 15% faster if you remove superko checking and undo. Michael Wing > Michael Wing wrote: > > > In my program (which implements undo), the cost of > > for suicide detection is around 1%, which means it > > would lose 1.5 ELO points. > > In programs that somehow maintain lists of legal moves > or even probability distribution functions over the legal > moves, avoiding suicide is free. I fact, adding the > suicide move to the list would cost. > > > On the other hand detecting superko costs more like > > 6% or so, which costs 9 or more ELO. So a benefit > > of 1 ELO for doing superko right may not be worth > > the cost. > > I guess you mean a bullet proof test from the beginning > of the game. I only test the last 7 moves (if enabled, > it can also be disabled) and that does not cost much. > > The reasons why I use 7 moves are 2: > > * I have never found among strong players a need for > repetition other that triple ko and double ko on a > group with no eyes. (Both are 6 moves long.) My point > is: If the program is so weak that it does silly > repetitions, improve something else. If it is so strong > that it has the same problems as strong humans, detect > superko. > > * My hash system can use only half of the hash (32 bits) > and detect the collision with probability 1. (Because of > the properties of the keys, you need at least 8 keys > for a combination of keys giving zero.) > > A reason I can figure for ignoring repetition in the > playouts is: If the playouts are random, it won't happen > much anyway. The probability of a repetition of 6 random > moves is too small to care about. But in real play it is > frequently a fight for the game. The player forced to > avoid the repetition will resign if it is about the > life of a big group. > > > 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] Suicide question
Don, I forgot to mention one additional consideration. My top-level driver does check rules for suicide and superko, even though the engine may or may not. At the top-level, if the engine chooses a bad move, then the driver will use the next best move instead. (Repeat as necessary) So it will not lose by rules and (hopefully) the second best move move is still reasonable. However, I am talking about the actual performance of my engine when doing random playouts for MC. I do know the ELO cost of detection, using a valid heuristic. The real ELO benefit of knowing the validity of moves is just a wild guess. Yet, I stand by my analysis. Michael Wing > I think you are off on the relative importance of superko and suicide > and it seems that your values are rather arbitrary - just made up. > > First of all, we are only talking about detection in the play-outs, not > in the tree search portion. > > In the play-outs, it is very important to avoid moves that are nearly > always horrible. This clearly includes suicide. I don't know why > you estimate that it is worth only 1 elo weakness. > > If you implement a program that doesn't understand superko, you will > occasionally lose a game due to this - but most of the time it won't be > an issue. Nevertheless, it happens often enough that it is probably > worth a few ELO points because your program will LOSE on CGOS if it > fails to realize that it is about to play superko.I am guessing that > this would amount to perhaps 20 ELO, I'm just guessing. > > HOWEVER, if your program simply avoids superko moves, without > understanding them, it probably subtracts almost nothing from your > rating. In monte carlo UCT you can STILL include positional superko > in the tree search and get 99% of the benefit and simply leave this out > of the random play-outs.Including PSK in the play-outs will have no > measurable impact on the quality of the play-outs. > > My conclusion is different than yours. If you leave PSK out of the > play-outs you lose NOTHING that is likely to be measurable. If you > let your program play suicide moves in the play-outs, I'm quite you > lose many ELO rating points (if speed isn't a consideration.) > > Of course speed IS a consideration too and that can change the > formula. In your program there is not question that you should detect > suicide and not play it, because this is only 1.5 percent for you. But > evidently some program benefit substantially (in speed) by accepting > suicide. > > - Don > > > > > > [EMAIL PROTECTED] wrote: > > We can use math to shed some light on the topic: > > > > * Assume that doubling the speed of a machine > > increases the rank of a program by 100 ELO, > > as Don has previously concluded. > > > > * Then we have the following table of approximate > > costs, which comes from the equation y = 100 * 2^x > > cost -> lost ELO > > > >1% -> 1.5 ELO > >2% -> 3.0 ELO > >3% -> 4.5 ELO > >4% -> 6.0 ELO > >5% -> 7.5 ELO > >6% -> 9.0 ELO > > 10% -> 15.0 ELO > > > > * In my program (which implements undo), the cost of > > for suicide detection is around 1%, which means it > > would lose 1.5 ELO points. > > > > * If I wanted to know whether it was worth it, I would > > want to measure the ELO benefit by making better > > decisions concerning suicide. It is a small but > > real amount, probably at least 1 ELO (using my > > finger in the breeze). > > > > * Thus the issue of whether you detect suicide may > > be a complete wash. > > > > * On the other hand detecting superko costs more like > > 6% or so, which costs 9 or more ELO. So a benefit > > of 1 ELO for doing superko right may not be worth > > the cost. > > > > Conclusions > > > > * The effect of suicide detection is *very* small in > > the scheme of things, and is probably not worth > > arguing over. Superko is also small, but might be > > worth a tiny amount of effort. > > > > * Some kind of study to measuring the ELO cost of bad > > suicide and ko decisions would be useful. > > > > * I plan to detect both suicide and superko on principle, > > confident that it doesn't make much difference. > > > > Michael Wing > > > > Don Dailey <[EMAIL PROTECTED]> said: > > > > > >>> There are two reasons to consider suicide and its detection.. > >>> > >>> 1) Some rule sets allow suicide.
Re: [computer-go] Suicide question
Mark, Don did say that doubling the speed of a machine is 100 ELO. See the thread at http://www.mail-archive.com/computer-go@computer-go.org/msg05358.html I believe that beating someone 2:1 is 100 ELO. So, if ignoring suicide is at most 1 ELO, then it doesn't matter. Michael Wing P.S. I should have used the equation y = 100 * log2(x) > I have a few question-marks here. > > First, did Don really say that a doubling of the speed gains 100 ELO? > Or did he say adding a ply would add 100 ELO? There's a big difference. > > Secondly, you say the ELO benefit for not playing suicide is 1. > Admittedly you say you used your wet finger in the breeze. Thinking > more about it I'd say Don is right, not playing suicide should be a > considerable gain. I'd say that (putting my wet finger up) a random > player that doesn't play suicide beats a random player that does 2:1. > What's that in ELO? 100 points? Should be easy to verify. > > Conclusions > > * The effect of suicide detection is *very* small in > > the scheme of things, and is probably not worth > > arguing over. Superko is also small, but might be > > worth a tiny amount of effort. > > > > * Some kind of study to measuring the ELO cost of bad > > suicide and ko decisions would be useful. > > > > * I plan to detect both suicide and superko on principle, > > confident that it doesn't make much difference. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
We can use math to shed some light on the topic: * Assume that doubling the speed of a machine increases the rank of a program by 100 ELO, as Don has previously concluded. * Then we have the following table of approximate costs, which comes from the equation y = 100 * 2^x cost -> lost ELO 1% -> 1.5 ELO 2% -> 3.0 ELO 3% -> 4.5 ELO 4% -> 6.0 ELO 5% -> 7.5 ELO 6% -> 9.0 ELO 10% -> 15.0 ELO * In my program (which implements undo), the cost of for suicide detection is around 1%, which means it would lose 1.5 ELO points. * If I wanted to know whether it was worth it, I would want to measure the ELO benefit by making better decisions concerning suicide. It is a small but real amount, probably at least 1 ELO (using my finger in the breeze). * Thus the issue of whether you detect suicide may be a complete wash. * On the other hand detecting superko costs more like 6% or so, which costs 9 or more ELO. So a benefit of 1 ELO for doing superko right may not be worth the cost. Conclusions * The effect of suicide detection is *very* small in the scheme of things, and is probably not worth arguing over. Superko is also small, but might be worth a tiny amount of effort. * Some kind of study to measuring the ELO cost of bad suicide and ko decisions would be useful. * I plan to detect both suicide and superko on principle, confident that it doesn't make much difference. Michael Wing Don Dailey <[EMAIL PROTECTED]> said: > > There are two reasons to consider suicide and its detection.. > > > > 1) Some rule sets allow suicide. In such a rule set a suicide can > > be the best move because it can be a huge ko threat. > > > > 2) As David Fotland has pointed out many times, when competing > > under rules that allow suicide, some programs will do one just to > > see if your program refuses to play when you detect its suicide. > But there are very few arguments for putting suicide in the play-outs. > You can still design your program to accept and even play suicide > without putting these moves in the play-outs. > > The play-outs are imperfect by nature - they try to take a statistical > sample of many possible ways the game might proceed.The path to > improve the quality of this statistical sample is to not play moves that > represent very UNLIKELY continuations.Adding these moves randomly to > the play-outs doesn't improve it's ability to statically measure the > likely outcome. > > For instance since is "legal" to resign, we could randomly include this > possibility in the play-outs, but it would not increase the resolving > power of the play-outs. > > Moving into 1 point eyes is also legal, but virtually all Monte Carlo > programs forbid this as it's well known to be incredibly stupid in the > vast majority of cases.But in some rare cases it is actually good - > but we still would not want to add it to our play-outs. > > Because of the 1 point eye rule, suicide in the play-outs probably isn't > THAT bad.You are probably only suiciding a group that is already > dead - but you are weakening the play-outs. It may be worth it if you > get enough speed in return. > > In my program I am always looking for an excuse to veto moves that are > obviously bad. If I had such an obvious class of position like > suicide, I would jump on the opportunity to remove them from the play-outs! > > - Don > > > > > > > > Cheers, > > David > > > > > > > > On 16, Jan 2008, at 5:52 AM, Don Dailey wrote: > > > >> I think suicide is insane myself. But I think the reason programs > >> might use it is only for a speedup - it's faster with some > >> implementations to allow suicide even though it makes the games longer. > >> > >> Of course you are right about point B.If suicide is illegal in the > >> actual game, there can be no point in allowing it in the play-outs. > >> It's almost certainly wrong to allow it in the play-outs even if you are > >> playing by suicide rules - a lot of work has gone into finding good > >> moves in the play-outs and this would be one of the prime candidates for > >> removal! > >> > >> - Don > >> > >> > >> Jacques Basaldúa wrote: > >>> Gian-Carlo Pascutto wrote: > >>> > >>>> Multi-stone suicide is allowed, single stone not. > >>> > >>> I hadn't even considered suicide.(It would be a major change for me, > >>> as neither my Gui nor my board system allow such moves.) > >>> > >>> The
Re: cgbg, was [computer-go] On average how many board updates/sec can top Go programs do these days?
terry mcintyre <[EMAIL PROTECTED]> said: > > www.swcp.com/~wing/cgbg > > I visited the www page, and the combination of with > very long lines does not work well at all. Tried both firefox > and IE. prevents the browser from wrapping the text to > fit the display page. Thanks. Reformatted the text. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
cgbg, was [computer-go] On average how many board updates/sec can top Go programs do these days?
Gian-Carlo Pascutto <[EMAIL PROTECTED]> said: > I wrote my program to track psuedoliberties because this is very fast > and I thought I could take a lot of shortcuts and early exits when I had > to know the real amount of liberties. Unfortunately the interesting > cases seem to be the ones that don't allow for the shortcuts. I am now > convinced designing the program with psuedoliberties was a mistake. My friends and I have just finished an alpha version of a code generator that compares go board implementations in a wholistic manner. The results are complicated, but pseudo-liberties work reasonably well, too. See below. Michael Wing www.swcp.com/~wing/cgbg --- The Critters Go Board Generator Michael Wing January 15, 2008 Ive wanted to develop a fast go board for many years, and have spent the last few months helping write a go board generator to figure out what fast means. The current code was inspired in part by discussions on the computer-go email. CGBG generates many go board implementations: 4 methods of tracking liberties, 3 methods of tracking adjacent groups, 2 methods for mapping a location to a chain. It also can generate code with and without borders, and for many board sizes. It generates ptest, which runs 2 performance tests: filling the board to 90% full (which resembles Monte Carlo readouts) and ladder reading (which resembles local board analysis). It generates ftest, which runs many functional unit tests. Caveats. CGBG was intended to create apples-to-apples comparisons, but does not strictly do so. First, the current implementations are solid, but not necessarily optimal. For example, union-find uses classic 2-pass path compression, rather than the 1-pass version in libego. Also, Many other optimizations (loop unrolling) are not implemented. This is alpha code. Many ideas are just sketches. There is a lot of cruft. Main conclusions: * GnuGo data structures are pretty darn good, even for Monte Carlo simulation. I had hoped to find a linked-list data structure, but didnt. * Behavior at 9*9 can be very different than behavior at 19*19. * The complex nature of cache and processor architecture makes it very hard to predict the effect of any data structure decision. Trying it out empirically is the only way. * Many reasonable implementations run within a factor or 33% or so of the best. Main conclusions for 19*19: * Using union-find is slower than changing the smaller chain, by a tiny amount. * Using arrays to track liberties is best for board analysis. * Using pseudo-liberties only is best for pure simulation. * Using arrays to track adjacent groups is best for board analysis. * Using search-only to track adjacent groups is best for pure simulation. * For a program that does both Monte Carlo and local board analysis, I would use arrays to track both liberties and adjacencies. * For a program that does no local analysis, I would use pseudo liberties only. Other Notes * CGBG precomputes board and hash data, so they can be stored in read-only memory and do not need to be initialized. This can be used as an example, or cut and paste into other implementations. * This implements positional superko checking (though not tested), which GnuGo and libego do not. Situational superko checking is sketched, but not complete. * The play() routine uses gotos. The conventional technique of deciding the status of a move and then using a switch statement is about 1 percent slower. The code is written in Ruby, and currently generates C code for gcc under cygwin. It also needs to link in SFMT. It is available at www.swcp.com/~wing/cgbg To Use * ./cgbg * make * ./ftest * ./ptest I would appreciate any feedback. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
> > With 8 hashes per position, the chance of two different boards > > producing a different set of hashes but > > the same canonical hash is greater than 1/2^64, because there will be > > a bias in the choice of canonical > > hashes - toward numerically lower numbers, for instance. > > > > I think. > > More importantly, how does it differ from 8/2^64 = 1/2^61? If hash collisions are worrisome, you can always use 96-bit or 128-bit hashes. Modern x86s can do 8 parallel loads, adds, subtracts, or stores of 16-bit numbers in one step using SIMD, just like Antti Huima suggests in http://fragrieu.free.fr/zobrist.pdf. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Tracking Liberties in GnuGo?
I have been dabbling with the liberty tracking code in GnuGo, and I would like to know whether it is considered state-of-the-art, or simply an example of solid code. I have found a couple other ways of tracking the liberties, and I would like to know whether they are worth pursuing. Thanks, Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tweaking the Pseudo Liberty Code
Jason,
I realize that I was looking at the IsOneSum() constructor,
which had the array lookups. My bad. I just didn't
understand how it worked.
-- M
> On Sat, 2007-11-24 at 10:36 -0700, [EMAIL PROTECTED] wrote:
> > > Since 160,000 < 2*(19*19)^2, a value well below the various possible
> > > sums of squares, I have to ask what additional work you've done to
prove
> > > that the overlap doesn't cause problems?
> >
> > 160,000 is greater than (19 * 19 + 1)^2, so the linear term does
> > not interact with the quadratic term at all. This is not a problem.
>
> I don't understand this logic, but...
>
> > The unit test code in the previous email tests all possible
> > combinations of up to 4 liberty values, so it has been
> > empirically verified.
>
> I missed that unit test in the sample code. Sorry.
>
> > > PS: Did you see the solution by Eric Boesch that used bit masking and
no
> > > random numbers?
> >
> > I saw it, but I didn't understand it. However, since it does array
> > references inside a for loop, it probably does at least as many
> > memory accesses as this solution.
>
> Below is the code Eric posted for his test. There are no loops or
> memory references.
>
> bool operator()(uint64_t codeSum) const {
> return codeSum < mThreshold && !((codeSum/(codeSum/mDivisor)) & mMask);
> }
>
> Note that there are two divisions, but these can be eliminated with some
> creativity:
>
> bool operator()(uint64_t codeSum) const {
> switch(codeSum>>XXX){
> case 1:
>return true; // 64 bit code
>return !(codeSum & mMask); // 32 bit code
> case 2:
>return !(codeSum & mMaskLeftOne);
> case 3:
>return ((codeSum&altMaskLeftOne)>>1) == (codeSum&altMask); // 64 bit
>return (((codeSum&altMaskLeftOne)>>1) == (codeSum&altMask))
> && !(codeSum & altMaskLeftTwo); // 32 bit
> case 4:
>return !(codeSum & mMaskLeftTwo);
> default:
>return false;
> }
> }
>
> where
> mMask = 0b 110 110 110 110...110 11;
> mMastLeftOne = mMask<<1 | 1;
> mMastLeftTwo = mMask<<2 | 3;
> altMask = 0b 001 001 001 001...001 00;
> altMaskLeftOne = altMask<<1;
> altMaskLeftTwo = altMask<<2;
>
> I know the definition of mMask and altMask isn't legit C, but hopefully
> the formatting gives the right idea. Eric gave real code that covers
> most of this. All variable names, when matching Eric's, would use the
> definition from his code.
>
> The two bits of padding on the right, that I previously suggested, can
> be eliminated with this alternate methodology, reducing the minimum
> number of bits from 31 to 29, but that still means that overflow is
> possible... Creating more strict tests on 32 bit machines. My code
> sample gives some duplicate lines of code, the comments indicate which
> line is for 32 bit and which is for 64 bit.
>
> ___
> 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] Tweaking the Pseudo Liberty Code
Jason House <[EMAIL PROTECTED]> said: > > On Sat, 2007-11-24 at 08:38 -0700, [EMAIL PROTECTED] wrote: > > To follow up on this thread, I have been playing with > > psuedo liberties a bit, and here is my solution. > > > > * I use 2 vectors of values. The first is used for > > storing the pseudo liberty values. The second lists has > > all 1*, 2*, 3*, and 4* the values, which are sorted. > > Binary search will show whether the value is for > > a single liberty or not. Division is still a pretty > > expensive op. This uses 2 additional memory lookups. > > I assume you mean 2 additional look-ups verses storing just the 1x > values as opposed to other methods. Yes. I use 2 additional lookups, rather than 2 divides or the bit masking. > > * For liberty values, I use the following equation: > > values[i] = 25000 + (16 * (i+1)) + ((i+1) * (i+1)); > > Some bits are constant, some are linear, and some > > are quadratic, which guarantees that the sum of > > up to 4 values will only be in the set if they > > are from the same liberty. I have more confidence > > in an equation than in random numbers. > > Since 160,000 < 2*(19*19)^2, a value well below the various possible > sums of squares, I have to ask what additional work you've done to prove > that the overlap doesn't cause problems? 160,000 is greater than (19 * 19 + 1)^2, so the linear term does not interact with the quadratic term at all. This is not a problem. The unit test code in the previous email tests all possible combinations of up to 4 liberty values, so it has been empirically verified. > If 160,000 was replaced with a number greater than 4*(19*19)^2=521,284, > I'd have no worries. Of course, if you used 521,285, the 250,000,000 > would need to be at least 752,735,541... yielding overflow of 32 bit > values with only 6 liberties. Using larger constants will work just fine, too. The problems with overflow are (in practice) no better or worse than using the smaller constants. In both cases, the program needs to use int64 for the pseudo-liberty value or use an additional pseudo-liberty count. > PS: Did you see the solution by Eric Boesch that used bit masking and no > random numbers? I saw it, but I didn't understand it. However, since it does array references inside a for loop, it probably does at least as many memory accesses as this solution. -- Michael Wing > > * These numbers are small enough that they fit in > > 32 bits. Unfortunately they are so large that > > the sum of say 20 liberties takes more than 32 bits. > > One solution is to use 64 bits for pseudo liberties. > > Another solution is keep a count of PLs, and also > > a 32 bit unsigned PL value, igoring overflow, and > > only check the PL value when the PL count is less > > than 5. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Tweaking the Pseudo Liberty Code
To follow up on this thread, I have been playing with
psuedo liberties a bit, and here is my solution.
* I use 2 vectors of values. The first is used for
storing the pseudo liberty values. The second lists has
all 1*, 2*, 3*, and 4* the values, which are sorted.
Binary search will show whether the value is for
a single liberty or not. Division is still a pretty
expensive op. This uses 2 additional memory lookups.
* For liberty values, I use the following equation:
values[i] = 25000 + (16 * (i+1)) + ((i+1) * (i+1));
Some bits are constant, some are linear, and some
are quadratic, which guarantees that the sum of
up to 4 values will only be in the set if they
are from the same liberty. I have more confidence
in an equation than in random numbers.
* These numbers are small enough that they fit in
32 bits. Unfortunately they are so large that
the sum of say 20 liberties takes more than 32 bits.
One solution is to use 64 bits for pseudo liberties.
Another solution is keep a count of PLs, and also
a 32 bit unsigned PL value, igoring overflow, and
only check the PL value when the PL count is less
than 5.
-- Michael Wing
// --- code for initializing and checking pseudoliberties ---
package go_core_2;
import java.util.Arrays;
public class PseudoLiberties {
public static int values[] = new int[19*19];
public static int possible[] = new int[4*19*19];
static {
for(int i = 0; i < 19 * 19; i++) {
values[i] = 25000 + (16 * (i+1)) + ((i+1) *
(i+1));
}
for(int j = 0; j < 4; j++) {
for(int i = 0; i < 19 * 19; i++) {
possible[19 * 19 * j + i] = (j + 1) * values
[i];
}
}
Arrays.sort(PseudoLiberties.possible);
}
public static boolean atari(int liberties) {
int left = 0;
int right = possible.length - 1;
for(;;) {
if(left > right) {
return false;
}
int mid = (left + right) / 2;
if(liberties < possible[mid]) {
right = mid - 1;
continue;
}
if(liberties > possible[mid]) {
left = mid + 1;
continue;
}
return true;
}
}
}
// --- unit test code ---
package go_core_2_test;
import go_core_2.PseudoLiberties;
import java.util.Arrays;
import junit.framework.TestCase;
public class PseudoLibertiesTest extends TestCase {
public void testAtariBasic() {
// ensure that everything on the list is true
for(int i = 0; i < PseudoLiberties.values.length; i++) {
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 1));
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 2));
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 3));
assertTrue(PseudoLiberties.atari
(PseudoLiberties.values[i] * 4));
}
for(int i = 0; i < PseudoLiberties.possible.length; i++) {
assertTrue(PseudoLiberties.atari
(PseudoLiberties.possible[i]));
}
}
public void testAtariIndividuals() {
// ensure that all numbers not on the list are false
boolean problemFound = false;
for(int i = 0; i < 4; i++) {
int slot = Arrays.binarySearch
(PseudoLiberties.possible, i);
if(PseudoLiberties.atari(i) != (slot >= 0)) {
System.out.println("pairs failed on " + i);
problemFound = true;
}
}
assertFalse(problemFound);
}
public void testAtariPairs() {
// ensure that all pairs of numbers work
boolean problemFound = false;
for(int i = 0; i < PseudoLiberties.values.length; i++) {
for(int j = 0; j < PseudoLiberties.values.length;
j++) {
int liberties = PseudoLiberties.values[i]
+ PseudoLiberties.values[j];
if(PseudoLiberties.atari(liberties) != (i ==
j)) {
System.out.println("pairs failed
on " + i + ","
Re: [computer-go] Re: compiler optimizations
Because many optimizations take exponential or worse time to figure out if they apply. This means that the sun would explode before your compile would finish. Yes, compilers will get more sophisticated over time. No, they will not replace any algorithms or data structures. Michael Wing > Why should a super-sophisticated compiler with algebraic type > inference not be able to do this one day? > > On Nov 22, 2007 12:36 AM, Dave Dyer <[EMAIL PROTECTED]> wrote: > > > > Arguments about the quality of compiler optimizations vs. hand coding > > are pointless, because programmers optimize programs in ways that compilers > > are (correctly) forbidden to do; by changing the algorithm. > > > > For example, if I happen to know "x" will always be an integer > > from 0 to 359, I can replace sin(x) with a table lookup. No compiler > > can ever do that, even if I include assert(x>=0 && x<360) in the code > > somewhere (which would be a good idea even if I "know" it). > > > > ___ > > 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] Drunken sailor on payday
> > No compiler will ever do *all* of the optimizations > > that are possible, because most optimizations are > > NP-complete or even much worse. For example the > > equivalance of boolean expressions is NP-complete. > > Some potential optimizations (such as replacement > > of data structures) may not even computable. > > This is why humans must choose the algorithms and > > data strucures. > > > > Compilers are very good at *small, local optimizations*, > > such as putting variables in registers, common > > sub-expression elimination, and choosing the fastest > > instructions. Compilers almost always > > outperform humans on these tasks because compilers > > consistently try every trick they know, and they > > don't get tired. > > > > Even way back in the 1970s, studies showed that > > optimizers consistently outperformed humans on > > these tasks, and back then, many people > > still practiced doing assembler regularly. > > > > Today, performance combines programmer and compiler > > intelligence. Neither can replace the other. > > Please use both. > So this seems to support the idea that C code is potentially faster > than hand-coded assembly, because the more complicated optimizations > can be done by the programmer in C while the optimizations better > suited to a computer are done by the compiler. Although it would also > be possible to hand-code in assembly and then run a program to > optimize it, but then it seems like there is no advantage over C. As > far as I can tell, the optimizations that a compiler can't do are > higher-level optimizations that can be done in C and wouldn't require > the programmer to write assembly, or am I wrong about this? To extend your thought: well-written code in any HLL (like C, C++, Java, Fortran, D, etc.) will in-general out-perform assembler, because the programmer can do better algorithms and data structures, and compilers are better at assembler. There is one major exception. I have seen several apps where programmers wrote a few functions in assembler for speed, for example to use the SIMD instructions. But, that was only a few functions out of an entire app. Data structures and algorithms are very important. Given the success of MC and UCT, there seems to be a lot of enthusiasm for performance. But, even improving performance by a factor of 10 by using assembler will not make MC and UCT play professional level go on 19*19. We still need to find much better algorithms and data structures. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
> What's to say that a computer program can't code assembly better than > any human possibly could? There are a ton of tasks that computers do > thousands of times better than humans. I think it makes perfect sense > that code written in C can execute faster than human-written assembly > code. No compiler will ever do *all* of the optimizations that are possible, because most optimizations are NP-complete or even much worse. For example the equivalance of boolean expressions is NP-complete. Some potential optimizations (such as replacement of data structures) may not even computable. This is why humans must choose the algorithms and data strucures. Compilers are very good at *small, local optimizations*, such as putting variables in registers, common sub-expression elimination, and choosing the fastest instructions. Compilers almost always outperform humans on these tasks because compilers consistently try every trick they know, and they don't get tired. Even way back in the 1970s, studies showed that optimizers consistently outperformed humans on these tasks, and back then, many people still practiced doing assembler regularly. Today, performance combines programmer and compiler intelligence. Neither can replace the other. Please use both. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Maximum number of strings
I have independently verified the MSP (maximum number of living strings on a board) results for board sizes up to 16 that Youhei Yano created and that Hiroshi Yamashita reported on in this mail group about a month ago. Youhei Yano's original results are at: http://www.yss-aya.com/msp1.jpg http://www.yss-aya.com/msp2.jpg They contain 2 typos, though the diagrams are all correct. My results show answers up to board size 18 and are listed at the bottom of this email. My results include maxes and examples for board sizes 17 and 18 which, to my knowledge, were previously unknown. --- My program can also solve board size 19, but not on my computer (a 1.66 gHz Intel Duo with 1 gig of RAM). I would need a computer with 64-bit mode, more than 2.5 gig of RAM, 30 gig of free disk space, and 3 to 4 days of uninterrupted compute time. The hard part is that the program allocates 2 arrays of about 1.2 gig each. It saves 19 copies of these arrays to disk, as intermediate results to reconstruct the example board. My program is written in Java and is 360 lines long. It could easily be rewritten in C, though that would not change the machine requirements at all. It uses dynamic programming to keep track of the most stones (actually fewest liberties) that are possible on one side of a barrier, as it moves the barrier. If anyone has access to a machine that can run this program, please let me know. Thank you, Michael Wing board size: 2 max: 2 time: 63 milliseconds .. Wb board size: 3 max: 6 time: 15 milliseconds .w. wbw b.b board size: 4 max: 12 time: 47 milliseconds b.bw wbw. .wbw wb.b board size: 5 max: 18 time: 31 milliseconds .w.wb wbwb. b.bwb wbw.w .wb.b board size: 6 max: 26 time: 62 milliseconds ..b.bw wbwbw. bw.wbw .bwb.b bwb.bw w.wbw. board size: 7 max: 37 time: 156 milliseconds b.bwb.b wbw.wbw .wbwbw. wb.b.bw .wbwbw. wbw.wbw b.bwb.b board size: 8 max: 48 time: 438 milliseconds .w.wbw.w wbwb.bwb b.bwbw.. wbw.wbwb .wbwb.bw wb.bwbw. .wbw.wbw wb.bwb.b board size: 9 max: 61 time: 1390 milliseconds .w.wbw.wb wbwb.bwb. b.bwbw.wb wbw.wbwb. .wbwb.bwb wb.bwbw.w bwbw..bwb ..wbwbwb. bwb.bw.wb board size: 10 max: 76 time: 4609 milliseconds b.b.bwb.bw wbwbw.wbw. .w.wbwb.bw wbwb.bwbw. b.bwbw.wbw wbw.wbwb.b .wbwb.bwbw wb.bwbw.w. .wbw.wbwbw wb.bwb.b.b board size: 11 max: 92 time: 16265 milliseconds b.bwb.bw.wb wbw.wbwb.b. ..bwbw.wbwb wbwb.bwbw.w bw.wbwb.bwb .bwbw.wbwb. bwb.bwbw.wb w.wbwb.b.bw bwb..wbwbw. .bwbwbw.wbw bw.wb.bwb.b board size: 12 max: 109 time: 55453 milliseconds .w.w.w.wb.bw wbwbwb.bwbw. b.b.bwbw.wbw wbwbw.wbwb.. .w.wbwb.bwbw wbwb.bwbw.wb b.bwbw.wbwb. wbw.wbwb.bwb .wbwb.bwbw.w wb.bwbw..bwb .wbw.wbwbwb. wb.bwb.bw.wb board size: 13 max: 129 time: 187203 milliseconds b.b.bwb.bwb.b wbwbw.wbw.wbw .w.wbwb.bwbw. wbwb.bwbwb.bw b.bwbw.w.wb.b wbw.wbwbwb.bw .wbwb.b.bwbw. wb.bwbwbw.wbw .wbw.w.wbwb.b wb.bwbwb.bwbw .wbwb.bwbw.w. wbw.wbw.wbwbw b.bwb.bwb.b.b board size: 14 max: 149 time: 623406 milliseconds ..bwb.bw.wbw.w wbw.w.wbwb.bwb b.bwbwb.bwbw.. wbwb.bwbw.wbwb .w.wbw.wbwb.bw wbwb.bwb.bwbw. b.bwbw.wbw.wbw wbw.wbwb.bwb.b .wbwb.bwbw.wbw wb.bwbw.wbwbw. bw.w.wbwb.b.bw .bwbwb..wbwbw. bwb.bwbwbw.wbw w.wbw.wb.bwb.b board size: 15 max: 172 time: 2073110 milliseconds b.b.b.bw.wbw.wb wbwbw.wbwb.bwb. .w.wbwb.bwb.bwb wbwb.bwbw.wbw.w b.bwbw.wbwb.bwb w.w.wbwb.bwbw.. bwbwb.bwbw.wbwb .b.bwbw.wbwb.bw bwbw.wbwb.bwbw. w.wbwb.bwbw.wbw bwb.bwbw.wbwb.b .bwbw.wbwb.b.bw bw.wbwb..wbwbw. .bwb.bwbwbw.wbw bw.wbw.wb.bwb.b board size: 16 max: 196 time: 7099422 milliseconds .w.wbw.wbw.w.w.w wbwb.bwb.bwbwbwb b.bwbw.wbwb.b.b. wbw..bwbw.wbwbwb .wbwbwb.bwbw.w.w wb.bw.wbwb.bwbwb bwb.bwbw.wbwb.b. ..wbwb.bwbw.wbwb bwbw.wbwb.bwbw.w wb.bwbw.wbw
