Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Can you give some more info about experimental setup and the algorithms you used? On Thu, Apr 9, 2009 at 01:42, w...@swcp.com 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.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, w...@swcp.com 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
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, w...@swcp.com 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.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, w...@swcp.com wrote: Isaac, I implemented about 6 way to track liberties, a couple years ago, and measured the running performance, and by far the
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
David Fotland wrote: Yes, I walk both chains looking for duplicates. This is quite fast if done efficiently, since group merging is rare enough. I found keeping the liberty arrays to be slower since they are big, so there is more copy overhead in the UCT tree, and they are not cache friendly. Leela also just keeps a liberty count. When two strings are merged, it walks the shortest chain and looks for empty neighbours that are shared. This is very simple, and very fast. -- GCP ___ 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?
On Wed, Apr 8, 2009 at 01:13, Darren Cook dar...@dcook.org wrote: Linked lists have a terrible cache behaviour: every pointer (or index) dereference has a nearly 100% chance of causing a cache miss. ... It's quite easy and efficient to put all lists (cyclic, linked in one direction) of liberties (on one 19x19 board) into 4*19*19*sizeof (vertex) array. If vertex is int32 then it is about 1.5 kB. Hi Lukasz, (private reply, but reply to the list is fine by me) Do you have some code demonstrating the above idea? It sounds interesting, but I cannot grasp what the data and algorithm look like. 4*19*19*4 is around 5.5 kB On 9x9 it will be less than 1.5 kB My mistake. Are you still interested? Darren -- 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/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Do you have some code demonstrating the above idea? It sounds interesting, but I cannot grasp what the data and algorithm look like. 4*19*19*4 is around 5.5 kB On 9x9 it will be less than 1.5 kB Are you still interested? My own method is a large pre-allocated pool of Chain objects, which use std::vector, or fixed-size arrays, to store liberties. So I'm using a lot more memory. If your idea actually works and is just as quick then of course I'm interested. Darren -- 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/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Wed, Apr 8, 2009 at 09:12, Darren Cook dar...@dcook.org wrote: Do you have some code demonstrating the above idea? It sounds interesting, but I cannot grasp what the data and algorithm look like. 4*19*19*4 is around 5.5 kB On 9x9 it will be less than 1.5 kB Are you still interested? My own method is a large pre-allocated pool of Chain objects, which use std::vector, or fixed-size arrays, to store liberties. So I'm using a lot more memory. If your idea actually works and is just as quick then of course I'm interested. The problem is similar to the problem of storing lists of stones in one group. For a reference you can take a look for a libego implementation: The file is in the spirit one class for all including unit tests, so it's big. But just ignore it and track chain_next_v http://github.com/lukaszlew/libego/blob/00264d126ef6aa909dd7f52a668e8fe33e62aeb4/ego/board.cpp chain_next_v is essentially a map vertex - next_vertex (vertex is board location). chain_next_v implements cyclic linked lists. The trick is that it is implemented as an array of size 19*19*sizeof(vertex). This is possible because one vertex can be always only in one group. Now merging groups is as simple as crossing the lists (line 500). If you have any questions so far, go ahead and ask :) Now the liberties. One liberty can be in many groups. But in only as many as 4. Let's call links between neighboring vertices pseudoliberties. Now we can create a structure similar to chain_next_v that track all pseudo-liberties of a group. It would be again map implemented as an array indexed by vertex and direction (N,W,S,E). Now when you merge you just go over this list and throw away duplicates. This can be done in linear time using another map-array vertex - bool. That will have info whether particular liberty (vertex without direction) was already in visited. Hope this helps :) Lukasz Darren -- 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/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
lot more memory. If your idea actually works and is just as quick then of course I'm interested. ... For a reference you can take a look for a libego implementation: Ah, so you already use this idea in libego? That is all I need to know, because, unless something has changed, libego does light playouts faster than any other program. (?) Darren -- 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/
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
... For a reference you can take a look for a libego implementation: Ah, so you already use this idea in libego? libego uses this idea only for list of stones in chain. list of liberties are not implemented. but I guess I will implement it sometime soon. That is all I need to know, because, unless something has changed, libego does light playouts faster than any other program. (?) I don't know about the speed of other programs. libego currently does 40-45 kpps / GHz. So if you have 3 GHz processor you will get around 130k playouts per second. Lukasz Lew ___ 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?
Hi Lukasz, I think I understand the way it is done for storing the stones; I do it exactly the same way. For the liberties: Does the index of the direction (NWSE) state where the chain is in respect to the liberty? So if you place a single stone on the board at position, you add 4 liberties and link them: - left of position, E - right of position, W - below of position, N - above of position, S Is that correct? I have another question. How do you efficiently track visited positions to avoid superko? I use zobrist hashing, but the memory it uses is quite big, and I think copying it from board to board takes a lot of time. Of course I don't do superko checks in the playouts, but in the UCT tree I have to check for it. Isaac Now the liberties. One liberty can be in many groups. But in only as many as 4. Let's call links between neighboring vertices pseudoliberties. Now we can create a structure similar to chain_next_v that track all pseudo-liberties of a group. It would be again map implemented as an array indexed by vertex and direction (N,W,S,E). Now when you merge you just go over this list and throw away duplicates. This can be done in linear time using another map-array vertex - bool. That will have info whether particular liberty (vertex without direction) was already in visited. Hope this helps :) Lukasz -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ 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?
On Wed, Apr 8, 2009 at 13:10, Isaac Deutsch i...@gmx.ch wrote: Hi Lukasz, I think I understand the way it is done for storing the stones; I do it exactly the same way. For the liberties: Does the index of the direction (NWSE) state where the chain is in respect to the liberty? So if you place a single stone on the board at position, you add 4 liberties and link them: - left of position, E - right of position, W - below of position, N - above of position, S Is that correct? Yep. I'm thinking about implementing it in libego with heavy playouts for demonstration. Maybe It will get libego some attention. :) I have another question. How do you efficiently track visited positions to avoid superko? I use zobrist hashing, but the memory it uses is quite big, and I think copying it from board to board takes a lot of time. Of course I don't do superko checks in the playouts, but in the UCT tree I have to check for it. I use zobrist hashing as well. But the random base is separated from board and shared so I don't copy it. I copy just a xor hash which is no more than 8 bytes per board. Isaac Now the liberties. One liberty can be in many groups. But in only as many as 4. Let's call links between neighboring vertices pseudoliberties. Now we can create a structure similar to chain_next_v that track all pseudo-liberties of a group. It would be again map implemented as an array indexed by vertex and direction (N,W,S,E). Now when you merge you just go over this list and throw away duplicates. This can be done in linear time using another map-array vertex - bool. That will have info whether particular liberty (vertex without direction) was already in visited. Hope this helps :) Lukasz -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ 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?
Łukasz Lew wrote: ... For a reference you can take a look for a libego implementation: Ah, so you already use this idea in libego? libego uses this idea only for list of stones in chain. list of liberties are not implemented. but I guess I will implement it sometime soon. You can find this idea in the GNU Go montecarlo board implementation, although with doubly linked lists, see for example http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c starting at line 43. This code is doing quite a lot of book-keeping to support tunable pattern-based heavy playouts, however, so it may be easier to start with a previous iteration of the code at http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b /Gunnar ___ 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?
2009/4/8 Gunnar Farnebäck gun...@lysator.liu.se: Łukasz Lew wrote: ... For a reference you can take a look for a libego implementation: Ah, so you already use this idea in libego? libego uses this idea only for list of stones in chain. list of liberties are not implemented. but I guess I will implement it sometime soon. You can find this idea in the GNU Go montecarlo board implementation, although with doubly linked lists, see for example http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c starting at line 43. This code is doing quite a lot of book-keeping to support tunable pattern-based heavy playouts, however, so it may be easier to start with a previous iteration of the code at http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b Indeed that's almost exactly what I meant. I can see that you are using doubly linked list to have a constant time liberty_edge removal. Is there any other reason? Have you considered amortized constant time (we remove it when we have an occasion) approach? Lukasz PS This is nice code to read :) /Gunnar ___ 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?
Łukasz Lew wrote: 2009/4/8 Gunnar Farnebäck gun...@lysator.liu.se: Łukasz Lew wrote: ... For a reference you can take a look for a libego implementation: Ah, so you already use this idea in libego? libego uses this idea only for list of stones in chain. list of liberties are not implemented. but I guess I will implement it sometime soon. You can find this idea in the GNU Go montecarlo board implementation, although with doubly linked lists, see for example http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c starting at line 43. This code is doing quite a lot of book-keeping to support tunable pattern-based heavy playouts, however, so it may be easier to start with a previous iteration of the code at http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b Indeed that's almost exactly what I meant. I can see that you are using doubly linked list to have a constant time liberty_edge removal. Is there any other reason? To be honest I don't really remember but that was probably the most important reason. Another possibility is that I became annoyed by the look of the code needed to traverse around a single linked cyclic list. :-) Have you considered amortized constant time (we remove it when we have an occasion) approach? No, not seriously at least. Actually this code hasn't been optimized at all, so there should be some gains left to be made. Lukasz PS This is nice code to read :) Thanks. /Gunnar ___ 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?
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, w...@swcp.com 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 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
RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Yes, I walk both chains looking for duplicates. This is quite fast if done
efficiently, since group merging is rare enough. I found keeping the
liberty arrays to be slower since they are big, so there is more copy
overhead in the UCT tree, and they are not cache friendly.
David
-Original Message-
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of Lukasz Lew
Sent: Tuesday, April 07, 2009 2:32 AM
To: computer-go
Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Tue, Apr 7, 2009 at 07:40, David Fotland fotl...@smart-games.com
wrote:
In Many Faces' playouts I don't keep arrays of liberties. I just keep
the
counts. In the older program I keep linked lists of liberties.
How do you count the number of liberties when you merge two groups?
Do you walk over both chains searching for duplicates in their empty
neighbourhoods (duplicated liberties)?
Lukasz
David
-Original Message-
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of w...@swcp.com
Sent: Monday, April 06, 2009 10:36 AM
To: computer-go
Subject: 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 computer-go@computer-go.org
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, w...@swcp.com 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
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
Thanks. What about linked lists?
They seem to be both compact and fast to merge and detect duplicates.
Why have you abandoned them?
Lukasz
On Tue, Apr 7, 2009 at 17:42, David Fotland fotl...@smart-games.com wrote:
Yes, I walk both chains looking for duplicates. This is quite fast if done
efficiently, since group merging is rare enough. I found keeping the
liberty arrays to be slower since they are big, so there is more copy
overhead in the UCT tree, and they are not cache friendly.
David
-Original Message-
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of Lukasz Lew
Sent: Tuesday, April 07, 2009 2:32 AM
To: computer-go
Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Tue, Apr 7, 2009 at 07:40, David Fotland fotl...@smart-games.com
wrote:
In Many Faces' playouts I don't keep arrays of liberties. I just keep
the
counts. In the older program I keep linked lists of liberties.
How do you count the number of liberties when you merge two groups?
Do you walk over both chains searching for duplicates in their empty
neighbourhoods (duplicated liberties)?
Lukasz
David
-Original Message-
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of w...@swcp.com
Sent: Monday, April 06, 2009 10:36 AM
To: computer-go
Subject: 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 computer-go@computer-go.org
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, w...@swcp.com 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
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Tue, Apr 7, 2009 at 12:33 PM, Łukasz Lew lukasz@gmail.com wrote: Thanks. What about linked lists? They seem to be both compact and fast to merge and detect duplicates. Why have you abandoned them? Lukasz Or a Hash Set, which has constant time insert, delete, contains, and size operations and guarantees no duplicates. Merging groups would be linear, I think. Colin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[OT] Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
This reminds me of a related question I had a while back. In a single MCTS/UCT search node, how do people store the children? Does a node contain summaries of all their children, or just pointers to the children? Pure pointers are simple but requires allocating many more objects, including greater hashtable usage. Local summaries should be more cache friendly, but may miss out on updates to children searched through other paths. Sent from my iPhone On Apr 7, 2009, at 12:33 PM, Łukasz Lew lukasz@gmail.com wrote: Thanks. What about linked lists? They seem to be both compact and fast to merge and detect duplicates. Why have you abandoned them? Lukasz On Tue, Apr 7, 2009 at 17:42, David Fotland fotl...@smart- games.com wrote: Yes, I walk both chains looking for duplicates. This is quite fast if done efficiently, since group merging is rare enough. I found keeping the liberty arrays to be slower since they are big, so there is more copy overhead in the UCT tree, and they are not cache friendly. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Lukasz Lew Sent: Tuesday, April 07, 2009 2:32 AM To: computer-go Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties? On Tue, Apr 7, 2009 at 07:40, David Fotland fotl...@smart- games.com wrote: In Many Faces' playouts I don't keep arrays of liberties. I just keep the counts. In the older program I keep linked lists of liberties. How do you count the number of liberties when you merge two groups? Do you walk over both chains searching for duplicates in their empty neighbourhoods (duplicated liberties)? Lukasz David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of w...@swcp.com Sent: Monday, April 06, 2009 10:36 AM To: computer-go Subject: 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 computer-go@computer-go.org 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, w...@swcp.com 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
Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?
computer-go-boun...@computer-go.org wrote on 07-04-2009 18:33:34: Thanks. What about linked lists? They seem to be both compact and fast to merge and detect duplicates. Why have you abandoned them? Linked lists have a terrible cache behaviour: every pointer (or index) dereference has a nearly 100% chance of causing a cache miss. Lists as arrays and bitmaps have the smallest cache footprint. Not storing them at all, but recomputing them as David Fotland does (only in the playouts) has no memory footprint at all. AvK Disclaimer RIVM___ 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?
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 computer-go@computer-go.org 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, w...@swcp.com 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/
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 computer-go@computer-go.org 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, w...@swcp.com 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: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
What other methods have you tried? Lukasz On Thu, Apr 2, 2009 at 17:14, w...@swcp.com 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 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/ ___ 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?
I actually found a bug in my test, and corrected it. The gap is far less large now. I found that for 10 inserts (and 1 delete, so 9 total libs), The arrays are faster by a small amount. For 11 inserts (10 libs), bit arrays are faster. This leads us to the question if groups in average have =10 or 10 liberties... :) Space is also very significant when choosing a representation. Michael Wing Can you explain? Isaac -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dslspecial.gmx.de/freedsl-surfflat/?ac=OM.AD.PD003K11308T4569a ___ 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?
On Mon, Apr 6, 2009 at 10:54 AM, Isaac Deutsch i...@gmx.ch wrote: This leads us to the question if groups in average have =10 or 10 liberties... :) Without actually having done any tests or measurements, I'd guess it's much less than 10. More like 4. Mark ___ 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?
In Many Faces' playouts I don't keep arrays of liberties. I just keep the counts. In the older program I keep linked lists of liberties. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of w...@swcp.com Sent: Monday, April 06, 2009 10:36 AM To: computer-go Subject: 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 computer-go@computer-go.org 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, w...@swcp.com 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/ ___ computer-go mailing
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Thu, Apr 2, 2009 at 5:14 AM, w...@swcp.com 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. -- 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/
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
From: Heikki Levanto hei...@lsd.dk On Fri, Apr 03, 2009 at 05:07:41PM +0200, Isaac Deutsch wrote: 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. besides, most often you only need to know if a string has zero, one, two, or many liberties, so the counting can be aborted early. Most cases do test for zero/one/two/many, but if we want smart playouts, it helps to know in advance exactly how many liberties some strings have, compared to others in a capturing race. Any program which assumes that n liberties is enough to live may be tricked by a player who can count to n+1. ___ 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, w...@swcp.com 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?
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/
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: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Thu, Apr 2, 2009 at 5:14 AM, w...@swcp.com 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 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). You can find my implementation in the reference-bots I made. The file that counts liberties (and does a bit of other house-keeping) is here: https://plug-and-go.dev.java.net/source/browse/plug-and-go/TesujiRefBot/source/tesuji/games/go/reference/monte_carlo/MCLibertyAdministration.java?rev=267view=markup Mark ___ 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?
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. On Wed, Apr 1, 2009 at 2:08 PM, Isaac Deutsch i...@gmx.ch wrote: Hi I'm currently using the method described here to detect if a group is in atari (1 real liberty): http://computer-go.org/pipermail/computer-go/2007-November/012350.html Thus I store the number of pseudo libs, the sum and the sum of squares for each group. Now for heavy playouts, it would be useful if I could somehow modify this so I can easily detect if a group can be put into atari (meaning it has exactly 2 real liberties). My intuition tells me it should be possible by also storing the sum of positions^3. However, I can't quite wrap my head around how to do the check. Has anyone looked into this before, and found an answer? I like this approach because it's so easy and fast. Regards, Isaac -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ 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?
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 On Wed, Apr 1, 2009 at 8:49 AM, Álvaro Begué alvaro.be...@gmail.com wrote: 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. On Wed, Apr 1, 2009 at 2:08 PM, Isaac Deutsch i...@gmx.ch wrote: Hi I'm currently using the method described here to detect if a group is in atari (1 real liberty): http://computer-go.org/pipermail/computer-go/2007-November/012350.html Thus I store the number of pseudo libs, the sum and the sum of squares for each group. Now for heavy playouts, it would be useful if I could somehow modify this so I can easily detect if a group can be put into atari (meaning it has exactly 2 real liberties). My intuition tells me it should be possible by also storing the sum of positions^3. However, I can't quite wrap my head around how to do the check. Has anyone looked into this before, and found an answer? I like this approach because it's so easy and fast. Regards, Isaac -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ 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] Pseudo liberties: Detect 2 unique liberties?
Many Faces also counts real liberties, and is quite fast enough. -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Mark Boon Sent: Wednesday, April 01, 2009 1:04 PM To: computer-go Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique liberties? 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 On Wed, Apr 1, 2009 at 8:49 AM, Álvaro Begué alvaro.be...@gmail.com wrote: 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. On Wed, Apr 1, 2009 at 2:08 PM, Isaac Deutsch i...@gmx.ch wrote: Hi I'm currently using the method described here to detect if a group is in atari (1 real liberty): http://computer-go.org/pipermail/computer-go/2007-November/012350.html Thus I store the number of pseudo libs, the sum and the sum of squares for each group. Now for heavy playouts, it would be useful if I could somehow modify this so I can easily detect if a group can be put into atari (meaning it has exactly 2 real liberties). My intuition tells me it should be possible by also storing the sum of positions^3. However, I can't quite wrap my head around how to do the check. Has anyone looked into this before, and found an answer? I like this approach because it's so easy and fast. Regards, Isaac -- Neu: GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate + Telefonanschluss für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ 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/
