You can accelerate the detection of whether a chain ran out of liberties or not dramatically by using additional data structures. For instance, you can keep an array of the same size as the board indicating which stone is the leader of the chain. It really doesn't matter which stone you make the leader, but just make sure that all the stones in the chain have the same leader (when you join two chains you change who the leader is for one of them, to make them match). You can then have another array with the size of the board which is indexed by leader and tells you how many "pseudo-liberties" each chain has. A pseudo-liberty is an adjacency to an empty point, but you count the point multiple times if there are multiple stones in the chain that touch it. This number is much easier to update incrementally.
In dimwit we also have an array of 16-bit integers which tell us the contents of the 8 neighbors, so we can determine if something looks like an eye with a single lookup into a precomputed table. I think these ideas can make your program much, much faster. Álvaro. On Fri, Dec 9, 2011 at 3:58 AM, Jouni Valkonen <[email protected]> wrote: > Ok, I now boosted the algorithm and I pushed the playout time down to > 200 milliseconds, while I increased the depth. I still need to program > the kou rule and fix some of the status recognition bugs. It tends to > remove undead groups occasionally. > > –Jouni > > On 9 December 2011 10:37, Jouni Valkonen <[email protected]> wrote: >> I found it little hard to program the gobot to recognize the status of >> the groups. >> >> However it does not fill eyes. It's logical structure is that: >> >> a) first it of course checks is the proposed random coordinates >> already reserved. >> >> b) second it checks if that particular location is a friendly eye. >> I.e. it does not fill own eyes. (this is why it has hard time to fill >> the kous, btw) >> >> c) then starts the hard part, because it need to count the liberties >> and does it take away the last liberty of opponent's groups. If it >> takes, opponent stones are removed. (this require's quite extensive >> looping, I have in this function some 4×40 iterations and variable >> amount of secondary iterations, although I am unsure how much is >> enough.) >> >> d) In fourth step it checks if it tries to play suicidal move inside >> opponent's ponnuki, because that is illegal (it equals to passing). >> >> 5) and fifth and final stage it count's whether it is going to fill >> the last liberty of own group. And if that is the case it removes the >> friendly dead stones. New Zeland rules allow suicide for larger than >> single stone groups. >> >> I do not see how this algorithm could be made significantly more >> simple. Perhaps status recognition function could be done smarter and >> thus counting liberties would require less iterations, but I have no >> idea how to do that. (Hmm... perhaps there is one idea that I might >> try.) >> >> That time tagging sound's good idea. The length of playouts is perhaps >> in average close to 105 moves. Sample of one gave 96 moves. >> >> –Jouni >> >> >> On 9 December 2011 01:13, Álvaro Begué <[email protected]> wrote: >>> I can't possibly imagine what the CPU is doing for a whole second in a >>> single playout. PHP is slow, but not *that* slow. I bet you can get >>> around 1000 "light" playouts per second even in PHP. Perhaps you can >>> add some timers to your code and see where the time is going. >>> >>> How long are your playouts? From an empty 9x9 board I seem to remember >>> the typical length of a playout was something like 105 moves, although >>> it's been a while since the last time I looked at that number. If your >>> number is much higher, perhaps your simulation is filling eyes. >>> >>> Álvaro. >>> > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
