[computer-go] April KGS bot tournament: results
The results of yesterday's KGS bot tournament are now available at http://www.weddslist.com/kgs/past/46/index.html As usual, I expect there are mistakes, and I will welcome corrections. Congratulations to the winner, CzechBot! Nick -- Nick Weddn...@maproom.co.uk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Reminder: April KGS bot tournament is tomorrow
Nick, I just read your comments. I appreciate it. I knew the StoneGrid was the weakest, but pleasantly surprised to see it managed to win one. I just started to work on the 19x19 versions lately, previously it mostly was about 9x9. It was early morning here when the tournament started, I did not stay up for the tournament. I got up for a few minutes, and took a peek at the games. My network was unstable, so I set it up to retry the kgsGtp once kgsGtp exits for any reason. I guess the delay you were seeing were due to that reason. By the way, my bot occasionally crashes due to some bug I could not identify. It only occurs rarely, and un-reproducible. So I set it to restart the bot once it received kgs-game-over. So the delay could be due to that reason as well. I did not realize there was a disagreement on the dead groups between CzechBot and StoneGrid until I read your summary. I will inspect the logs to see whether it is on my side or CzechBot's side. As for hardware, what you listed is right, it was running on L7700 core 2 duo. Thanks again, John Fan On Sat, Apr 4, 2009 at 5:07 AM, Nick Wedd n...@maproom.co.uk wrote: The April 2009 KGS computer Go tournament will be next Sunday, April 5th the Asian evening, European morning and American night, starting at 07:00 UTC/GMT (08:00 BST) and ending at 13:00 UTC/GMT (14:00 BST). There will be only one division. It will be a 6-round Swiss with 19x19 boards and 29 minutes each of main time. It will use Chinese rules with 7.5 points komi, and a very fast Canadian Overtime, of 25 moves in 20 seconds. There are details at http://www.gokgs.com/tournInfo.jsp?id=447. Registration is now open. To enter, please read and follow the instructions at http://www.weddslist.com/kgs/how/index.html. The rules are given at http://www.weddslist.com/kgs/rules.html. Please send your registration email (with the words KGS Tournament Registration in the title) to me at maproom at gmail dot com (converted to a valid address in the obvious way). Nick -- Nick Weddn...@maproom.co.uk ___ 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 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
