[computer-go] Monte Carlo and refutation
I'm running into a problem where my Monte Carlo program is very slow to acknowledge that its favorite move has a strong counter. Part of the problem is that the value of a move is based on how many of the runs through that move have succeeded. If there were a lot of them before the correct reply was discovered, the move has considerable "inertia" and it takes time to recover. Has anyone tried only counting the most recent games through a move (say, the last 100), rather than the entire history? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Monte Carlo and refutation
On Oct 30, 2006, at 7:51 PM, Don Dailey wrote: On Mon, 2006-10-30 at 19:34 -0800, Peter Drake wrote: I'm running into a problem where my Monte Carlo program is very slow to acknowledge that its favorite move has a strong counter. Part of the problem is that the value of a move is based on how many of the runs through that move have succeeded. If there were a lot of them before the correct reply was discovered, the move has considerable "inertia" and it takes time to recover. The inertia effect is minor, once it finds the right move it tends to quickly recover. I'm getting a rather severe effect. Specifically, if the move in question has led to wins for hundreds of thousands of games, it takes a similar amount of time to get its win rate back down. Has anyone else had experience with this? The reason this works so well is that you are taking very large samples, 100 samples wouldn't begin to be enough. Just a number I pulled out of my hat. A rationale (rationalization?), though, would be that since the most recent games were played with the most information, they're the most reliable. If you want to experiment, the best way to solve this problem in my opinion is to emphasize the later moves more than the early moves but in a very smooth way. The way I did this was to hit each move I encounter as well as it's siblings, with a "degrade factor". I multiply the scores and the moves by the same constant. Something very close to 1.0 such as 0.9. You have to use floating point values to do this. Consider how this works - if you play 100 games and win half of them, with my method it matters which ones you win. With the normal method it doesn't matter. With my method you will score much higher if you win more of the games towards the end. Conversely, if this move is refuted and you lose most of the later games, your score will drop much more quickly. That sounds reasonable. Another thought is to keep a score for each node that is incremented when the player wins and decremented when the player loses, but within some bounds (say, +/- 100). The only way to have a high positive score is to have won many recent games. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ Has anyone tried only counting the most recent games through a move (say, the last 100), rather than the entire history? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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/
[computer-go] Monte Carlo challenge: ladders
To those of you with Monte Carlo programs:Consider this board configuration:...ww..wBBw..wBBw..wB I believe black's best move is to play in the center and escape via the broken ladder.1) Is this true? (This is a Go-playing question.)2) Can your program find this move (and decide that it's not a good move if the ladder-breaker is missing)?3) If so, how many runs does it take?4) With fewer runs, what does the program do? If there is no ladder breaker, does the program think the ladder works until it has read it to the end?I'm having a devil of a time getting my program to solve this one, and I'm wondering if I just picked an extremely hard problem.Peter DrakeAssistant Professor of Computer ScienceLewis & Clark Collegehttp://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] UCT
I've decided to bite the bullet and implement UCT in Orego, since (a) everyone else appears to be using it and (b) not being a statistician, improving on this is probably not where I'm likely to make a contribution. Here's my understanding of UCT. It is an algorithm for choosing the best move from a given parent node. Let p = # of runs through parent node r = # of runs through move in question w = # of wins through move in question UCT proposes that we choose the node with the highest sum average + uncertainty where average = w/r and uncertainty = sqrt(2 * logn(p) / r) Is this correct? Are there any things to watch out for? Also, are people pruning any move for which (average + uncertainty) is less than the (average - uncertainty) of some other move? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] UCT
On Nov 3, 2006, at 8:10 AM, Rémi Coulom wrote: You can try multiplying uncertainty by a well-chosen constant value. This way, you can tune how selective your search is. I found that using a constant < 1 improves the search on 9x9 for Crazy Stone (I use 1/sqrt(10), if I recall correctly). I wonder what is the experience of other UCT programmers, by the way. Whee, parameter tweaking! :-) Do you have some reason for choosing this value, or did it just work well in practice? Also, are people pruning any move for which (average + uncertainty) is less than the (average - uncertainty) of some other move? I am not sure what you mean. In UCT, you only search the move that has the highest average + uncertainty, and you don't search any other at all. By "prune" I mean "remove from the stored tree", making the memory used on that branch available for something else. Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] UCT
On Nov 3, 2006, at 8:33 AM, Rémi Coulom wrote: I have never had memory problems with Crazy Stone. Crazy Stone uses 32 bytes of RAM per node of the tree. It is not really a tree, but a hash table, to handle transpositions. For nodes closer to the root, I "extend" each node with more data (pointers to children). This is only Since Orego stores the entire tree (with some optimizations for non- branching paths), it is ... somewhat less memory-efficient than Crazy Stone. :-) needed for a small proportion of the total number of nodes, so it does not eat up a huge amount of RAM. That is because I don't do UCT in a node before 81 random simulations have been run there. A thought: if we define the uncertainty of an untried move to be 2, the UCT algorithm will automatically try all of those before trying anything else twice. Maybe you're already doing that. Since I use transpositions, it is not really possible to remove a subtree, anyways. Yes, another thing I have to (re-)implement... Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] UCT finds the right answer, but...
Consider this position:...wBww.wB...wBBBBw..wBw...w..wBw.w.w.wwBw...This is black to play, no komi.As I read it (correct me if I'm wrong!), the white groups at upper left and lower right can't be killed (assuming white defends them). Black can kill either of the other groups, and white can respond by saving the remaining one. Since killing the upper right white group is not big enough, black's only winning move is to kill the lower left group by playing at b2.Orego (now using UCT) quickly finds the correct answer, but the estimates of the probability of winning are strange. Here's a graph:The probability of winning by starting at b2 is greater than the probability starting elsewhere, but shouldn't it approach 1.0, since b2 is a winning move? Do others get this same behavior? Does anyone have an explanation?For what it's worth, here are the probabilities and / through each move:B1 (0.262654 = 1510/5749):G1 (0.269305 = 2504/9298):H1 (0.276537 = 5200/18804):J1 (0.263229 = 1567/5953):*B2 (0.290454 = 134822/464177):C2 (0.288902 = 69762/241473):G2 (0.274577 = 4156/15136):J2 (0.276275 = 5034/18221):B3 (0.261835 = 1427/5450):C3 (0.269523 = 2554/9476):G3 (0.269982 = 2655/9834):H3 (0.27404 = 3927/14330):J3 (0.273359 = 3660/13389):F6 (0.25266 = 831/3289):G6 (0.268461 = 2334/8694):H6 (0.273485 = 3706/13551):J6 (0.247165 = 632/2557):A7 (0.269866 = 2632/9753):B7 (0.274571 = 4157/15140):C7 (0.268814 = 2404/8943):A8 (0.275441 = 4577/16617):C8 (0.277177 = 5617/20265):A9 (0.259601 = 1237/4765):B9 (0.27903 = 7180/25732):C9 (0.268422 = 2324/8658):G9 (0.257561 = 1090/4232):H9 (0.277021 = 5513/19901):J9 (0.262094 = 1452/5540):PASS (0.221808 = 238/1073): Peter DrakeAssistant Professor of Computer ScienceLewis & Clark Collegehttp://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] UCT finds the right answer, but...
On Nov 7, 2006, at 11:10 AM, Magnus Persson wrote: Quoting Peter Drake <[EMAIL PROTECTED]>: The probability of winning by starting at b2 is greater than the probability starting elsewhere, but shouldn't it approach 1.0, since b2 is a winning move? Do others get this same behavior? Does anyone have an explanation? The situation is still such that random play can mess things up. Even if black is winning UCT search for white will pick those moves which allows black to make bad moves deeper in the tree. I've had similar experiences with other variants of Monte Carlo Go. Incidentally, I think this makes ladders particularly difficult. Thanks, good to know it's not just my program that exhibits this behavior. What you should do is to print out the winning percentage for the principle variation and not only the top move. In valkyria the winning score do not change much at the root but following the tree down a winning variation often increase the winning percentage 5-10 % at each ply until it reache a point where random play always lead to a win. It doesn't always work out that way, but sometimes it does: B2:0.292577 H9:0.291222 C2:0.29693 G2:0.292865 G6:0.312761 B1:0.35 J2:0.67 PASS The important thing is that UCT (very!) quickly finds the correct move. Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Flummoxed with GTP
Orego supports GTP, but for some reason today I can't get it to work with Goban, glGo, or GoGui. It runs fine and quickly from the command line, responding to GTP commands: $ /Users/user/Documents/go/xcode/Orego/build/Release/Orego name = Orego genmove black = E5 quit = When I invoke the same program from any of the GTP front ends, though, it never responds to the name command and is apparently crunching away. I'm at a loss to imagine why the behavior of the program would change depending on whence it is invoked. Can anyone think of any sense in which sending a command like "name" from a front end is different from doing it manually? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Flummoxed with GTP
As always, publicly announcing one's confusion generally causes a solution to appear. The difference is that my program is being invoked from a different directory, which was causing confusion when the program went to look up the opening book file. We apologies for the interruption and return you to your regularly scheduled programming. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 14, 2006, at 9:19 AM, Peter Drake wrote: Orego supports GTP, but for some reason today I can't get it to work with Goban, glGo, or GoGui. It runs fine and quickly from the command line, responding to GTP commands: $ /Users/user/Documents/go/xcode/Orego/build/Release/Orego name = Orego genmove black = E5 quit = When I invoke the same program from any of the GTP front ends, though, it never responds to the name command and is apparently crunching away. I'm at a loss to imagine why the behavior of the program would change depending on whence it is invoked. Can anyone think of any sense in which sending a command like "name" from a front end is different from doing it manually? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Testing against gnugo
Orego speaks GTP, as does gnugo. I'd like to run a bunch of games (say, 50) between them to see how many Orego wins. Does anyone have a handy script (ideally bash or Python) for this? Thanks, Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Positions illustrative of computer stupidity ?
One could use the heuristic that the outside is larger than the inside, but perhaps a situation can be created where this is not true. This might even be something beginning Go players could see/ understand. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 22, 2006, at 2:07 PM, Chrilly wrote: Attached is a very simple position which adresses the problem of what is inside and what is outside. A seemingly logical definition of inside is that the point is enclosed by stones of one color and/ or the border. Or the fireman-algorithm. If one traverses along an own wall and/or the border in the same direction and comes back to the point. But in the given position a3 and all the other 257 intersections are according this definition also "inside". It would never come to the mind of a human player the the 3 black stones enclose the 257 intersections. The message is: Tasks which are for a human completly trivial are hard to formalize. Chrilly ___ 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] Orego 3.03 posted
If anyone's interested in digging through our C++ code, here it is: http://www.lclark.edu/~drake/go/ Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Paper presents results on proximity heuristic
Here it is: https://webdisk.lclark.edu/xythoswfs/webui/_xy-2115826_1-t_OX34gnaB Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Making Java much faster
Everyone here has offered me all kinds of useful advice on speeding up or otherwise improving Orego. In thanks, I offer a recent (to me) discovery about how to make Java programs run much faster. Instead of java MyProgram do java -server MyProgram It's not entirely clear what the difference between "server mode" and the default "client mode" is -- maybe just-in-time compilation? In any case, I found that it nearly doubled the speed of a small program. Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Making Java much faster
Orego version 3.03, described in the paper and available at the Orego web site, is in C++. However, we are finding C++ an exceedingly frustrating language to work in. I won't go into the details here -- we don't need another language war -- but suffice it to say that it seems like we're spending a lot of time messing with details that aren't of interest for the research. Now that I've found that Java can have speed within a factor of 2 of C++, I'm thinking of going back to Java. A student and I are challenging each other to make the program multithreaded -- he in C++, me in Java. If I can rewrite the program in Java AND multithread it before he can multithread the C++ version, it will be (weak) evidence that it might be worth trading some runtime speed for development time. Your point (also raised by others) about testing against other opponents is, of course, valid. I would have done so in this paper were the submission deadline not pressing, and plan to do so for future papers. In defense of this paper, I can only say that (according to the self-play data in the paper) adding the proximity heuristic offered not just an improvement but a very large improvement -- 95% statistical confidence. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 29, 2006, at 3:22 AM, Chrilly wrote: I am confused. In your paper you write "Orego is a Monte CarloGo programm written in C++". Is Orego now in C++ or in Java or both? The paper mentions the relative comparison of 2 versions. This is common practice in the scientific literature, but it is a very poor choice if one wants to measure the effect of a new method. The effects of changes is much more pronounced than against another opponet. A method which is good against the twin-brother must not be good against other opponents at all. Even against other opponents it happens frequently that a method works quite well against opponent A but it fails against B. Its relative easy to make a version which crashes e.g. Rybka, but this version is poor against Fritz and Shredder. The really difficult task is to find a combination which plays good against all. But its of course a good method for papers where the authors want to proove how good their idea is. But it demonstrates the lack of competence of the academic world for game-programming. Otherwise such experiments would not be accepted as a proof for a concept. There is also Vincent Diepeveens law: In a weak programm is every change an improvement. I do not know how good Orego is, but playing e.g. against the top-3 programms would be a much better experiment. This remark is not against the Orego team which does a fine job to explain their work. I like to read the Orego project "news". Its against a very common and bad practice in papers. One can even get an award for the best paper of the year and become a standard reference with this poor methodology. In my "Null-Move" paper I did the same. The Null-Move Version of Nimzo was running on a 386, the Non-Null-Move Version on a 486 and the result was about equal. My conclusion was: The Null-Move is worth one hardware generation. At that time I was not really aware of the problem and the bad comparision was not on purpose. But the reviewer/editor of the ICCA- Journal should have insisted on better experiments. The only "improvements" he made was changing the original title from "Null move and deep search: Selective search heuristics for. stupid chess programs" to "obtuse chess programms". I know what a stupid programm is, but I do not know till today the meaning of "obtuse". Chrilly ___ 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] Making Java much faster
This is something we hope to do once we have Orego multithreaded: give each version the same amount of time, so the time costs of adding a heuristic are automatically taken into account. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 29, 2006, at 7:30 AM, Eduardo Sabbatella wrote: Games are additionally hard-real-time problems. E.g. in the Orego tests but versions got the same amount of nodes. For a realistic comparision one has to give both sides the same time and not the same node-budget. What do you think about giving the same program different player times? Perhaps its found that ELOs/time grow log/lineal/exp. Also, same program but with one feature disabled, same time. Does make any sense? __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ 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] Making Java much faster
On Nov 29, 2006, at 9:26 AM, Eduardo Sabbatella wrote: I'm a full time worker. Before starting my engine (a couple of months ago) by 3rd or 4th try. I concluded this: It will be impossible for me to do anything in C, C++ because I will have to focus on not having memory leaks, range errors, etc. My engine nowadays is winning agains gnugo on lower levels. Without time constrait. Ok, gnugo takes 10 secs to play, my engine 90 seconds. But, something I has sorted out in the beginning: - I have to optimise algoritms, not code. I agree absolutely, and have seen this advice in many books. One went so far as to propose the two rules of optimization: 1. Don't to it. 2. (For advanced programmers only) Don't do it yet. Algorithmic improvements are much more important than local efficiency improvements. I think Drake follow the correct path, first optimise algorithm on Java, then move it to C/C++. Since computer Go algorithms are always, to some degree, in flux, I'm now leaning toward staying in Java. Yes, C/C++ allows fine control, but it also requires such fine control that it's hard to think about larger algorithmic issues. Personally, I found that creating objects in Java is reay expensive. My engine use a lot arrays of ints, longs, big linked arrays by reference numbers. (yes, a'la C... sometimes I have to resize arrays, its costy, but I found that its a lot cheaper on overall perfomance than creating objects). Yes, in both time and space. I intend to go to some lengths to avoid dynamic object creation, e.g., creating all of the objects at startup time and just clearing them out when I need "new" ones. For the most memory-intensive part of the program (the enormous search tree), I intend to use a big array of raw ints. Yes, this will be just as ugly as doing it in C/C++, but at least I'll be able to confine the ugliness to that part of the program. Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] language choices
A note: we're working on converting Orego back from C++ to Java, and we're getting 5,000 (totally random at this point) simulated games per second. We'll probably continue in this direction. Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] How to improve Orego
It's not clear whether this is faster. Determining that a move is illegal because the point is occupied is very fast; determining that a move IS legal (i.e., not a suicide or ko violation) is the slow part, and I avoid that by taking the first legal move I find. (Of course, once all moves have been tried from a given move, UCT takes over.) In any case, my profiling data indicates that choosing the random move per se is not the expensive part; playing the move is. Thanks for the suggestion, Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 4, 2006, at 7:52 AM, Chrilly wrote: In the Orego paper the problem of selecting a move when the board is filled with stones is mentioned. Orego uses a sort of double- hashing scheme. But isn't it trivial to keep a list of empty intersections? Before the MC-run is started, one builds up this list. If a stone is placed now on the board, the entry is removed from the list and the last entry is copied into this slot. In this way the list is always dense. One can of course not run linearly trough the list to find the entry which should be removed. Instead one builds at the beginning another array which is indexed by the board-point and which contains the index of the point in the empy-point-list. This second array has to be changed too when the last entry is copied into the removed slot. With a few operations one gets the big advantage to sample all the time only the empty points. I think this solution is much simpler and more efficient than the double-hashing scheme of Orego. Chrilly ___ 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] language choices
The three most important things seem to be: 1) Run java in -server mode. This appears to double speed for no effort. 2) As you say, avoid creating objects. For example, instead of creating a new array each time a method is invoked, make the array a field and just clear it out when you need a "new" one. Similarly, instead of Foo x = y.clone(); do something like x.copyDataFrom(y); where of course you have to write copyDataFrom(). 3) Algorithmic improvements are always more important that fine-tuning. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 4, 2006, at 2:40 AM, Eduardo Sabbatella wrote: Would you like to share some experiences on tunning up Java code ? Yesterday I left my machine profilling the code. (takes ages with TPTP). I didn't research too much the results, but as far I could see, creating objects is almost FORBIDDEN. The "clone" method on game class which is used for create a copy of game object for every simulation is the function that is taking the most of the time. (implies a couple of inner clones...) Also, a "getNear" method that returns a list of near points (considering borders) is the second most expensive. (even, being optimised ... The problem is that is creating a new array of size 1|2|3|4 elements for returning the result). About game class, I think that I will change to simple floodfill insteads of maintaining a list of liberties and chains. Clonning that list is expensive. --- Peter Drake <[EMAIL PROTECTED]> escribió: A note: we're working on converting Orego back from C++ to Java, and we're getting 5,000 (totally random at this point) simulated games per second. We'll probably continue in this direction. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ 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] Proposed UCT / transposition table implementation
I've noticed that Orego has done very poorly in the last couple of competitions. This is partly due to the improvements in others' programs, but I think the fact that Orego currently doesn't have a transposition table is crippling. Since I'm rewriting this stuff in Java, I'm thinking about how to handle this, and would like to offer up the following plan for all of you to poke holes in. I'm not sure if I'm reinventing the CrazyStone structure here, but I think this one is slightly different. DATA STRUCTURE The "tree" is a enormous, preallocated array of Node objects. (Because this array is also being used as a hash table, the size of the table should be a prime number.) This is really a directed acyclic graph (DAG) rather than a tree, because a Node may be a child of more than one parent. Each Node contains the following information: A+1 "pointers" (in some sense) to child Nodes, where A is the area of the board. (The extra pointer is for the pass move.) Some of these pointers (initially, all of them) may be the special value UNEXPLORED. The number of runs through this Node so far. The number black wins through this Node so far. A Zobrist hash of the position represented by this Node. This must incorporate, in addition to the locations of stones on the board, the turn number (e.g., zero for the beginning of the game) and the number of consecutive passes. The turn number, stored explicitly. A forced leaf turn number, to be explained below. (Note that, in contrast to the current Orego structure, we won't need tails or a free list for this one.) GENERATING A MONTE CARLO RUN I want to separate the process of generating a Monte Carlo run from the process of modifying the tree for two reasons. First, this will make multithreading easier. Second, I will be able to incorporate recorded games into the tree by pretending that the program had played them. To generate a Monte Carlo run, I start at the root Node. Each move is chosen using UCT, based on UCB1-TUNED as described on p. 5 of the recent Gelly et al tech report on MoGo. As in the current Orego, this is done with a double-hashing scheme and in a way that always chooses an untried move if one exists. There is one complication here. The number of runs through the children might exceed the number of runs through the parent because of transpositions. In Gelly's notation, this means Tj(n) may exceed n. I THINK I can ignore this, as it will just give "oversampled" moves unusually narrow confidence windows. If we are not at a Node (because we're in an unexplored region of the search space), if the current Node has a forced leaf turn number greater than or equal to the root turn number, or if any child is found that is not at the correct turn number (because of a hash collision), the move is chosen randomly. INCORPORATING A GAME INTO THE TREE Again, we start at the root Node. We work down the tree, updating the run and black win count of each node encountered. If the child pointer we would be following is UNEXPLORED, we use the aforementioned Zobrist hash (modulo the table size) to find a Node to use as the child. This may be a Node that has already been initialized, a "fresh" Node (i.e., one that we can overwrite), or a Node that we can't overwrite. If the child has the correct turn number, either we have been down this path before or we have found a transposition. In either case, continue down the tree. If the child has a turn number that is lower than that of the root, it is an old node and can be overwritten. We reinitialize this one node, update its run and black win counts, and stop. Thus, every run adds at most one node to the tree. If the offending child is not so old that it can be overwritten, we must leave it alone lest it mess up another part of the tree. At this point, the parent's forced leaf turn number is set to the child's turn number; all moves from that parent will be random until a later point in the game when it is safe to overwrite the offending child. I welcome your input, Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] KGS Computer Go Tournaments
Only 28 bytes? What's in your nodes? That doesn't seem like enough room for 82 pointers to children. If you don't have pointers to children, how do you find the children's statistics for UCT? Play each move and examine the resulting hash code? Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 6, 2006, at 2:04 AM, Magnus Persson wrote: Quoting Chrilly <[EMAIL PROTECTED]>: Maybe there is a logical flaw in my calculation. In this case it would be nice if one of the UCT-programmers explains were all this memory is used. Valkyria currently preallocate 2 million records for the nodes of 28 bytes each which is about 50 MB. I could allocate more memory than that but at some point I had a problem with severe memory thrashing (*) so I decided to try using as little as possible. I also only have access to computer with are a little outdated. I think the huge factor here is that for every terminal node reached I add all children for that node, although only one of them is actually played. The reason is that then there is a lot of code (pattern matching) that thus only have to run once. I used to to only expand nodes that were selected to be played, but the overhead of the recomputing stuff and some nightmare bugs, made me sacrifice memory for simplicity and a 30% speedup. With old code I had no memory problems as you correctly predicted although my numbers differs somewhat from what you assumed. When I run out of nodes I simply delete all subtrees that has been visited less times than a threshold. --- I just ran a test having it think for one hour on the empty 9x9 board. It played on average 2500 simulations per second, but added 3 Nodes/second. This means that it fills memory in one minute. This is not an accident of course I designed it such that it should never need garbage collection the first minute it thinks. It played 222000 moves per second including all overhead. The principle variation was 7 ply deep. And here I limit the depth to nodes which has been visited at least 2000 times, the UCT tree goes much deeper than that but with this restricition the moves in the principle variation is always reasonable. The second best variation was searchd to 5 ply, and the remaining 4 was searched to 3 ply. Thanks to symmetry pruning Valkyria only searches 6 moves in the opening position. The first time garbage collection was done 1.9 Mnodes were freed which is close to 100%, so most of the initial tree is really unimportant nodes. The last time it freed only 0.7 MNodes which means that more than half of the nodes is actually is used for nodes that I do not dare to prune. I guess if I allocate 5 times more memory then I could play up to 10 hours without a serious problem but after 20 hours perhaps the program would do garbage collection all the time. -Magnus (*) In reality it turned out that my laptop easily overheats and shuts down all systems that generated heat, so I can probably allocate 5-10 times more memory without problems on my machines. ___ 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] language choices
9x9, 2 GHz Intel Core Duo iMac. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 6, 2006, at 2:59 PM, Don Dailey wrote: On Sun, 2006-12-03 at 19:53 -0800, Peter Drake wrote: A note: we're working on converting Orego back from C++ to Java, and we're getting 5,000 (totally random at this point) simulated games per second. We'll probably continue in this direction. Hi Peter, Which hardware is this on and what board size? - Don Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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/
Re: [computer-go] language choices
I'm getting about 98.2 for purely random games, but Orego has a turn limit that prevents a game from taking more than 162 moves on 9x9. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 6, 2006, at 3:48 PM, Don Dailey wrote: When playing 9x9 games from the opening position, what is the average number of moves per game? Lazaurs reports about 107.3 but I'm porting over to the D programming language and I'm getting about 101.4. I think there is a bug. What are others getting here? I think most of us use the same eye rule. I only count fully legal moves and I also do not count pass moves. I doubled checked, I'm not counting pass move with either program. - Don On Wed, 2006-12-06 at 15:05 -0800, Peter Drake wrote: 9x9, 2 GHz Intel Core Duo iMac. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 6, 2006, at 2:59 PM, Don Dailey wrote: On Sun, 2006-12-03 at 19:53 -0800, Peter Drake wrote: A note: we're working on converting Orego back from C++ to Java, and we're getting 5,000 (totally random at this point) simulated games per second. We'll probably continue in this direction. Hi Peter, Which hardware is this on and what board size? - Don Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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/
Re: [computer-go] experiments with D programming
On Dec 6, 2006, at 9:36 PM, Don Dailey wrote: The equivalent C version (after I took out some optimizations) is doing 13,745.70 games per second on an old pentium 4. I'd really love to know what I'm doing wrong. I was never able to get more than about 6,000 games per second on a 2 GHz machine, even in C++. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Threads (was Re: [computer-go] experiments with D programming)
On Dec 7, 2006, at 9:05 AM, Don Dailey wrote: Are you trying to keep a lot of information updated? Mine only tries to play random games as fast as possible. It does not have the ability to undo moves - this is easily handled by copying state when you need this feature. I do have the undo ability, but I think it's done in (I think) a very efficient way. For example, when I want to undo a bunch of move at once (e.g., after a MC run) I just reduce a stack pointer. There is also about a 2 to 1 slowdown if you are not finding the random legal moves properly. I don't know if you are or not, but look at the recent emails on this, one of mine and one by Lex Luthor - or was it Lukasz Lew? I think my technique here is faster than those recently described, because I don't bother building a data structure. In related news, I've just multithreaded my program and ... it's slower than the single-thread version! I'm pretty sure that this happened because I threaded it at too fine a scale; I'm incurring the overhead of thread creation for each MC run. I'll have to do some thinking about how to reorganize this. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Threads (was Re: [computer-go] experiments with D programming)
Those of you with multithreaded UCT programs -- how do you do it? Doesn't UCT pretty much require updating a common data structure after each MC run? Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 7, 2006, at 9:17 AM, Peter Drake wrote: In related news, I've just multithreaded my program and ... it's slower than the single-thread version! I'm pretty sure that this happened because I threaded it at too fine a scale; I'm incurring the overhead of thread creation for each MC run. I'll have to do some thinking about how to reorganize this. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Threads (was Re: [computer-go] experiments with D programming)
I'm afraid I don't follow you. I THINK I'm doing what you describe.
My Player object creates several threads, each of which plays a game.
After all of the games are completed, the main thread incorporates
them into the search tree. Here's the Java:
timer.schedule(interrupt, MSEC_PER_MOVE);
while (!currentThread().isInterrupted()) {
// Create and start the threads
for (int i = 0; i < NUMBER_OF_THREADS; i++) {
runnables[i].prepareForLongUndo();
threads[i] = new Thread(runnables[i]); // I suspect this is the
expensive part
threads[i].start();
}
// Wait for all of the threads to finish (code omitted)
// Incorporate games
for (int i = 0; i < NUMBER_OF_THREADS; i++) {
incorporateRun(runnables[i].getBoard());
runnables[i].longUndo();
}
}
The problem is that a single MC run takes about 1/5 of a millisecond,
so it's not worth the overhead of putting it off into another thread.
I need some way to tell a thread to do many runs, then somehow
incorporate the multiple runs back into my search tree. I believe
others are already doing this and I'm curious how.
Remi? Sylvain?
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 9:41 AM, steve uurtamo wrote:
Those of you with multithreaded UCT programs -- how
do you do it?
Doesn't UCT pretty much require updating a common
data structure
after each MC run?
you could hand a job (starting position) to each
thread and have the thread manager update a shared
memory segment that they all can read from (but not
write to).
or are you talking about networked threads?
s.
__
__
Have a burning question?
Go to www.Answers.yahoo.com and get answers from real people who know.
___
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: Threads (was Re: [computer-go] experiments with D programming)
On Dec 7, 2006, at 9:42 AM, [EMAIL PROTECTED] wrote: Hello, Those of you with multithreaded UCT programs -- how do you do it? Doesn't UCT pretty much require updating a common data structure after each MC run? in MoGo we simply protect the tree access using a mutex, so only the MC simulations are run in parallel. The tree update is done by only one thread at a time. I think this not so efficient, but at least it is very simple, and efficient enough comparing to other challenges :). Is that access to the entire tree, or to each node? (The latter seems like an awful lot of mutexes (mutices?).) It would have to be set up so that any number of threads can read from the tree at once, but only one can write to it, and nobody can read while someone is writing. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Threads (was Re: [computer-go] experiments with D programming)
Aha! Now I get it. You only have to look at the tree during the
opening part of the run. Once you've fallen off and are making purely
random moves, you can let someone else use the tree.
Thanks!
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 9:59 AM, [EMAIL PROTECTED] wrote:
The problem is that a single MC run takes about 1/5 of a millisecond,
so it's not worth the overhead of putting it off into another thread.
Creating a thread for each MC simulation is clearly very costy.
I need some way to tell a thread to do many runs, then somehow
incorporate the multiple runs back into my search tree. I believe
others are already doing this and I'm curious how.
Yes we do that in MoGo.
I try to explain the algorithm here:
3 methods:
DescendTheTreeUsingUCT
MCSimulation
UpdateTheTree
At the beginning of a genmove, we create n threads
(n==nbProcessors), then
each thread calls the method "think" which is:
think {
while (time left) {
mutex.lock()
DescendTheTreeUsingUCT
mutex.unlock()
MCSimulation
mutex.lock()
UpdateTheTree
mutex.unlock()
}
}
Each thread has his own data for all except tree (for exemple we
keep the
current sequence, ...).
Is it cleared that way ?
___
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: Threads (was Re: [computer-go] experiments with D programming)
Got it -- now I'm getting just under 10,000 games per second! Whee!
(FWIW, I actually don't have the UCT part in there yet -- these are
purely random games.)
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 10:07 AM, Peter Drake wrote:
Aha! Now I get it. You only have to look at the tree during the
opening part of the run. Once you've fallen off and are making
purely random moves, you can let someone else use the tree.
Thanks!
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 9:59 AM, [EMAIL PROTECTED] wrote:
The problem is that a single MC run takes about 1/5 of a
millisecond,
so it's not worth the overhead of putting it off into another
thread.
Creating a thread for each MC simulation is clearly very costy.
I need some way to tell a thread to do many runs, then somehow
incorporate the multiple runs back into my search tree. I believe
others are already doing this and I'm curious how.
Yes we do that in MoGo.
I try to explain the algorithm here:
3 methods:
DescendTheTreeUsingUCT
MCSimulation
UpdateTheTree
At the beginning of a genmove, we create n threads
(n==nbProcessors), then
each thread calls the method "think" which is:
think {
while (time left) {
mutex.lock()
DescendTheTreeUsingUCT
mutex.unlock()
MCSimulation
mutex.lock()
UpdateTheTree
mutex.unlock()
}
}
Each thread has his own data for all except tree (for exemple we
keep the
current sequence, ...).
Is it cleared that way ?
___
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] The Two Rules of Monte Carlo Optimization
Let me propose the following rules for comment: 1) The vast majority of your time is spent making RANDOM moves (beyond the leaves of your tree). 2) Almost none of your nodes have more than one child. These, along with the KISS principle, seem to point to a lot of optimizations in both time and space. For example, that latter suggests that the first child / next sibling tree representation mentioned here recently is a much better idea than the array-of- children representation I'm currently using. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Threads (was Re: [computer-go] experiments with D programming)
Precisely: I'm getting almost optimal use of my dual-core processor.
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 10:47 AM, Don Dailey wrote:
On Thu, 2006-12-07 at 10:24 -0800, Peter Drake wrote:
Got it -- now I'm getting just under 10,000 games per second! Whee!
Hold on, I thought the non-threaded version was doing 5,000? What
exactly did you change? Or are you just using 2 processors more
efficiently to get 10,000 games?
- Don
(FWIW, I actually don't have the UCT part in there yet -- these are
purely random games.)
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 10:07 AM, Peter Drake wrote:
Aha! Now I get it. You only have to look at the tree during the
opening part of the run. Once you've fallen off and are making
purely random moves, you can let someone else use the tree.
Thanks!
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 9:59 AM, [EMAIL PROTECTED] wrote:
The problem is that a single MC run takes about 1/5 of a
millisecond,
so it's not worth the overhead of putting it off into another
thread.
Creating a thread for each MC simulation is clearly very costy.
I need some way to tell a thread to do many runs, then somehow
incorporate the multiple runs back into my search tree. I believe
others are already doing this and I'm curious how.
Yes we do that in MoGo.
I try to explain the algorithm here:
3 methods:
DescendTheTreeUsingUCT
MCSimulation
UpdateTheTree
At the beginning of a genmove, we create n threads
(n==nbProcessors), then
each thread calls the method "think" which is:
think {
while (time left) {
mutex.lock()
DescendTheTreeUsingUCT
mutex.unlock()
MCSimulation
mutex.lock()
UpdateTheTree
mutex.unlock()
}
}
Each thread has his own data for all except tree (for exemple we
keep the
current sequence, ...).
Is it cleared that way ?
___
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/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Threads (was Re: [computer-go] experiments with D programming)
On Dec 7, 2006, at 11:08 AM, Don Dailey wrote: On Thu, 2006-12-07 at 09:17 -0800, Peter Drake wrote: I do have the undo ability, but I think it's done in (I think) a very efficient way. For example, when I want to undo a bunch of move at once (e.g., after a MC run) I just reduce a stack pointer. BINGO! I'm pretty sure that is your problem. My program does this too, but not during the random games. I make single copy of the current state then play a random game from that copy. Obviously, it's faster to place a single stone on an existing board - than to make a copy and then place a stone on the copy. I'm not sure that would be true for Orego; playing moves involves a bunch of operations on bit vectors, so there's plenty of writing to memory anyway. The amount of copying I'm doing is pretty trivial; I'm copying the 9 (or 19) ints that represent the board, but I'm not copying a HashSet or anything silly like that. In the search tree part of the game, (not the random simulation part) I make state copies, do Zobrist hashing and full repetition checks and other stuff - the tree part is cheap. Agreed -- the playing of moves is the expensive part. No matter how you implement undo - it will cost you dearly whether by state copy or keeping stacks of information updated. Are you one of those who advocates ignoring the ko rule during MC searches? I'm actually pretty happy with 10,000 runs/second (9x9). I'm not so happy with my tree data structure, so I'm going to go mess with that... Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] firstChild/nextSibling in a DAG
(This is all within the context of Monte Carlo.) Is anyone storing a search DAG (as opposed to a tree) and using the firstChild/nextSibling representation? I'm having trouble seeing how this would work, since when you traverse children (e.g., in UCT) you have to know which move is associated with which child node. If a node might have more than one parent, the node can't store its last move. Any clever solutions? If not, any opinions (or better yet, evidence) as to whether the space savings or the DAG transposition table is more valuable? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] firstChild/nextSibling in a DAG
I can avoid the ko problem by storing the depth of each node and never creating a link from a node at depth d except to a node at depth d+1. This prevents any cycles, at the (minimal, in my opinion) cost of omitting transpositions of different lengths. I need the move for two reasons: 1) In performing UCT, I need to traverse my children, find the value and confidence bound for each one, and then choose the move leading to the "best" one. This requires knowing which move leads to which child node. 2) In testing, I like to be able to print out the tree. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 7, 2006, at 2:58 PM, House, Jason J. wrote: DAG's have a problem with graph history, especially with super ko considerations. Do you need the parent play for more than ko considerations? -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Peter Drake Sent: Thursday, December 07, 2006 5:47 PM To: Computer Go Subject: [computer-go] firstChild/nextSibling in a DAG (This is all within the context of Monte Carlo.) Is anyone storing a search DAG (as opposed to a tree) and using the firstChild/nextSibling representation? I'm having trouble seeing how this would work, since when you traverse children (e.g., in UCT) you have to know which move is associated with which child node. If a node might have more than one parent, the node can't store its last move. Any clever solutions? If not, any opinions (or better yet, evidence) as to whether the space savings or the DAG transposition table is more valuable? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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/
Re: Threads (was Re: [computer-go] experiments with D programming)
I see. I only recently had this realization that the within-tree and purely-random parts of the search were deeply different. I'll take a shot at this. Thanks, Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 7, 2006, at 3:21 PM, Don Dailey wrote: Peter, I also want to point out that I DO do full KO testing, but it's just in the tree search - it's the Monte/Carlo part that's a waste of time. I say that because monte/carlo is a RANDOM search, it's not going to deal with any positional finesses and such. It's too expensive even to maintain the incremental hash key - so I have 2 move make routines, one that maintains it and one that doesn't. - Don On Thu, 2006-12-07 at 18:13 -0500, Don Dailey wrote: On Thu, 2006-12-07 at 14:09 -0800, Peter Drake wrote: In the search tree part of the game, (not the random simulation part) I make state copies, do Zobrist hashing and full repetition checks and other stuff - the tree part is cheap. Agreed -- the playing of moves is the expensive part. No matter how you implement undo - it will cost you dearly whether by state copy or keeping stacks of information updated. Are you one of those who advocates ignoring the ko rule during MC searches? Not simple KO, but more than simple KO is a waste of valuable processor time. Whatever you are doing or not doing, you probably could be 3X faster. I don't know why you are happy with 10,000, especially when most of the programs get more with 1 processor. Unless of course you are getting something for it, such as valuable information that can be used to improve the monte carlo part of the search. - Don ___ 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: Threads (was Re: [computer-go] experiments with D programming)
Okay, so I created a FastSloppyBoard class that works like a Board but doesn't maintain ko or Zobrist information. Not all the wires are plugged in yet (e.g., I'm not incorporating the results into the tree), but this got me about a 20% improvement in run per second. For those of you keeping track, that's about 12,000 pure MC runs per second with the dual-core processor. I seem to have reached the point of diminishing returns here. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 7, 2006, at 3:21 PM, Don Dailey wrote: Peter, I also want to point out that I DO do full KO testing, but it's just in the tree search - it's the Monte/Carlo part that's a waste of time. I say that because monte/carlo is a RANDOM search, it's not going to deal with any positional finesses and such. It's too expensive even to maintain the incremental hash key - so I have 2 move make routines, one that maintains it and one that doesn't. - Don On Thu, 2006-12-07 at 18:13 -0500, Don Dailey wrote: On Thu, 2006-12-07 at 14:09 -0800, Peter Drake wrote: In the search tree part of the game, (not the random simulation part) I make state copies, do Zobrist hashing and full repetition checks and other stuff - the tree part is cheap. Agreed -- the playing of moves is the expensive part. No matter how you implement undo - it will cost you dearly whether by state copy or keeping stacks of information updated. Are you one of those who advocates ignoring the ko rule during MC searches? Not simple KO, but more than simple KO is a waste of valuable processor time. Whatever you are doing or not doing, you probably could be 3X faster. I don't know why you are happy with 10,000, especially when most of the programs get more with 1 processor. Unless of course you are getting something for it, such as valuable information that can be used to improve the monte carlo part of the search. - Don ___ 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] firstChild/nextSibling in a DAG
I was also hoping to use my DAG as a transposition table, so I could use the Zobrist hash of the current position to find where the child node would be if it existed. If the space was already occupied (by a node at the right depth), I would have a transposition. If each "node" might really require several nodes, this trick won't work. Oh, well. I guess I was trying to kill too many birds with the same stone. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 7, 2006, at 3:46 PM, Anders Kierulf wrote: Is anyone storing a search DAG (as opposed to a tree) and using the firstChild/nextSibling representation? When you traverse children (e.g., in UCT) you have to know which move is associated with which child node. If a node might have more than one parent, the node can't store its last move. SmartGo uses a DAG for tactical proof number search, and is using the firstChild/nextSibling representation. Different moves leading to the same position are given their own node (a twin node), and that node then points to the base node on the same level. Any information about the position is stored in the base node; any information related to the move played is stored in the twin nodes. For tactical search, a DAG is a clear benefit; the extra space is certainly worth it. In my current implementation, each node contains pointers to the base node and to the next twin node, but that could be reduced to a single pointer linking the twin nodes in a circular list plus a bit to indicate the designated base node. Anders Kierulf www.smartgo.com ___ 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] firstChild/nextSibling in a DAG
Crikey -- it worked! Incorporating moves into the tree with a transposition table, I'm still getting 10,000 games per second with the dual cores. The games are still purely random -- UCT is tomorrow's job. I went ahead and (*shudder*) created the TwinNode objects on the fly, rather than maintaining a pool of them, since they're much rarer than true Nodes. It looks like I create about one transposition in every ten runs using purely random games, but I expect this will drop off precipitously under UCT. If I'm wrong, I can always add a node pool. Orego is hugely faster and uses an order of magnitude less memory than it did 24 hours ago. Thanks, everyone! Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 7, 2006, at 10:07 PM, Anders Kierulf wrote: I was also hoping to use my DAG as a transposition table, so I could use the Zobrist hash of the current position to find where the child node would be if it existed. If the space was already occupied (by a node at the right depth), I would have a transposition. If each "node" might really require several nodes, this trick won't work. Oh, well. I guess I was trying to kill too many birds with the same stone. I'm solving that by using a separate hash table that points to the base node for each position. But it seems like you should be able to use the DAG directly as a transposition table too, with the twin nodes implemented as an overflow list. Anders Kierulf www.smartgo.com ___ 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] When to pass in random games?
I had been including pass as one of the possible random moves, just as likely as any other. I reasoned that, if there is a seki on the board, passing might be the best move. On further thought, it's almost certainly more important to avoid leaving dead stones on the board. I changed this and took a big performance hit because the games run longer now. I'm down to 3400 games / sec with one thread, roughly 6000 with two. I think it's worth it, though, because the random games will be more accurate. Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Unsigned random numbers in Java
I tried creating a random number generator java.util.Random rand = new java.util.Random() and then asking it for a random int rand.nextInt() which I would then take modulo the board size to choose a random point. Since ints in Java are signed, I would have to take the absolute value of this int before the modulo operaton. (As in C/C++, Java's % operator does not behave as modulo, in the mathematical sense, when the first argument is negative. It might more accurately be called "remainder".) This almost always works, but once in a very great while I would get a negative result anyway. I eventually hunted down the problem, which is explained in the API for the java.lang.Math.abs() method: "Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative." Yikes! So, I'll have to check the sign of my result and try again in those rare (but not ignorably rare) instances where it is negative. I hope this saves some time for the next person to encounter this problem. Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Slow KGS computer Go Tournament idea
Ah. Orego will have the "ponder" feature soon. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 20, 2006, at 3:11 PM, Don Dailey wrote: ponder means to "use the opponents time to think" - Don On Wed, 2006-12-20 at 23:56 +0100, Ephrim Khong wrote: hi, steve uurtamo wrote: this might be a counterproductive idea, but does anyone who mc's also ponder? a quick question from a non-nativ english speaker: what does "ponder" mean here? thanks eph ___ 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/
Time Zones (was Re: [computer-go] KGS Slow tournament)
An interesting report. I have a question about a line near the end where you address the two meanings of "UCT": "UCT as applied to times stands for Universal Coordinate Time. It is the same, for most practical purposes including ours, as GMT, Greenwich Mean Time, the time zone based on London, England." I had an experience where I set a Mac OS X "Dashboard Widget" clock to London time, and it was an hour off from UCT. I could only get the correct time by using Dakar as the city. Does London use something like Daylight Savings Time, making London time the same as GMT/UCT only part of the year? Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Dec 23, 2006, at 10:58 AM, Nick Wedd wrote: I have written up the week's Slow KGS bot tournament. My report, which is fuller than usual, is at http://www.weddslist.com/kgs/past/s1/index.html I think that, despite various accidents, the event was a success. I plan to hold another one, but only after the next release of the KGS server fixes the "five minute rule" bug. Congratulations to the winner, MoGoBot19! Nick -- Nick Wedd[EMAIL PROTECTED] ___ 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] Allocating remaining time
How much time should a program spend on each move? If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? Peter Drake Assistant Professor of Computer Science Lewis & Clark College 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] Testing against gnugo
I used the Python version and it worked almost perfectly on the first try -- thanks! Here's the command I used: python /Applications/gnugo-3.6/interface/gtp_examples/twogtp.py -- black '' --white '/usr/local/bin/gnugo -- mode gtp --quiet --level 1 --never-resign --chinese-rules --capture- all-dead' --verbose 2 --komi 7.5 --size 9 It played out the game, but at the end this happened: Black passes A B C D E F G H J 9 O O . O . O O O . 9 8 O O O O O O . O O 8 7 . O O . O O O . O 7 6 O O O O O . O O . 6 5 O O O O O O . O O 5 4 . O O . O . O O . 4 3 O O + O . O O . O 3 2 O . O O O O O O . 2 WHITE (O) has captured 51 stones 1 . O . O . O . O O 1 BLACK (X) has captured 0 stones A B C D E F G H J Game 1: W+88.5 ERROR: GTP Command failed: unknown command Game 1: ERROR: GTP Command failed: unknown command W+88.5 White: 3.400s CPU time I interpret this to mean that the script sent "W+88.5" as a GTP command to my program, which of course didn't understand it. Is this standard GTP or something specific to GNU Go? Would a reasonable response be to silently acknowledge any command whose second character is "+"? (Lest Orego's honor be besmirched, I should clarify that I was only allowing Orego one second per move while testing out the protocol. Hopefully it won't get wiped off the board by GNU Go level 1 if I give Orego more time.) Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 20, 2006, at 3:44 AM, alain Baeckeroot wrote: Le vendredi 17 novembre 2006 18:41, Peter Drake a écrit : Orego speaks GTP, as does gnugo. I'd like to run a bunch of games (say, 50) between them to see how many Orego wins. Does anyone have a handy script (ideally bash or Python) for this? Thanks, Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ Hi In GNU Go package you have tools interface/gtp_examples/twogtp.xyz in various languages. my 2 cents Alain ___ 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] Can Go be solved???... PLEASE help!
There are a number of definitions of solved, ranging from "a program exists that can beat any human" to "we can quickly determine, for any position, the best move and the result under optimal play". In the latter strong sense, I believe Go has only been solved up to 5x5, maybe 6x6. There are some games, such as Hex, for which we know who wins from the starting position given optimal play, but we don't know how to figure out the best move. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Jan 12, 2007, at 8:45 AM, terry mcintyre wrote: From http://senseis.xmp.net/?7x7BestPlay it looks like 7x7 Go may already have been solved. 5x5 was solved in 2002, according to http://erikvanderwerf.tengen.nl/5x5/5x5solved.html AFAIK, 9x9 Go has not been solved yet. 19x19 Go will surely exceed the capabilities of computers in my lifetime, I suspect. -- Terry McIntyre - Original Message From: Chris Fant <[EMAIL PROTECTED]> To: computer-go Sent: Friday, January 12, 2007 8:16:35 AM Subject: Re: [computer-go] Can Go be solved???... PLEASE help! Seems like a silly title. Any game of perfect information that has a clear rule set can be solved. Plus, some would argue that any Go already is solved (write simple algorithm and wait 1 billion years while it runs). A better question is, "Can Computer Go Surpass Human Go?" But again, clearly it will. It's just a question of how long until it occurs. On 1/12/07, Mehdi Ahmadi <[EMAIL PROTECTED]> wrote: > Hello & thank in advance for any interests/ responses. > > I'm unfortunately (or not) doing a dissertation as part of my final year > project (undergraduate) on the game of Go. The exact title is: "Can the game > of go be solved? Analysis of computational methodologies for go." And I have > included my overall objectives below. > > I have many works from different people on different aspects of Computer Go > which would make for great inclusion at different parts - but overall I am > still gravely struggling. In reviewing some of these my greatest difficulty > is in understanding exactly how say Monte-Carlo-UCT or even Alpha- Beta > testing (pruning, etc) occur so as to be able to give a simplified depiction > (illustrated or otherwise) of the process. Can this be done without having > to go through the source code of say something like GNU Go? > > Also another difficulty I've had is in trying to get further information on > the commonly referred top ranking packages, Handtalk, Go++, Many Faces of > Go, etc due to their commercial nature? (the only thing I've been able to > find which is a bit outdated: > http://www.inventivity.com/OpenGo/Papers/EditedGoPapers.html). > > Lastly can any general categorisation - distinction be made of current > approach/ implementations in trying to 'solve' Go. in comparison to say > traditional disciplines used in trying to solve games (complex or otherwise) > via computer? To put simply I am trying to have some core root comparison in > current methodologies (if there is any?). > > If anyone has any suggestions/ guidance on anything mentioned - I would be > eternally indebted. > > == > 5.1 OBJECTIVES > . To concisely review all game playing aspects of Go (rules, openings, > middle game, etc) and its relevance to the complication of meaningful > measurements of interest. > . To evaluate, gain and develop further understanding of specific game > aspects including (eg): > - Representation: > . Eyes > . life-and-death > . territory estimates and weakness > - Move Evaluation: > . Territorial and strategic affluence. > . Address specific and current implementation methodologies including: > - Search algorithms (Alpha-Beta - local/global, Monte-Carlo -UCT) > - Move Generation > - Positional Evaluation (Patterns, Neural Networks) > . To detail inadequacies in research and reasons for shortfalls where > applicable. > > > > ___ > 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/ We won't tell. Get more on shows you hate to love (and love to hate): Yahoo! TV's Guilty Pleasures list. ___ 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] Testing against gnugo
Now there's an additional curiosity. The log of moves printed out by the GNU Go twogtp.py script seems to sometimes insert gratuitous passes or allow one player to play more than once in a row: Black plays c9 White plays B9 Black plays d7 White plays D6 Black plays h6 White plays D4 White passes White plays D8 Black plays c8 White plays D9 Black plays d5 Later, the script sent my program "genmove black" twice in a row, which of course confused it. What's going on here? Has anyone else run into these problems? Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Jan 12, 2007, at 9:05 AM, Peter Drake wrote: D'oh! I turns out this was the result of my program not handling the final_score command. It works fine now. I hope this helps others, Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Jan 12, 2007, at 8:47 AM, Peter Drake wrote: I used the Python version and it worked almost perfectly on the first try -- thanks! Here's the command I used: python /Applications/gnugo-3.6/interface/gtp_examples/twogtp.py -- black '' --white '/usr/local/bin/gnugo -- mode gtp --quiet --level 1 --never-resign --chinese-rules -- capture-all-dead' --verbose 2 --komi 7.5 --size 9 It played out the game, but at the end this happened: Black passes A B C D E F G H J 9 O O . O . O O O . 9 8 O O O O O O . O O 8 7 . O O . O O O . O 7 6 O O O O O . O O . 6 5 O O O O O O . O O 5 4 . O O . O . O O . 4 3 O O + O . O O . O 3 2 O . O O O O O O . 2 WHITE (O) has captured 51 stones 1 . O . O . O . O O 1 BLACK (X) has captured 0 stones A B C D E F G H J Game 1: W+88.5 ERROR: GTP Command failed: unknown command Game 1: ERROR: GTP Command failed: unknown command W+88.5 White: 3.400s CPU time I interpret this to mean that the script sent "W+88.5" as a GTP command to my program, which of course didn't understand it. Is this standard GTP or something specific to GNU Go? Would a reasonable response be to silently acknowledge any command whose second character is "+"? (Lest Orego's honor be besmirched, I should clarify that I was only allowing Orego one second per move while testing out the protocol. Hopefully it won't get wiped off the board by GNU Go level 1 if I give Orego more time.) Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 20, 2006, at 3:44 AM, alain Baeckeroot wrote: Le vendredi 17 novembre 2006 18:41, Peter Drake a écrit : Orego speaks GTP, as does gnugo. I'd like to run a bunch of games (say, 50) between them to see how many Orego wins. Does anyone have a handy script (ideally bash or Python) for this? Thanks, Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ Hi In GNU Go package you have tools interface/gtp_examples/ twogtp.xyz in various languages. my 2 cents Alain ___ 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] Computer Go tournament at US Go Congress
I'm still trying to set up a Computer Go tournament at the US Go Congress, August 2-9 here in Portland, Oregon. We finally heard back from the where we're holding the Congress, and their policy on using their computer labs appears to be completely unworkable: Begin forwarded message: Also, these computer are pretty locked down, security-wise, meaning that anything needing to be installed has to be done through the User Support Office, with a minimum of four weeks notice. Any thoughts on what to do now? I can't think of anything better than having people bring their own machines. (Since there will be prize money involved, we can't reasonably allow remote connections.) I'm also trying to get some funding from industry, but I'm not holding my breath on that one. 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] Computer Go tournament at US Go Congress
Can you expand on that? I'm not familiar with VMWare. I suspect many programmers here would be concerned about the performance hit of working on a virtual machine. Peter Drake http://www.lclark.edu/~drake/ On Mar 18, 2008, at 7:46 PM, Michael Williams wrote: If they install VMWare, would the virtual machines be as locked down? Peter Drake wrote: I'm still trying to set up a Computer Go tournament at the US Go Congress, August 2-9 here in Portland, Oregon. We finally heard back from the where we're holding the Congress, and their policy on using their computer labs appears to be completely unworkable: Begin forwarded message: Also, these computer are pretty locked down, security-wise, meaning that anything needing to be installed has to be done through the User Support Office, with a minimum of four weeks notice. Any thoughts on what to do now? I can't think of anything better than having people bring their own machines. (Since there will be prize money involved, we can't reasonably allow remote connections.) I'm also trying to get some funding from industry, but I'm not holding my breath on that one. 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/
Re: [computer-go] Computer Go tournament at US Go Congress
Thanks to everyone for all the comments. Another question: Should the tournament be 9x9, 19x19, or both? 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] BGA adopts AGA rules
From the American Go Association e-journal: THIS JUST IN: BRITS ADOPT U.S. RULES: The British Go Association officially adopted AGA rules of go at last weekend's British Go Congress at Hastings, reports BGA President Ron Bell, who was re- elected for another term. "AGA rules have two major benefits," Bell tells the E-Journal, "First, they neatly allow either the Japanese or Chinese styles of counting the score to be used. Second, the use of pass stones allows any disagreement between the players to be resolved by simply resuming play. Since the BGA Council adopted AGA rules last October, they've been used successfully in about half a dozen tournaments. We do have some members who wanted to keep the previous Japanese rule set - but the motion at the AGM to approve the change was passed with no opposition." I'm not saying we should adjust our programs just yet, but we may be getting closer to an international standard. Of course, it's irrelevant until Japan, China, and Korea get on board. You can find the rules in question here: http://www.cs.cmu.edu/~wjh/go/rules/AGA.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 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] Another beginner question: string management
Carter: It might help to look at the Orego code. In the doc directory, there's a file called Board-data-structures-explained.pdf. Orego's current board-handling data structures are basically a Java "translation" of Lukasz Lew's Library of Effective Go Routines (EGO), although I've gone to somewhat greater length to explain them. If you find C++ easier to read than Java, by all means use Lew's code. Orego is here (you'll have to download and unpack the latest .jar): http://www.lclark.edu/~drake/Orego.html Peter Drake http://www.lclark.edu/~drake/ On May 16, 2008, at 4:29 PM, Carter Cheng wrote: I am having some difficulties deciding on a string management scheme which copes gracefully with merging groups. A first glance for me this seems like it is quite a slow operation akin to capture. The problem is how to have each stone vertex know which chain record to look up for information. I am curious how this is done in the current generation of MC bots. Is the naive way the best i.e. going through each stone and updating the pointer to the record? Regards, Carter. ___ 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] Another beginner question: string management
On May 16, 2008, at 5:41 PM, Carter Cheng wrote: Thanks for pointing to the existence of this document. It clarifies some things about a conventional light playout UCT design(It also answered a question about pseudo-liberties I guess they are equivalent to what I term |multi set liberty|). From the code I gather Orego (thus libEgo) does update all the pointers to the chain record. When two chains are merged, the chainIds for the stones in only one of them (ideally, the smaller one) have to be changed. This takes time proportional to the size of the smaller chain. Also the two circular linked lists have to be appended, which takes constant time. See orego.core.Board.mergeChains(). There are still a few design tradeoffs I dont quite understand such as caching adjacent vertex properties in the vertex. How much and why does this result in a speedup? Do you mean neighborCounts? This has a number of uses. It allows you to immediately: 1) Eliminate most points from being "eyelike". See isEyelike(). 2) Determine the initial pseudoliberty count of a newly-placed stone (before merging with neighboring chains). See placeStone(). 3) Tell whether you need to check for single-stone suicide or simple ko violation. See playNonPassUnoccupied(). 4) Tell whether a point is surrounded when counting the score at the end of a playout. See playoutScore(). Lukasz could say more -- he spent a lot of time optimizing the heck out of this stuff. 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] Tournament at US Go Congress
Please find below preliminary rules for the computer Go tournament to be held at this year's US Go Congress in Portland, Oregon. Obviously, some details are being finalized. If you can think of anything here (or not here) that could cause trouble, please let me know ASAP. I'd like the tournament to run as smoothly as possible. Peter Drake http://www.lclark.edu/~drake/ Tournament Director Peter Drake (AND CO-DIRECTOR?) Description This 19x19 tournament is for computer programs only. While there have been notable breakthroughs in recent years, computer Go remains an open problem in artificial intelligence research. Location NEED LOCATION Schedule Round 1 1:00 PM, Sunday, August 3 Round 2 3:30 PM, Sunday, August 3 Round 3 7:00 PM, Sunday, August 3 Round 4 1:00 PM, Monday, August 4 Round 5 3:30 PM, Monday, August 4 Round 6 7:00 PM, Monday, August 4 Round 7 1:00 PM, Tuesday, August 5 Round 8 3:30 PM, Tuesday, August 5 Round 9 7:00 PM, Tuesday, August 5 Time Limits 60 minutes per player, no byo-yomi. Rules To give programmers as much time as possible to work out networking bugs, we will use the same rules as the monthly KGS computer go tournaments. These rules can be found at http://www.weddslist.com/ kgs/. Of particular note are that programs must implement GTP and that Chinese (area) scoring is used. All hardware must be physically present in the competition room. Programmers may bring their own hardware; we will also provide some machines (NEED DESCRIPTION). This is a formal tournament, meaning that people may not, for example, enter a-modified version of a public-domain program such as GNU Go. (See the web page above for a more detailed description.) Programmers who cannot attend the Congress may send alternate operators. Prizes Prize money has been donated by Hierarchical Systems Research Foundation and OTHER DONORS: 1st place $500 2nd place $300 3rd place $150 4th place $50 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tournament at US Go Congress
On Jun 3, 2008, at 6:41 PM, David Fotland wrote: You need to specify how pairings will be made and how ties will be broken, etc. I attached the announcement from one of the US computer go tournaments I ran at the go congress as an example. The short story is "as in the monthly KGS tournaments". Nick W. or Bill S., can you provide more info here? Will the games be played on KGS using network connections from the contest site, or will you provide a referee program? If the games are played on KGS, why do people have to drag their computers to Portland? We will use KGS. There are three reasons for having competitors present in person: 1) As an anti-cheating measure. Since there is money at stake, we don't want to make it trivial for a strong human player to masquerade as a program. 2) As a sort of scientific conference, giving Go programmers an opportunity to network in a way that is not possible over email. 3) To create an event on which the media can report. 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] Tournament at US Go Congress
On Jun 4, 2008, at 7:07 PM, David Doshay wrote: I would like to strongly suggest that enough rounds be run that every program plays every other program twice, once as B and once as W. This seems like a good idea, but I have two concerns: 1) Can the KGS tournament system support this? Nick, Bill? 2) If we get, say, a dozen programs, each program will have to play 22 games, right? That's conceivably 44 hours. I was at first mystified by David Fotland's comment that "A round robin can get many more rounds in the same time." Are you pointing out that, if programs resign, other rounds can begin? Do a lot of the KGS monthly tournament games end in resignation with a lot of time left on the clock? Monte Carlo players tend to use almost all of their time. Perhaps I should say something like, "Time permitting, we will run a double round-robin tournament." As set, the schedule does not have breaks for meals, and I think that for the health and happiness of the programmers, such breaks would be a good idea. I know that 3 days in a row without a proper dinner break will be very hard on my stomach. For what it's worth, the current schedule has dinner from 5:30-7:00. 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] US Go Congress Computer Tournament: Who's Playing
We'd like to get an estimate of numbers. Who's planning to enter the US Go Congress Computer Go Tournament? Here is the latest version of the info on the tournament: Computer Go Tournament Tournament Director Peter Drake (AND CO-DIRECTOR?) Description This 19x19 tournament is for computer programs only. While there have been notable breakthroughs in recent years, computer Go remains an open problem in artificial intelligence research. Location NEED LOCATION (at US Go Congress in Portland, Oregon) Schedule Rounds will be played as games are completed, beginning at 1:00 PM, Sunday, August 3. Time permitting, we hope to run a double round- robin tournament. Time Limits 60 minutes per player, no byo-yomi. If there are many entrants, we may reduce this to 45 minutes per player. Rules To give programmers as much time as possible to work out networking bugs, we will use the same rules as the monthly KGS computer go tournaments. These rules can be found at http://www.weddslist.com/ kgs/. Of particular note are that programs must implement GTP and that Chinese (area) scoring is used. All hardware must be physically present in the competition room. Programs may not rely on any remote resources. Programmers must be able to roughly explain and demonstrate the program’s “thought process”, e.g., by showing logging output as the program responds to an arbitrary position. Programmers may bring their own hardware; we will also provide some machines (NEED DESCRIPTION). Programs must be entered by the authors, although authors who cannot attend the Congress may sent alternate operators. If a program is based on another program (e.g., GNU Go or MoGo), it must contain a significant amount of new code. The tournament director has final say over what constitutes a "significant amount"; as a guideline, a radically different search algorithm or life-and-death evaluator would be significant, but tweaking some parameters or adding new patterns to a database would not. Such derivative entries must include written permission from the authors of the original program. If you have any doubts about the eligibility of your program, contact the TD before buying an airline ticket! Prizes Prize money has been donated by Hierarchical Systems Research Foundation and other anonymous donors. At a minimum, the following prizes will be awarded: 1st place $400 2nd place $200 3rd place $100 4th place $50 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] Re: US Go Congress Computer Tournament: Who's Playing
So far we've had two entries, both with caveats. Could others please sound off on whether you're coming, and if not, why not? 1) Can't afford the time 2) Can't afford the money 3) Don't feel my program is strong enough to compete 4) Have a conflicting event 5) Other (please explain) Thanks, Peter Drake http://www.lclark.edu/~drake/ On Jun 9, 2008, at 10:25 AM, Peter Drake wrote: We'd like to get an estimate of numbers. Who's planning to enter the US Go Congress Computer Go Tournament? Here is the latest version of the info on the tournament: Computer Go Tournament Tournament Director Peter Drake (AND CO-DIRECTOR?) Description This 19x19 tournament is for computer programs only. While there have been notable breakthroughs in recent years, computer Go remains an open problem in artificial intelligence research. Location NEED LOCATION (at US Go Congress in Portland, Oregon) Schedule Rounds will be played as games are completed, beginning at 1:00 PM, Sunday, August 3. Time permitting, we hope to run a double round- robin tournament. Time Limits 60 minutes per player, no byo-yomi. If there are many entrants, we may reduce this to 45 minutes per player. Rules To give programmers as much time as possible to work out networking bugs, we will use the same rules as the monthly KGS computer go tournaments. These rules can be found at http://www.weddslist.com/ kgs/. Of particular note are that programs must implement GTP and that Chinese (area) scoring is used. All hardware must be physically present in the competition room. Programs may not rely on any remote resources. Programmers must be able to roughly explain and demonstrate the program’s “thought process”, e.g., by showing logging output as the program responds to an arbitrary position. Programmers may bring their own hardware; we will also provide some machines (NEED DESCRIPTION). Programs must be entered by the authors, although authors who cannot attend the Congress may sent alternate operators. If a program is based on another program (e.g., GNU Go or MoGo), it must contain a significant amount of new code. The tournament director has final say over what constitutes a "significant amount"; as a guideline, a radically different search algorithm or life-and-death evaluator would be significant, but tweaking some parameters or adding new patterns to a database would not. Such derivative entries must include written permission from the authors of the original program. If you have any doubts about the eligibility of your program, contact the TD before buying an airline ticket! Prizes Prize money has been donated by Hierarchical Systems Research Foundation and other anonymous donors. At a minimum, the following prizes will be awarded: 1st place $400 2nd place $200 3rd place $100 4th place $50 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] Ladders and UCT
In Sunday's tournament, Orego lost a game embarrassingly by playing out a lost ladder. I know how to write a ladder checker in general, but I'm not sure how to incorporate such a thing into UCT. What are other people doing? 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] Ladders and UCT
Mark: Can you say more? Do you mean ALWAYS play such moves first if they are available, do so with some probability, or what? Peter Drake http://www.lclark.edu/~drake/ On Jun 16, 2008, at 4:09 PM, Mark Boon wrote: play ladder-capturing and ladder-escaping moves during playout ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Ladders and UCT
Without the 10% random moves, would every playout from a given leaf be identical? Peter Drake http://www.lclark.edu/~drake/ On Jun 17, 2008, at 3:14 AM, Magnus Persson wrote: Valkyria plays uniformily the highest ranked move. Ladders as a response to the last move are almost always ranked above all else. But it has a parameter that makes it play any move with 10% probability no matter what the tactical situation is on the board. I have not tested if these really is beneficial. If it is it is probably really a small change to winning rate. Magnus Quoting Carter Cheng <[EMAIL PROTECTED]>: I hope you don't mind me chiming in here. I think I asked this question quite recently on the mailing list and the reply I received from Magnus Persson (I hope I am not misquoting him) was that Valkyria adjusts the probability distribution based on a simple ladder readout which is a function which returns either success fail or unknown in order to feed this information into the playout process. --- On Mon, 6/16/08, Peter Drake <[EMAIL PROTECTED]> wrote: From: Peter Drake <[EMAIL PROTECTED]> Subject: Re: [computer-go] Ladders and UCT To: "computer-go" Date: Monday, June 16, 2008, 10:13 PM Mark: Can you say more? Do you mean ALWAYS play such moves first if they are available, do so with some probability, or what? Peter Drake http://www.lclark.edu/~drake/ On Jun 16, 2008, at 4:09 PM, Mark Boon wrote: > play ladder-capturing and ladder-escaping moves during playout___ 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 mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Congress tournament: you can send a proxy
For the tournament at the US Go Congress: Please remember that you can send someone else to run your program if you can't attend yourself. You might consider finding someone who is attending anyway and would be willing to run your program. Is there anyone attending the Congress who does NOT have a program and would be willing to stand in for someone else? (I have some research assistants who may be able to help with this.) On a related note, please consider entering even if your program is weak. You don't have to come out on top to win something, and I haven't yet heard from MoGo, CrazyStone, or any other programs known to be very strong. You might do better than you think! 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] List of contestants for US Go Congress tournament
Here's the info I have so far. Please appraise me of any errors or omissions. Program Primary Author Notes SlugGo David Doshay As the author is involved in organizing the tournament, this program will not be eligible for prize money Orego Peter Drake Same as above FirstGo Edward de Grijs Needs operator, will borrow hardware ManyFaces David Fotland Argus Sam Gross HouseBotJason House Needs operator, will borrow hardware Any others? None of the very strong UCT programs are here, so who knows who will win the $400 first prize? 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] List of contestants for US Go Congress tournament
Terry -- thanks for the offer! We'll likely take you up on it. We're looking at starting after lunch on Sunday and finishing up by dinner on Tuesday. Hopefully things will be automated enough that, if necessary, games can continue overnight. Peter Drake http://www.lclark.edu/~drake/ On Jun 23, 2008, at 10:50 AM, terry mcintyre wrote: What is the schedule for this computer tournament? If it does not conflict with the main tournament, I could operate a program for somebody. It looks like the US open games begin at 9 AM, and there's 90 minutes on each clock, so it's reasonable to expect that game would finish by noon. Terry McIntyre <[EMAIL PROTECTED]> “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.” Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] - Original Message From: Peter Drake <[EMAIL PROTECTED]> To: Computer Go Sent: Sunday, June 22, 2008 10:41:33 PM Subject: [computer-go] List of contestants for US Go Congress tournament Here's the info I have so far. Please appraise me of any errors or omissions. Program Primary Author Notes SlugGo David Doshay As the author is involved in organizing the tournament, this program will not be eligible for prize money Orego Peter Drake Same as above FirstGo Edward de Grijs Needs operator, will borrow hardware ManyFaces David Fotland Argus Sam Gross HouseBotJason House Needs operator, will borrow hardware Any others? None of the very strong UCT programs are here, so who knows who will win the $400 first prize? 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] 9x9 server
It looks like the server is running, but the standings page is not being updated: http://cgos.boardspace.net/9x9/standings.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/
[computer-go] UCB/UCT and moving targets
UCB (and hence UCT) would treat the following sequences of wins (1) and losses (0) the same: 01010101010101010101010101010101 Clearly, it would be better to favor the second sequence, because that move has done more for us lately. Because the tree is growing, the values of the moves are moving targets. Has anyone done any work dealing with this phenomenon, e.g., somehow giving more weight to more recent playouts? 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] New paper on genetic algorithms for Go
Drake, P. & Chen, Y.-P. (2008) “Coevolving Partial Strategies for the Game of Go”. In Proceedings of the 2008 International Conference on Genetic and Evolutionary Methods, CSREA Press. URL: http://webdisk.lclark.edu/drake/publications/drake-gem2008-final.pdf We've made some considerable improvements since the results reported here. It's not as strong as UCT yet, but one of our genetic player (Orego-genetic2) has a rating of 967 on the 9x9 CGOS. Expect more in the coming weeks... 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] UCB/UCT and moving targets
On Jun 26, 2008, at 1:35 AM, Magnus Persson wrote: Quoting Peter Drake <[EMAIL PROTECTED]>: UCB (and hence UCT) would treat the following sequences of wins (1) and losses (0) the same: 01010101010101010101010101010101 I have two comments. Isn't the problem here that UCT will not search the second sequence at all because it is so bad initially? Well, UCT never really discards a branch, just samples it less and less often. It would eventually go back to sequence 2 and discover that it had become good. So will there ever be a situation like this? UCT will more likely continue to sample the first and third sequenc settling for the first if their are no change again. And when it finally discovers that sequene 2 is good it will quickly choose it. The second thing is that in practice you will rarely get any clear patterns like this so how would you be able to detect any recency? I'm thinking of a situation where move A looks good when we're assuming a random response from the opponent, but once the child node starts using UCB, it is discovered that the opponent has a very good response, so now runs through A start losing. Later, runs through A start winning again because we discover a good counterresponse... One simple trick is to always replay a move in the tree if it won the last time the position was visited, and only use UCT for positions where the last played moved lost. Should'nt this work like a dream if sequence 2 truly goes to 100% winrate directly after the wirst win is scored? Probably, but we rarely get such pure victory branches. I have a number of schemes in mind, though. Has anyone tried this empirically? 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] UCB/UCT and moving targets
Can anyone point me to a thread, or at least some buzzwords? I'm having little luck googling for words like "recent" and "forget". Thanks, Peter Drake http://www.lclark.edu/~drake/ On Jun 26, 2008, at 11:40 AM, Ivan Dubois wrote: This same topic already occured on the list some time ago. I think the idea is to "forget" older results. For exemple you can compute the win rate based only on the last 500 simulations. Older information may not be up to date and will not help much because 500 simulations is enough to compute an accurate winrate. The problem is that you have to store the result of 500 simulations at each node. I think some people reported that it does indeed increase the strength of their program. - Original Message - From: "Peter Drake" <[EMAIL PROTECTED]> To: "Computer Go" Sent: Wednesday, June 25, 2008 5:48 PM Subject: [computer-go] UCB/UCT and moving targets UCB (and hence UCT) would treat the following sequences of wins (1) and losses (0) the same: 01010101010101010101010101010101 Clearly, it would be better to favor the second sequence, because that move has done more for us lately. Because the tree is growing, the values of the moves are moving targets. Has anyone done any work dealing with this phenomenon, e.g., somehow giving more weight to more recent playouts? 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/
Re: [computer-go] UCB/UCT and moving targets
Just what I was looking for -- thanks! On Jun 26, 2008, at 12:04 PM, Rémi Coulom wrote: Peter Drake wrote: Can anyone point me to a thread, or at least some buzzwords? I'm having little luck googling for words like "recent" and "forget". Thanks, Peter Drake http://www.lclark.edu/~drake/ Try "discounted UCB": http://computer-go.org/pipermail/computer-go/2007-March/009033.html http://www.lri.fr/~sebag/Slides/Venice/Kocsis.pdf Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ 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] Hardware at US Go Congress tournament
Since a few people have asked, the stats on the machines we have to loan for the tournament are given below. Peter Drake http://www.lclark.edu/~drake/ Begin forwarded message: You bet. The boxes we have are currently running Linux, but can be made to dual-boot Windows if we need that for the event. Attached please find some statistics. I *think* the two "processors" are actually two-way hyperthreading, but I'd have to check. Bart Massey # $ uname -a Linux astor.cs.pdx.edu 2.6.22-14-generic #1 SMP Tue Feb 12 07:42:25 UTC 2008 i686 GNU/Linux $ astor @ cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 15 model : 4 model name : Intel(R) Pentium(R) 4 CPU 3.20GHz stepping: 1 cpu MHz : 3200.188 cache size : 1024 KB physical id : 0 siblings: 2 core id : 0 cpu cores : 1 fdiv_bug: no hlt_bug : no f00f_bug: no coma_bug: no fpu : yes fpu_exception : yes cpuid level : 5 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx constant_tsc pni monitor ds_cpl cid xtpr bogomips: 6405.84 clflush size: 64 processor : 1 vendor_id : GenuineIntel cpu family : 15 model : 4 model name : Intel(R) Pentium(R) 4 CPU 3.20GHz stepping: 1 cpu MHz : 3200.188 cache size : 1024 KB physical id : 0 siblings: 2 core id : 0 cpu cores : 1 fdiv_bug: no hlt_bug : no f00f_bug: no coma_bug: no fpu : yes fpu_exception : yes cpuid level : 5 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx constant_tsc pni monitor ds_cpl cid xtpr bogomips: 6400.46 clflush size: 64 $ cat /proc/meminfo MemTotal: 1026684 kB MemFree: 17664 kB Buffers:232732 kB Cached: 553628 kB SwapCached:816 kB Active: 817204 kB Inactive:79160 kB HighTotal: 122044 kB HighFree: 244 kB LowTotal: 904640 kB LowFree: 17420 kB SwapTotal: 995988 kB SwapFree: 957912 kB Dirty: 4 kB Writeback: 0 kB AnonPages: 109188 kB Mapped: 30208 kB Slab:38032 kB SReclaimable:27016 kB SUnreclaim: 11016 kB PageTables: 1680 kB NFS_Unstable:0 kB Bounce: 0 kB CommitLimit: 1509328 kB Committed_AS: 233196 kB VmallocTotal: 114680 kB VmallocUsed: 6500 kB VmallocChunk: 107852 kB $ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Graph history interaction
My sense is that most programs ignore superko except for checking right before a "real" move (as opposed to a playout move) is played. The way out of the infinite loop is to set a maximum number of moves in a playout; abort the playout if you reach this threshold. On Jul 11, 2008, at 9:03 AM, Jason House wrote: I tracked down a rare hang/crash in my bot and I'm curious how others handle this. I use simple ko state as part of my hash lookup, but I don't use super ko. I can't store the whole graph history because then there would be no transpositions at all. I can't really update legal moves to exclude super ko because the super ko legality changes based on how a node is reached. In particular, a deterministic algorithm like UCT can get caught in an infinite loop. My random playouts may take a bit longer from super ko, but it gets quickly resolved. Sent from my iPhone ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ 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] Graph history interaction
Since the tree is of finite size, you will eventually get to the nondeterministic part of the playout. The moves here will probably finish the playout (one way or another) before hitting the maximum move threshold, so the playout will not be aborted but will update the tree. On Jul 11, 2008, at 9:39 AM, Jason House wrote: The way out of the infinite loop is to set a maximum number of moves in a playout; abort the playout if you reach this threshold. That trick only works when your playout is non-deterministic. Outside the search tree, things are non-deterministic and cycles are easy to break or ignore. Inside the search tree it isn't that easy. If no cached data is updated from an aborted search, UCT will walk the tree the same way it did for the last playout. When the cycle is *inside* the search tree, this means another infinite/aborted playout. The abortted playout trick would cause the bot to cycle uselessly until the game takes another path. 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] Graph history interaction
Ah, I forgot that you had a transposition table. (Orego currently does not.) I, too, will be interested to hear the solution to this problem. Peter Drake http://www.lclark.edu/~drake/ On Jul 11, 2008, at 10:49 AM, Jason House wrote: On Jul 11, 2008, at 12:43 PM, Peter Drake <[EMAIL PROTECTED]> wrote: Since the tree is of finite size, you will eventually get to the nondeterministic part of the playout. Unforunately, no. A graph cycle has finite size, in the case I debugged yesterday, it took only 4 nodes. I'm not sure how big the whole tree was, but it was at least 20 ply The moves here will probably finish the playout (one way or another) before hitting the maximum move threshold, so the playout will not be aborted but will update the tree. On Jul 11, 2008, at 9:39 AM, Jason House wrote: The way out of the infinite loop is to set a maximum number of moves in a playout; abort the playout if you reach this threshold. That trick only works when your playout is non-deterministic. Outside the search tree, things are non-deterministic and cycles are easy to break or ignore. Inside the search tree it isn't that easy. If no cached data is updated from an aborted search, UCT will walk the tree the same way it did for the last playout. When the cycle is *inside* the search tree, this means another infinite/aborted playout. The abortted playout trick would cause the bot to cycle uselessly until the game takes another path. 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/
Re: [computer-go] Graph history interaction
Another possibility would be to keep a list of nodes visited in the "tree" on each playout. In the rare event where the length of this list exceeds some max game length threshold, go back through the list looking for repetitions. Mark the first move that led to a repetition as a loss for the player that made that move. This should eventually cause the move to be rated so poorly by UCB that it will not be explored further. On Jul 11, 2008, at 11:12 AM, Sanghyeon Seo wrote: 2008/7/12 Jason House <[EMAIL PROTECTED]>: I tracked down a rare hang/crash in my bot and I'm curious how others handle this. I use simple ko state as part of my hash lookup, but I don't use super ko. I can't store the whole graph history because then there would be no transpositions at all. I can't really update legal moves to exclude super ko because the super ko legality changes based on how a node is reached. Fuego source has this interesting comment: Capture History As a heuristic fix to the Graph-History-Interaction (GHI) problem, the hash code also includes a component, that depends on the order, in which stones were captured. The idea is to eliminate hashing problems caused by the same position reached at different level in the search, or recapture is legal in one branch and illegal in another. It is not a complete solution to the GHI problem. -- Seo Sanghyeon ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ 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] Graph history interaction
Do you always check it? Would it be faster to hold off on this check until you realize that you're in a cycle? On Jul 11, 2008, at 12:06 PM, John Fan wrote: I guess you missed my message. I solved this by comparing the current node with its ancestors in the path. On each walking down the tree, I pass the list of nodes in the same path. Then I check whether the current node already appear in the path. If yes, I assign a loss there. To speed it up, I only check the current node against 6 nodes before it. It is not perfect or accurate solution for the issue, but it solves the problem at hand. On Fri, Jul 11, 2008 at 12:23 PM, John Fan <[EMAIL PROTECTED]> wrote: I had the same issue in UCT tree. What I did is to check if the current node is a ko move, then compare it with its latest 6 ancestors. If any match is found, then consider the move is a loss. So it cuts off the infinite loop. On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake <[EMAIL PROTECTED]> wrote: My sense is that most programs ignore superko except for checking right before a "real" move (as opposed to a playout move) is played. The way out of the infinite loop is to set a maximum number of moves in a playout; abort the playout if you reach this threshold. On Jul 11, 2008, at 9:03 AM, Jason House wrote: I tracked down a rare hang/crash in my bot and I'm curious how others handle this. I use simple ko state as part of my hash lookup, but I don't use super ko. I can't store the whole graph history because then there would be no transpositions at all. I can't really update legal moves to exclude super ko because the super ko legality changes based on how a node is reached. In particular, a deterministic algorithm like UCT can get caught in an infinite loop. My random playouts may take a bit longer from super ko, but it gets quickly resolved. Sent from my iPhone ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ 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/ 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] US Congress - computer go operator volunteer
I believe all of the programs that need operators (FirstGo, HouseBot, and Leela) all run on Windows. I hope someone will take Terry up on his generous offer! Peter Drake http://www.lclark.edu/~drake/ On Jul 11, 2008, at 12:30 PM, terry mcintyre wrote: I will be attending the US Congress in Portland, OR from Aug 2-10. Will be bringing a core 2 duo laptop running Linux. Intel(R) Core(TM)2 Duo CPU T7300 @ 2.00GHz MemTotal: 2034016 kB If anyone needs an operator for the Computer Go tournament, let me know. Can use my laptop or (if you arrange availability) other equipment. If your program can utilize a quadcore, I might be persuaded to shlep my HP desktop along, but it's easier for me to travel light; will be sharing a car with two others for a 14 hour drive. Unix systems administration is my day job; can deal with most of the usual setup hassles. ;) Terry McIntyre <[EMAIL PROTECTED]> “Wherever is found what is called a paternal government, there is found state education. It has been discovered that the best way to insure implicit obedience is to commence tyranny in the nursery.” Benjamin Disraeli, Speech in the House of Commons [June 15, 1874] ___ 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] Human-computer showdown
(This is from the US Go Congress to be held in Portland, Oregon.) On Thursday, August 7, at 1:00 PM, Kim MyungWan 8p will take on MoGo, the world’s strongest computer Go program. MoGo will connect remotely from France, where it will be running on a supercomputer boasting over 3,000 processor cores. The game will be broadcast on KGS. 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] Human-computer showdown
19x19. There will be a handicap. We're currently planning on five blitz games to adjust the handicap, then one "real" game. On Jul 21, 2008, at 2:07 PM, Eric Pettersen wrote: 9x9 or 19x19? On Jul 21, 2008, at 2:04 PM, Peter Drake wrote: (This is from the US Go Congress to be held in Portland, Oregon.) On Thursday, August 7, at 1:00 PM, Kim MyungWan 8p will take on MoGo, the world’s strongest computer Go program. MoGo will connect remotely from France, where it will be running on a supercomputer boasting over 3,000 processor cores. The game will be broadcast on KGS. 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/ 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] Human-computer showdown
Pacific time. We'll do this in the Computer Go room. We'll announce the usernames when the time comes. On Jul 21, 2008, at 2:28 PM, Jason House wrote: 1pm in which timezone? Which room & user name(s) will be used on KGS? Sent from my iPhone On Jul 21, 2008, at 5:04 PM, Peter Drake <[EMAIL PROTECTED]> wrote: (This is from the US Go Congress to be held in Portland, Oregon.) On Thursday, August 7, at 1:00 PM, Kim MyungWan 8p will take on MoGo, the world’s strongest computer Go program. MoGo will connect remotely from France, where it will be running on a supercomputer boasting over 3,000 processor cores. The game will be broadcast on KGS. 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/ 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] What Do You Need Most?
More hardware would help, of course. More data would be good. Particularly useful would be game records (for training) and sets of whole-board positions (9x9 and 19x19). Pattern libraries and opening libraries would be good, too, but incorporating them into existing programs may be difficult. I think the interesting algorithmic area is somehow localizing the search. My team is working on it... The community is quite good. I wonder if a 13x13 CGOS would help, because many of us are doing well at 9x9, but 19x19 is MUCH harder. Peter Drake http://www.lclark.edu/~drake/ On Jul 27, 2008, at 6:23 PM, Darren Cook wrote: I have a strong interest in seeing a 19x19 computer go program that is at least 3-dan by 2010. The recent jump in strength on the 9x9 board has given me new hope and I want to ask people here, especially the authors of strong programs, what you now need to make the next jump in strength. There seem to be four broad categories: * More hardware (CPU cycles? Memory? Faster networking? Do you just need that hardware for offline tuning, or for playing too?) * More data * New algorithms (if so, to solve exactly what? evaluation? search? other?) * More community By community I mean things like this mailing list, CGOS, open source projects, etc. By data I mean things like: game records, or board positions, marked up with correct/incorrect moves; game records generally; pattern libraries; test suites; opening libraries. 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://darrendev.blogspot.com/ (blog on php, flash, i18n, linux, ...) ___ 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] Re: IMPORTANT: US Go Congress Computer Go Tournament
There are a number of important updates regarding the Computer Go tournament next week at the US Go Congress in Portland, OR. First, timing: due to unforeseen circumstances, we won't be able to start the tournament (or get into the lab) until Monday, August 4. I plan to open the lab at 9:00 AM, allow an hour for setup, fitting SlugGo through the door, etc., then start the first round at 10:00. There MAY also be some media present to talk with all of you; the match later in the week pitting MoGo on a supercomputer vs an 8-dan professional looks like it might draw some attention. Second, participants. Here's my current list: Program Primary Author Notes SlugGo David Doshay As the author is involved in organizing the tournament, this program will not be eligible for prize money Orego Peter Drake Same as above Operated by Andrew Hubbard, will borrow hardware FirstGo Edward de Grijs Operated by Seth Pellegrino, will borrow hardware ManyFaces David Fotland Argus Sam Gross HouseBotJason House Operated by Terry McIntyre Leela Gian-Carlo Pascutto Operated by Kevin Imber, will borrow hardware (Windows) ButterBot Metascopic, Inc Operated by Jason Galbraith, will borrow hardware IT IS YOUR RESPONSIBILITY to contact your operator in advance of the tournament. Operators' email addresses are CCed above. Make sure they have your software and know how to run it! Please let me know immediately if there are any changes to the list of participating programs. Finally, I need to know the KGS USERNAME each of your programs will be using. Here's hoping for a good tournament! 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] What Do You Need Most?
Indeed! That's part of the motivation of organizing the tournament at the US Go Congress. Perhaps we (or the subset of us within a given country) could just pick an existing conference (something on machine learning or games) and all go there... Peter Drake http://www.lclark.edu/~drake/ On Jul 30, 2008, at 2:36 PM, Łukasz Lew wrote: It would be nice to have a workshop from time to time where we could share our skills. Lukasz On Mon, Jul 28, 2008 at 03:23, Darren Cook <[EMAIL PROTECTED]> wrote: I have a strong interest in seeing a 19x19 computer go program that is at least 3-dan by 2010. The recent jump in strength on the 9x9 board has given me new hope and I want to ask people here, especially the authors of strong programs, what you now need to make the next jump in strength. There seem to be four broad categories: * More hardware (CPU cycles? Memory? Faster networking? Do you just need that hardware for offline tuning, or for playing too?) * More data * New algorithms (if so, to solve exactly what? evaluation? search? other?) * More community By community I mean things like this mailing list, CGOS, open source projects, etc. By data I mean things like: game records, or board positions, marked up with correct/incorrect moves; game records generally; pattern libraries; test suites; opening libraries. 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://darrendev.blogspot.com/ (blog on php, flash, i18n, linux, ...) ___ 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] Ladders and UCT again
I know we had this conversation recently, but I just can't seem to get my head around writing a ladder reader. What, exactly, does the ladder reader do? Our approach was to read out ladders involving the last stone played. In the playout (beyond the tree), if the attacker can capture by continuing a ladder, the attacker plays that move. If the defender can escape by running, the defender plays that move. Otherwise, a random move is played. The trouble seems to be that, once the attacker plays, there's nothing more for the ladder reader to say. At this point, it's 50-50 whether the attacker or defender will play on the defender's last liberty. Thus, the ladder reader doesn't give any pressure to stop running when caught in a ladder. What am I missing? 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] Ladders and UCT again
On Jul 31, 2008, at 4:24 PM, Mark Boon wrote: On 31-jul-08, at 19:50, Peter Drake wrote: I know we had this conversation recently, but I just can't seem to get my head around writing a ladder reader. What, exactly, does the ladder reader do? Our approach was to read out ladders involving the last stone played. In the playout (beyond the tree), if the attacker can capture by continuing a ladder, the attacker plays that move. If the defender can escape by running, the defender plays that move. Otherwise, a random move is played. The trouble seems to be that, once the attacker plays, there's nothing more for the ladder reader to say. At this point, it's 50-50 whether the attacker or defender will play on the defender's last liberty. Thus, the ladder reader doesn't give any pressure to stop running when caught in a ladder. What am I missing? What you're missing (or so it seems to me) is that it's not to prevent from running a ladder that is caught. Really? My motivation has been to prevent my program from embarrassingly running in just those situations. Is there something other than a ladder reader used for this? It is to ensure to escape when you can or capture when necessary to prevent an escape. And not only the last stone played of course, it could be the neighbour of the last stone played as well. The neighbor point is useful. Of course, as Don pointed out in another message, there are always additional complexities to add -- what if one of the attacking groups is in atari, or can be put in atari? I'm more interested in the bigger issue: exactly what question is the ladder reader trying to answer? When does it suggest a move and when doesn't it? 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] Ladders and UCT again
Okay, let me see if I can sum this all up. Let <2, capture, attacker> stand for "defending chain has 2 liberties, it will be captured if the ladder is played out, and it is the attacker's turn". Use the following rules to suggest moves: <1, capture, defender> => defender plays ladder breaker, then attacker captures <1, capture, attacker> => no suggestion <1, escape, defender> => run (play out ladder), no suggestion for attacker's follow-up <1, escape, attacker> => capture <2, capture, defender> => run (to gain a 3rd liberty, escaping the ladder) <2, capture, attacker> => chase (play out ladder), no suggestion for defender's follow-up <2, escape, defender> => no suggestion <2, escape, attacker> => ladder breaker Which chains are considered? All of them with few enough liberties? If we only consider the last stone and its neighbors, moves elsewhere on the board will look disproportionately bad because they "disable" the ladder searcher. Peter Drake http://www.lclark.edu/~drake/ On Jul 31, 2008, at 5:06 PM, terry mcintyre wrote: From: Peter Drake <[EMAIL PROTECTED]> Our approach was to read out ladders involving the last stone played. In the playout (beyond the tree), if the attacker can capture by continuing a ladder, the attacker plays that move. If the defender can escape by running, the defender plays that move. Otherwise, a random move is played. A human player would not play "a random move;" the likelihood of a playing a ladder-breaker would be high. The opponent would then have to consider whether to capture the ladder or respond to the ladder-breaker in some other way. Higher-level players and those with experience programming Go can surely offer improvements. ___ 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] Ladders and UCT again
On Aug 1, 2008, at 8:08 AM, Mark Boon wrote: The neighbours of the last move come in the picture because usually it's only the last stone played that can be escaping a ladder and it's the neighbours of the last move that could have been put into atari. Nothing to do with the additional complexities Don mentioned. Let me give a specific example. Suppose that, during a playout, the tree leads us to this position, with O to play: . ...OO ..O##a... ...Ob c . . . . Having reached the frontier of the tree, we now finish the game using Monte Carlo with a ladder reader. The last stone played, to the left of a, is trapped in a ladder, but can escape if not chased. Our ladder reader therefore suggests O play at a. For the next move in the playout, if # only reads ladders from the last move played, it will see that the O stone at a is not in a ladder, so move is suggested. The playout now turns completely random, and it's a coin toss as to whether the group will escape. If we also search stones next to the last stone played, things only get slightly better. # sees that its stones are in a ladder from which they cannot escape, so it doesn't suggest b. If we tell it to play a ladder breaker in such situations, it might play c, which is fine. However, on O's next turn, c is not in a ladder, nor is any stone next to c, so no move is suggested. Specifically, O does not make the vital capture at b. It seems too expensive to search every point on the board for ladders. What to do? 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] Re: US Go Congress Computer Go Tournament
I had a look at the room where we'll be playing; it looks good. For those of you borrowing software, the tech support people would be extremely happy if you could send them your program in advance so that they can install it. If not, we'll do the best we can on Monday morning. If you have any special needs regarding libraries, etc., please let them know ASAP. The address is: [EMAIL PROTECTED] 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] CGOS server boardsize
I prefer consistent 13x13 on the third server, since I use CGOS to determine if some change to the program is an improvement. 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] Ladders and UCT again
Depending on your implementation, it may be faster to re-derive the liberty list when you need it. For example, if your playout move suggester only suggests capturing the last stone played, you don't need to do all of the work to update liberty counts for any other chains. Thanks a lot for everyone's help here. I think I have my ladder- reader working, although my program was still playing out ladders. The solution turned out to be something completely different: turn up the "exploration" coefficient in the UCT formula. If it's too low, the program commits to a particular move too early, builds up a lot of playouts through that move, and keeps playing the move even though it has read a sequence of follow-ups that lead to a bad result. Peter Drake http://www.lclark.edu/~drake/ On Aug 2, 2008, at 7:06 AM, Álvaro Begué wrote: On Sat, Aug 2, 2008 at 9:43 AM, Jason House <[EMAIL PROTECTED]> wrote: On Aug 2, 2008, at 4:31 AM, Gunnar Farnebäck <[EMAIL PROTECTED]> wrote: It's often a good idea to bias capturing moves in the playouts, regardless whether it's a ladder or not. This would result in those stones being captured in most simulations. What method do people use for finding capture moves in playouts? Pseudo liberties can miss simple stuff like open triangles and one-eyed groups. Additionally, some literature discusses captures to add group liberties. What's the preferred method to detect that?___ When we wrote dimwit, John Tromp found a fast method that I described here: http://computer-go.org/pipermail/computer-go/2007-November/ 012342.html However, my current thinking is that it's probably best to just keep a real liberty count and a list of liberties for each chain. This way you can also find atari moves, which would be very hard to do if you only keep pseudo-liberties. ___ 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] Computer tournament at US Go Congress
For your information. Peter Drake http://www.lclark.edu/~drake/ Begin forwarded message: From: Aaron Fellin <[EMAIL PROTECTED]> Date: August 2, 2008 1:04:26 PM PDT To: Barton C Massey <[EMAIL PROTECTED]>, Peter Drake <[EMAIL PROTECTED]> Cc: [EMAIL PROTECTED] Subject: Re: Go Tourney next week Reply-To: [EMAIL PROTECTED] Wow, I didn't realize this email was going to be so long when I started. That's probably a result of me attempting to err on the side of completeness wherever possible. The first section is a recap of where we stand from a technical standpoint; the second section is a mix of things that will be important on Monday morning (or before). The last part of this is a rundown of different ways to get ahold of MCECS Support (aka, TheCAT). - Aaron Technical stuff: It looks like we've got everything set up for the connection to the go server and I've tested with the one go computer program that we've received. There is a wrapper installed as /usr/bin/kgsGtp on the linux lab computers that they can use to start the program. It sounds like the people running the go bots know how to connect using a config file for this program, so all should be well on that front (if all else fails, try /usr/bin/kgsGtp -help). I was able to connect to the kgs go server with the one go computer we've got. As far as I know, it was working correctly, but I never got it to play a game against me. The program to watch the games is just a java web start link, so that will work on all our linux and windows computers. In addition, the web site has an applet version of it that will work. The last I've heard from the Wintel team is that they will have a minimally loaded windows computer available in the lab. I made sure to tell them that you will need java and java web start for the tournament, so that'll be installed on it (the things they don't install will likely be Adobe Acrobat, Office, et cetera). On the day of: There is to be no food and drink in the lab. There is a table near the door of the lab to hold food and drink. In order to keep the door from being propped open and our campus security folks getting paged, we've moved the table into the lab; our no food and drink policy is being stretched to its limit for the tournament. Users with their own hardware will need to register their hardware as laptops on our network. The url is https://intranet.cecs.pdx.edu/network/ laptops . They should log in with the guest accounts. Once the "laptops" are registered, any laptop jack in the lab (there are 5 or 6) will work within about 20 minutes. Two of those jacks are the ones next to where we decided the mac mini cluster will probably fit best. The url for laptop registration is written on the whiteboard in the lab. There are three tables set up for laptops/other hardware near the back of the room. One of them has a plugged in surge strip mounted to the underside so you won't have to climb under the table to plug hardware in. Unfortunately, under and behind the table is where the laptop jacks are, so networking cables will still require some spelunking. I'm guessing those cables will be unplugged from the wall less often than power cables, though. The last I've heard is that there will be a CAT with sufficient access to install libraries on the linux boxes and tweak the networking should anything fail on Monday morning (I make no guarantee against faulty cables in the wiring closet). I do not believe that anyone from the windows team with sufficient access will be available on site first thing Monday morning. There is a general user support person scheduled on the front desk at 8am as well; they may be able to assist with some general troubleshooting. Ways to get ahold of user support (in the middle of the night): From online, probably the most efficient way to contact us is over IRC. irc.cat.pdx.edu is our IRC server and #support is our general user support channel. If things break in the middle of the night, this is probably one of the fastest ways to get ahold of people if there happens to be any one staying up late. [EMAIL PROTECTED] will email the entire support staff. Because of the delay in email, this is probably not as ideal for urgent troubleshooting, but is not a bad way to contact us by any means. FAB 60-06 is our main front desk. I don't think we actually went there on Friday, but Bart at least should know where this is. It can be a bit of a hike from the lab, unfortunately. The desk is generally staffed from 9am to 6pm; hours are at http://www.cat.pdx.edu/fab_60-06_schedule.html . While I won't guarantee that cell phones will work near the lab, the desk phone is (503) 725-5420. The CS tutors are available just down the hall from the lab from 11am to 6pm daily; if you g
[computer-go] Location for US Go Congress computer tournament
The Linux lab is in the Fourth Avenue Building, room 81-03. Leave some time to find it; the building is rather labyrinthine. I'll be there by 8:30 AM Monday, possibly a bit earlier, so hopefully people can set up and then go play in the US Open. 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] Re: Computer tournament at US Go Congress
To anyone who's here at the Congress: The American Go Association (most likely the board thereof) is having a meeting about "Computer / Internet Development" in Smith 229 at 4:00 PM. Since decisions are made by people who happen to be in the room at the time, it might be a good idea for us to be there to advocate for computer tournament funding, rated games for computers, etc. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Kim vs MoGo match Thursday -- NEW LOCATION
(Please propagate this information widely. I will make some posters and put them up around Smith.) Thursday, August 7, 1 PM PDT, Kim MyungWan 8p will play against MoGo, the world's strongest computer Go program. MoGo will be connecting remotely, running on a European supercomputer using hundreds if not thousands of processor cores. Mr. Kim, some computer Go programmers, and a crowd of rapt observers will be in Smith 338 (next to the ballroom). I'll bring a projector to project the game on the wall. The game will also be broadcast on KGS in the Computer Go room (one of the "social" rooms). We'll have a few blitz matches to adjust the handicap, then play a "real" game with an hour per side. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] komi for 13x13 and 19x19
I would be in favor of 7.5 everywhere. We used 7.5 at the US Go Congress computer tournament and got 23/42 wins for white. Of course, every game but one ended in resignation... Peter Drake http://www.lclark.edu/~drake/ On Aug 6, 2008, at 5:57 AM, Don Dailey wrote: I'm wondering if I should have set 7.5 for 19x19.Someone posted that 6.5 for Japanese, 7.5 for Chinese.I currently have it set for 6.5 but that can easily be changed. I would rather be consistent with 7.5 unless it's clear that this is incorrect. - Don On Wed, 2008-08-06 at 18:13 +0900, Darren Cook wrote: Does it make sense to use a komi of 7.5 for 13x13 and 19x19 under CGOS rules? I see you went with 7.5 for 13x13. I was about to suggest 8.5 but changed my mind while writing this email. First evidence for 8.5 is Robert Jasiek's comments (e.g. "I have observed that 8.5 komi for 13x13 ... frequently lead to strategically demanding 0.5 games") here: http://senseis.xmp.net/?HandicapForSmallerBoardSizes Second, Little Golem has used 8.5 for a few years, and this top tournament has exactly 50-50 for black/white wins: http://www.littlegolem.net/jsp/tournament/tournament.jsp? trnid=go13.ch.10.1.1 However, the tournament after has 15 to black, 21 to white here: http://www.littlegolem.net/jsp/tournament/tournament.jsp? trnid=go13.ch.11.1.1 And the tournament before has 13 to black, 23 to white: http://www.littlegolem.net/jsp/tournament/tournament.jsp? trnid=go13.ch.9.1.1 So, it seems 8.5 komi may favour white. Darren ___ 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] Re: mogo beats pro!
Yes, MoGo gained much more from the longer time setting than Mr. Kim did. Note that Mr. Kim used very little of his time in the one-hour game. He said after the match that using more time would not have helped him. This is an interesting property of Monte Carlo Go. At the risk of overgeneralizing, it may be that digital computers have an advantage over brains in terms of fast and accurate short-term memory (dare we call it "concentration"?). A human pro has better lightning instincts (fuzzy long-term memory?), but some time for MC sampling allows the program to develop that instinct (or something analogous) over the course of the game. If we could only decide what to store (and how to store it) between games, we could get good blitz performance and superhuman long game performance. Peter Drake http://www.lclark.edu/~drake/ On Aug 7, 2008, at 10:26 PM, Dave Dyer wrote: My take-away from watching the match is that blitz performance wasn't at all representative. A human playing blitz games might do 90% as well as at a full length game, whereas mogo's performance looked like it scaled more linearly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
On Aug 8, 2008, at 7:13 AM, Robert Waite wrote: I was in the KGS room for a couple of hours before the match and a couple after. I was very surprised by the result as many were. There still is a lack of clear information about the event. For example, when Kim said that the computer plays at maybe 2 or 3 dan... does he mean professional or amateur pro? I believe he meant amateur. One person who seemed to be in the room with Kim said that he was laughing and clapping at some of the computer's moves. This was only at one moment during the second blitz game when MoGo cut off one of Kim's groups. He was definitely concentrating on his games. One person in this list, but not the AGA eJournal, mentioned that Kim used about 11 minutes time.. where the computer used around 50. This was surprising to me... Kim is reported to say that he felt having extra time would not have helped. Correct. To me... this seems a little odd. He may have used it as a tactic to give the computer less thinking time (if Mogo was indeed thinking during Kim's turn). I don't know about this; he may not have been aware that MoGo pondered. Many of the audience were surprised that MoGo was capable of resigning. 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/
