[computer-go] Complicated seki with Ko
Your example is very clever, but the recapture doesn't technically bring us back to where we started, as Magnus required. |- - - - - - - |. * * o . . . |* . * o * . * |o . o o * . . |o * o . * . . |o o o * . . . |. * * * . . . |. . . . . . . |. * . . . . . Black to play and kill :) In this case one needs to check that after the two stones are captured the capturing single stone can be recaptured bringing us back to where we started. If it is a big eye there is no recapture. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Complicated seki with Ko
- puts itself into atari - has four occupied neighbours, one of which is its own color - does not put the opponent in atari In the Ko in question, J6 does put the opponent in atari, so this rule is not applicable. But I will make a note of it for future reference. Another rule I just thought of that may work very well is not put yourself into atari with more than one stone if you can play at the other liberty without putting yourself into atari. This rule works very well in Pebbles. It is used in the playouts as an 'upgrade' rule. That is, if a move is both atari and self-atari and you can play safely at the other end, then do so. I first heard about this rule in a paper by Remi Coulom. (Don't remember which one; to find it, google the computer go bibliography.) This change makes a huge difference on this ko/seki situation. Pebbles can now accurate assess the position literally dozens of moves in advance where it realized it was lost before. Note that this rule doubles the probability of finding the next-to-last move of a semeai when one string has a protected liberty. So it is helpful in many situations, not just this odd case. I don't have a case yet in which this rule is implicated in a disaster. Perhaps one will come up eventually, and if so then I will let you know. Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Complicated seki with Ko
This case is of course not pruned by Valkyria, simply because the the pattern here is completely different from what we discussed. :) This sacrifice prevents an eye to be made. -Magnus Quoting Christian Nentwich christ...@modeltwozero.com: |- - - - - - - |. * * o . . . |* . * o * . * |o . o o * . . |o * o . * . . |o o o * . . . |. * * * . . . |. . . . . . . |. * . . . . . Black to play and kill :) Christian On 01/07/2009 17:41, Magnus Persson wrote: In this case one needs to check that after the two stones are captured the capturing single stone can be recaptured bringing us back to where we started. If it is a big eye there is no recapture. -Magnus Quoting Brian Sheppard sheppar...@aol.com: For black I think I prune this kind of two stone suicide always no matter what the situation is (exception is ko). These prunings are probably wrong in some extremely rare cases. How can you tell the difference between this kind of two-stone self-atari, and a self-atari of two stones within an opponent's big eye, which could be necessary for lifedeath? ___ 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/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] any AMD performance experience?
Hi all, do any of you have performance figures for multi-processor AMD (opteron/shanghai) systems with your engines? Any single-processor? There's a good offer here on AMD based servers to get the second processor for free, so I am thinking of pouncing on it. I'm curious about how the better memory performance for the multi-processor AMD system impacts Go engines, versus the worse integer and branch prediction performance.. thanks, Christian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Hash tables
Okay, so I've finally built a transposition table. There is a big pool of nodes, allocated at startup. To find a node, I: 1) Play the move on the board and get the new Zobrist hash (incorporating the simple ko point and color to play). 2) Take this modulo the length of the table (currently 128K nodes) to find the first place to probe. 3) Linearly probe (i.e., try the next location, then the next one, etc.) until either I find a node with the correct Zobrist hash or hit the limit on the number of probes (1024 seems to work okay). 4) In situations where I'm trying to allocate a node, if I didn't find one that matched, I overwrite the first old node I encountered. An old node is one that wasn't touched on the previous turn (as indicated by a timestamp). If I didn't find an old node, the allocation fails. This works all right, but I'm bothered by the tension between a low probe limit (speeding up unsuccessful searches) and a high one (making more complete use of the table). Also, the table tends to fill up. Questions for others: a) Are you using this timestamp trick, or are you traversing your DAG to mark which nodes are still relevant every time you accept a (real, non-playout) move? I realize that almost none of the nodes touched last turn are still relevant, but traversing the entire table seems expensive. b) Is there some clever way to abandon an unsuccessful search earlier? In a hash table that wasn't full or close to it, I'd go until I found a null (i.e., a node that had never been used, as opposed to a node that is old or marked for deletion). Unfortunately, Orego fills up the table of 128k nodes in a matter of seconds. c) Is there some useful way of rehashing to get rid of the old nodes? Unfortunately, I can't fit a second copy of the table in memory... Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 11'th Annual Malibu Go Party
please join us for an afternoon of surf, sand, and go. saturday, august 22'nd 2009, from 11 a.m. to 6 p.m or so, at 26918 malibu cove colony drive (http://maps.google.com/maps?f=qsource=s_qhl=engeocode=q=26918+malibu+cove+colony+drive,+malibu+californiasll=33.8565,-118.148904sspn=0.007431,0.017059ie=UTF8ll=34.027428,-118.75886spn=0.007416,0.017059z=16iwloc=A) this is a custom house on the beach with pool and jacuzzi, so bring bathing suits. please bring a 6-pack of whatever you like to drink. please bring a go board and stones if you have one that can travel. partners and well behaved children are welcome (partners sometimes play other games or walk on beach). if you have a favorite dish that you like to make, please do so and bring it. the usual dogs and burgers will be provided. please rsvp to *me* (not eric) so we can get a head count. if you need directions, please email me or call me at (562) 272-8556. check in at the guard station and tell them that you are going to eric cotsen's go party. thanks --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: fuego HowTo
Hello Jonathan I tried something like the following: install the boost stuff in some place: build bjam (the source is somewhere in the boost stuff) $ ./build.sh use bjam to build boost: $ ./bjam -sTOOLS=darwin --prefix=/Users/patrick/boost --exec-prefix=/Users/patrick/boost install use boost to build fuego $ ./configure --with-boost=/Users/patrick/ph_workspace/go/fuego/boost $ make copy book.dat, fuege, libboost_filesystem-1_33_1.dylib, libboost_thread-1_33_1.dylib to a new directory reset the library path in the fuego executables so that they can be found localy $ install_name_tool -change libboost_thread-1_33_1.dylib @executable_path/libboost_thread-1_33_1.dylib fuego $ install_name_tool -change libboost_filesystem-1_33_1.dylib @executable_path/libboost_filesystem-1_33_1.dylib fuego downsize the fuego executable $ strip fuego good luck Patrick --- On Wed, 7/1/09, ~:'' ありがとうございました。 j.chetw...@btinternet.com wrote: From: ~:'' ありがとうございました。 j.chetw...@btinternet.com Subject: fuego HowTo To: ech_na...@yahoo.com Date: Wednesday, July 1, 2009, 7:40 AM fuego HowTo Ech, enjoyed your intel binary, :-) tx could you please provide a how to, as I fell somewhere. regards Jonathan Chetwynd 3 Dan UK $ cd fuego-0.4/ $ ./configure ... ... checking for boostlib = 1.33.1... configure: error: We could not detect the boost libraries (version 1.33 or higher). If you have a staged boost library (still not installed) please specify $BOOST_ROOT in your environment and do not give a PATH to --with-boost option. If you are sure you have boost installed, then check your version number looking in boost/version.hpp. See http://randspringer.de/boost for more documentation. $ http://www.boost.org/users/download/ unzipped boost_1_39_0.zip moved to /usr/local $ vi .bash_profile PATH=$PATH:/usr/local/boost_1_39_0 export PATH restarted bash in new terminal, same response, what did I miss? kind regards ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Complicated seki with Ko
You always need to be extremely careful about these kind of heuristics. Especially in MC programs they can be detrimental very easily. But I believe you can come up with a reasonable rule to prevent some self-atari's. I have one which is something along the following lines: - puts itself into atari - has four occupied neighbours, one of which is its own color - does not put the opponent in atari Probably better rules can be invented. I would be surprised if any such rule is always 100% safe. But these at least cover your case. Another rule I just thought of that may work very well is not put yourself into atari with more than one stone if you can play at the other liberty without putting yourself into atari. Mark On Wed, Jul 1, 2009 at 7:06 AM, Christian Nentwichchrist...@modeltwozero.com wrote: |- - - - - - - |. * * o . . . |* . * o * . * |o . o o * . . |o * o . * . . |o o o * . . . |. * * * . . . |. . . . . . . |. * . . . . . Black to play and kill :) Christian On 01/07/2009 17:41, Magnus Persson wrote: In this case one needs to check that after the two stones are captured the capturing single stone can be recaptured bringing us back to where we started. If it is a big eye there is no recapture. -Magnus Quoting Brian Sheppard sheppar...@aol.com: For black I think I prune this kind of two stone suicide always no matter what the situation is (exception is ko). These prunings are probably wrong in some extremely rare cases. How can you tell the difference between this kind of two-stone self-atari, and a self-atari of two stones within an opponent's big eye, which could be necessary for lifedeath? ___ 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] Hash tables
a) I don't use timestamps. I don't have a DAG. I just reuse nodes that have few visits or are old (I keep the depth from root in each node). b) By unsuccessful search, I assume you mean the linear search in the probe. I don't do a probe search, so I can't help you there. I have a strong aversion to doing big linear searches in performance-sensitive code :) How big are your nodes? If you have 2 GB, they are about 15 KB each. That seems a little large. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Thursday, July 02, 2009 4:21 PM To: Computer Go Subject: [computer-go] Hash tables Okay, so I've finally built a transposition table. There is a big pool of nodes, allocated at startup. To find a node, I: 1) Play the move on the board and get the new Zobrist hash (incorporating the simple ko point and color to play). 2) Take this modulo the length of the table (currently 128K nodes) to find the first place to probe. 3) Linearly probe (i.e., try the next location, then the next one, etc.) until either I find a node with the correct Zobrist hash or hit the limit on the number of probes (1024 seems to work okay). 4) In situations where I'm trying to allocate a node, if I didn't find one that matched, I overwrite the first old node I encountered. An old node is one that wasn't touched on the previous turn (as indicated by a timestamp). If I didn't find an old node, the allocation fails. This works all right, but I'm bothered by the tension between a low probe limit (speeding up unsuccessful searches) and a high one (making more complete use of the table). Also, the table tends to fill up. Questions for others: a) Are you using this timestamp trick, or are you traversing your DAG to mark which nodes are still relevant every time you accept a (real, non-playout) move? I realize that almost none of the nodes touched last turn are still relevant, but traversing the entire table seems expensive. b) Is there some clever way to abandon an unsuccessful search earlier? In a hash table that wasn't full or close to it, I'd go until I found a null (i.e., a node that had never been used, as opposed to a node that is old or marked for deletion). Unfortunately, Orego fills up the table of 128k nodes in a matter of seconds. c) Is there some useful way of rehashing to get rid of the old nodes? Unfortunately, I can't fit a second copy of the table in memory... Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Many Faces is up now in 19x19 CGOS
Many Faces is on cgos 19x19 now, playing on a 1 CPU Pentium M 1.7 GHz. I'm not using this computer for anything else, so it should be up indefinitely, if any other programs want some competition. I made some minor improvements this week. Currently it's winning about 81% against gnugo 3.7.10 level 10, when doing 8000 playouts per move on 19x19. David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Jul 5, 2009, at 6:01 PM, David Fotland wrote: a) I don't use timestamps. I don't have a DAG. I just reuse nodes that have few visits or are old (I keep the depth from root in each node). Do you save the tree between turns? If so, how do you adjust the depth from the root when a real move is played and one of the children of the old root becomes the new root? Similarly, do you clear out all of the nodes, so they don't look like they have many visits? ...or does root mean the beginning of the game? b) By unsuccessful search, I assume you mean the linear search in the probe. I don't do a probe search, so I can't help you there. I have a strong aversion to doing big linear searches in performance-sensitive code :) I share the same aversion. Do you simply give up if the node indicated by (zobristHash % tableSize) cannot be overwritten? How big are your nodes? If you have 2 GB, they are about 15 KB each. That seems a little large. The machine in question has 1 GB, and I believe the nodes are around 1K (for 9x9). That does imply that I should be able to fit around a million of them in there, but the machine thrashes when I go from 128K to 256K nodes. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Hash tables
Yes, I save the search state from move to move. I don't save the tree, since I don't have a DAG. I keep the depth from the start of the game, not the start of the search. I give up when there are no nodes that area available to be overwritten. If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Sunday, July 05, 2009 7:08 PM To: computer-go Subject: Re: [computer-go] Hash tables On Jul 5, 2009, at 6:01 PM, David Fotland wrote: a) I don't use timestamps. I don't have a DAG. I just reuse nodes that have few visits or are old (I keep the depth from root in each node). Do you save the tree between turns? If so, how do you adjust the depth from the root when a real move is played and one of the children of the old root becomes the new root? Similarly, do you clear out all of the nodes, so they don't look like they have many visits? ...or does root mean the beginning of the game? b) By unsuccessful search, I assume you mean the linear search in the probe. I don't do a probe search, so I can't help you there. I have a strong aversion to doing big linear searches in performance-sensitive code :) I share the same aversion. Do you simply give up if the node indicated by (zobristHash % tableSize) cannot be overwritten? How big are your nodes? If you have 2 GB, they are about 15 KB each. That seems a little large. The machine in question has 1 GB, and I believe the nodes are around 1K (for 9x9). That does imply that I should be able to fit around a million of them in there, but the machine thrashes when I go from 128K to 256K nodes. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Jul 5, 2009, at 7:21 PM, David Fotland wrote: Yes, I save the search state from move to move. I don't save the tree, since I don't have a DAG. I keep the depth from the start of the game, not the start of the search. Got it. I give up when there are no nodes that area available to be overwritten. I'm still a little confused. First, does the hash table contains pointers into a node pool, or do you use the node pool as the hash table? Second, how and when do you determine which nodes (if any) are available for overwriting, without doing some sort of traversal? Is the following a correct summary of what you do when it's time to create a new node? Go to the one node that would be used for this Zobrist hash. If the same hash is stored there, use the existing node. If not, either overwrite this node (if this node is available for overwriting) or not create a new node (otherwise). Also, what exactly is the criterion for overwriting? You said nodes that have few visits or are old. Is this just (visits visitThreshold) || (depthFromBeginningOfGame currentGameTurn)? Doesn't depthFromBeginningOfGame cause you to keep around nodes that are outside the still-relevant branch of the tree (i.e., the branch descending from the current root), almost all of which are irrelevant? If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. ...because this improves the quality of information in the nodes you were able to create. That makes sense. Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Hash tables
The hash table contains a linked list of nodes with the same hash index. Your description is pretty close, but I don't remember the exact details. Yes, I keep around some nodes for while, but eventually old nodes go into the past and can be recovered. I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. David I give up when there are no nodes that area available to be overwritten. I'm still a little confused. First, does the hash table contains pointers into a node pool, or do you use the node pool as the hash table? Second, how and when do you determine which nodes (if any) are available for overwriting, without doing some sort of traversal? Is the following a correct summary of what you do when it's time to create a new node? Go to the one node that would be used for this Zobrist hash. If the same hash is stored there, use the existing node. If not, either overwrite this node (if this node is available for overwriting) or not create a new node (otherwise). Also, what exactly is the criterion for overwriting? You said nodes that have few visits or are old. Is this just (visits visitThreshold) || (depthFromBeginningOfGame currentGameTurn)? Doesn't depthFromBeginningOfGame cause you to keep around nodes that are outside the still-relevant branch of the tree (i.e., the branch descending from the current root), almost all of which are irrelevant? If the search is long enough, there are no nodes that can be recovered, and the UCT tree stops growing. I keep searching when there are no reusable nodes. ...because this improves the quality of information in the nodes you were able to create. That makes sense. Thanks, Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
On Jul 5, 2009, at 9:05 PM, David Fotland wrote: The hash table contains a linked list of nodes with the same hash index. Okay, I've almost got it. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. That's reassuring. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Hash tables
Between moves, I find the nodes that can be recycled and put them on a free list. If the free list is empty I do a very short search, then give up. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Sunday, July 05, 2009 9:42 PM To: computer-go Subject: Re: [computer-go] Hash tables On Jul 5, 2009, at 9:05 PM, David Fotland wrote: The hash table contains a linked list of nodes with the same hash index. Okay, I've almost got it. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. That's reassuring. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hash tables
Aha, got it! Thanks. Peter Drake http://www.lclark.edu/~drake/ On Jul 5, 2009, at 10:17 PM, David Fotland wrote: Between moves, I find the nodes that can be recycled and put them on a free list. If the free list is empty I do a very short search, then give up. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Peter Drake Sent: Sunday, July 05, 2009 9:42 PM To: computer-go Subject: Re: [computer-go] Hash tables On Jul 5, 2009, at 9:05 PM, David Fotland wrote: The hash table contains a linked list of nodes with the same hash index. Okay, I've almost got it. If you're hashing by chaining, you presumably go to the appropriate slot in the table, then traverse the (short) linked list of nodes hanging from that slot. If the node you want isn't present, though, you have to find another node you can overwrite, presumably from another chain in the hash table. How do you find such a node without a lengthy search? I actually have fewer total nodes than you do. The commercial version allocates 30K nodes per CPU core. The version in the world championship had much more, but the commercial version can't be that greedy for memory. That's reassuring. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
