Re: [computer-go] Some beginner's questions concerning go bots
Quoting Carter Cheng [EMAIL PROTECTED]: 1) How typically do UCT bots score simulations quickly? I am not too familiar with Chinese scoring rules. In the end of a random games. There are only Black stones and Black Eyes, as well as White stones and eyes. If your playouts are smart enough there may also be points in seki. In that case at least one black and a white stone is adjascent to the point in seki which is simply not counted. If the playouts is even smarter it might avoid capturing some dead stones, but then you have to deal with that in counting. Although counting may be slower your random playouts become shorter so there may be a gain in efficency. Also some people stop the random playout prematurely after very large captures that makes it clear that one side has won the game. 2) How do machines define eyes analytically (mathematically) and are there approximations which are faster to calculate for more traditional or UCT designs (is this information even used for UCT bots?). Mathmatically speaking there are eyes that are not detected by 3x3 patterns. For example a living group can be made having the corners (1,1) and (19, 19) empty. If then all stones on the first line of the board has the same color then this is a live group. This violates 3x3 patterns because it does not matter if the (2,2) and (18,18) point belong to the opponent. But these types of eyes are so rare in real games that it can be ignored, and simply looking at 3x3 patterns are good enough to make a strong program. 3) What sort of algorithm is used to match patterns once you have mined them from some data source? If there is a general approach you probably want to take your pattern (whatever shape it has) and make a hash score of it and put it in a hash table. In the table you will store only those patterns that appear most frequently in games if you use large patterns. The best approach imho that is also well documented is that for Crazystone so go and check the papers at http://remi.coulom.free.fr/CrazyStone/ My program Valkyria rely completly on handwritten pattern recognition, basically using a decision tree which sometimes calls quick algorithms for tricky cases. This is a very time consuming approach for the programmer. 4) And lastly how does UCT cope with ladders? Valkyria reads ladders in the playouts. The ladder code is special because it can only read ladders and do not implement proper go rules. It also gives up if the ladders gets complicated. So it actually returns a) A stone can be captured for sure b) It does not know if it can be captured. This way the ladder code will be as fast as possible and still return a lot of helpful information. The ladder implementation uses a stack to record all changes to the board and then restores the board to the original state. This is because my board representation is too complex to use with the ladder code which must be super fast. The ladder information can be used to play better moves in the playouts, and bias the search in the UCT tree. Thanks in advance, Good luck! Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
Thanks everyone for the responses. My go skills are somewhat limited (only 6-7kyu on KGS) so hopefully I am not belaboring the obvious. I have a few followup questions- 1) What mathematically is a seki? I know this is a local draw but can it be determined statically at some point in all cases using some sort definition without placing stones on the board (i.e. searching). I only know of three cases here- the 1 eye each case with one shared liberty. two shared liberties and the half eye situation. 2) I am guessing hash maps get quite large if they are exhaustive. i.e. (nxn)^3 can quickly become quite big. Or do they tend to be sparsely populated? 3) GTP and time management and scoring after two passes. Are these issues discussed anywhere? Do libraries like Orego and Libgo contain code that already does this which can be used as a reference? Thanks again, Carter. Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
On May 10, 2008, at 7:01 AM, Carter Cheng wrote: Thanks everyone for the responses. My go skills are somewhat limited (only 6-7kyu on KGS) so hopefully I am not belaboring the obvious. I have a few followup questions- 1) What mathematically is a seki? I know this is a local draw but can it be determined statically at some point in all cases using some sort definition without placing stones on the board (i.e. searching). I only know of three cases here- the 1 eye each case with one shared liberty. two shared liberties and the half eye situation. How about a situation where there are neutral points yet the best move is to pass? 3) GTP and time management and scoring after two passes. Are these issues discussed anywhere? Do libraries like Orego and Libgo contain code that already does this which can be used as a reference? Yes, Orego contains some code for this. If you plan to work in Java, the Orego code is intended to be relatively easy to read, so you might start there. BTW, Orego has moved to: http://www.lclark.edu/~drake/Orego.html 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] Some beginner's questions concerning go bots
On Sat, May 10, 2008 at 12:29 PM, Peter Drake [EMAIL PROTECTED] wrote: On May 10, 2008, at 7:01 AM, Carter Cheng wrote: Thanks everyone for the responses. My go skills are somewhat limited (only 6-7kyu on KGS) so hopefully I am not belaboring the obvious. I have a few followup questions- 1) What mathematically is a seki? I know this is a local draw but can it be determined statically at some point in all cases using some sort definition without placing stones on the board (i.e. searching). I only know of three cases here- the 1 eye each case with one shared liberty. two shared liberties and the half eye situation. How about a situation where there are neutral points yet the best move is to pass? Best move for both players -- in some positions and some rulesets, pass can be a ko threat. To include Japanese rulesets, where filling dame is unimportant, you might want to require that pass be the unique best move. Evan Daniel ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
Thanks for the responses. 1) I guess for this seki question I was wondering if it was as easy to define as liveness without seki. The reason I am interested in this is I am curious about absolutely correct scoring functions and whether they currently cope well with advanced seki situations or not. I have been looking at some of the cases listed on the Sensei's Library. A cursory look seems to indicate that they are very difficult to classify- and any seki classifier might need some knowledge of killing shapes. 2) You are correct Jason I transposed the symbols for some reason I actually meant 3^(n^2) but typed it in backwards. 3) Also thanks for the links. I have taken a look at some of the code. I am not sure I will be writing in Java or D and most likely will be implementing the system in something like C++. I am worried about Java's speed since it's interpreted (which still means a x2 slowdown even with the JIT and Hotspot compilation and selective inlining). D I am just not too familiar with I am wondering what advantages it brings over C++. I am primarily concerned about maturity issues. I am not trying to start a discussion on which language is better, but those are my initial impressions. I am primarily interested in creating a very basic go bot at this point and use it for primarily data gathering. I have been curious about certain aspects of game searches and how they apply to go and how reinforcement learning works etc. I figure being a complete beginner at this it will take some time before I have any meaningful insights into how everything works to contribute anything. Regards, Carter. Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some beginner's questions concerning go bots
On Sat, 2008-05-10 at 20:23 -0700, Carter Cheng wrote: 3) Also thanks for the links. I have taken a look at some of the code. I am not sure I will be writing in Java or D and most likely will be implementing the system in something like C++. I am worried about Java's speed since it's interpreted (which still means a x2 slowdown even with the JIT and Hotspot compilation and selective inlining). D I am just not too familiar with I am wondering what advantages it brings over C++. I am primarily concerned about maturity issues. I am not trying to start a discussion on which language is better, but those are my initial impressions. I think Java's speed has come a long way and is now close to comparable to C++. I had gotten interested in D back when it was initially discussed on this list. One described it as C++ without the warts. When I switched from a classical alpha-beta bot to monte carlo, I also switched from C++ to D. In theory, it should be as fast as C++ because it's compiled to machine language, but in practice that's not true... The compilers are not mature yet. Additionally, it's Mac and 64 bit support is limited. marketing for D language D has some really cool features that I've taken advantage of with my bot: * Greatly simplified generic coding * Builtin function objects (called delegates) * Design by contract * Built in unit testing * Foreach / no iterators /marketing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
