Re: [computer-go] a few more questions
Álvaro Begué wrote: On Tue, May 13, 2008 at 8:10 PM, Weston Markham [EMAIL PROTECTED] wrote: On Tue, May 13, 2008 at 7:08 PM, Gunnar Farnebäck [EMAIL PROTECTED] wrote: And I agree, don't even think of doing this with floating point numbers. This is a bit tangential to computer go. But you have piqued my curiosity Offhand, that sounds rather extreme to me. Perhaps I haven't really thought this through completely, but it seems as if there is a simple modification to the stated algorithm, that would ensure that it works fine with floating point numbers. Or at least well enough for any conceivable purpose: Make sure that you select each random number from a slightly larger range than prescribed by the exact totals. (For example, always round up while calculating the totals. If you do not have control over the rounding mode, just add on some small fraction of the largest weight.) Then, in the event that subtracting the weights of the points/rows/buckets never reduced the selected number to a non-positive value, just select a new random number and start over. Would this work fine, or is there some flaw in my thinking that Álvaro and Gunnar have already considered? John Tromp and I spent quite a bit of time patching the floating-point implementation and hunting down the subsequent bugs. I am not saying that making it robust is impossible, but I ended up so frustrated that I don't think I will ever try again. Integers are much better behaved and are sufficient for everything we wanted to do. I did the same, until I decided that it was utterly pointless. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
I was waiting for this one... :) Joel On Wed, May 14, 2008 at 1:57 PM, Hideki Kato [EMAIL PROTECTED] wrote: Álvaro Begué: [EMAIL PROTECTED]: Ooops! I hit sent before I finished writing the pseudo code. Sorry. int pick(Move *empties, int num_empties) { int num_candidates = num_empties; int picked; while(1) { picked = rand()%num_candidates; This code introduces few bias unless num_candidates is a power of two, though. #Assuming rand() returns [0 .. power of two). -Hideki if(!acceptable(empties[picked])) { num_candidates--; swap(empties[picked],empties[num_candidates]); } else break; } return picked; } On Tue, May 13, 2008 at 1:57 PM, Álvaro Begué [EMAIL PROTECTED] wrote: On Tue, May 13, 2008 at 1:51 PM, Mark Boon [EMAIL PROTECTED] wrote: On 13-mei-08, at 14:10, Álvaro Begué wrote: What others do is the right thing to do. Your method will introduce some biases. Could you elaborate what bias it could lead to? I also do the same as Jason. I did consider the possibility of a bias but couldn't immediately think of one. This has been explained already. After the first eye appears on the board, the first empty point after the eye has a probability of being picked that is twice the probability of any other empty point. What good does moving it to the end of the list do? Next time around it's just as likely to be picked as when left in place. Or do you only process the 'end' after the 'front' moves are all tried? You move it to the end and you reduce the number of candidates by one. The code is roughly this: int pick(Move *empties, int num_empties) { int num_candidates = num_empties; int picked; do { picked = rand()%num_candidates; num_candidates--; } while(!acceptable(empties[picked]); return picked; } Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ 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] 10k UCT bots
On Tue, May 13, 2008 at 11:57 PM, Hideki Kato [EMAIL PROTECTED] wrote: Álvaro Begué: [EMAIL PROTECTED]: Ooops! I hit sent before I finished writing the pseudo code. Sorry. int pick(Move *empties, int num_empties) { int num_candidates = num_empties; int picked; while(1) { picked = rand()%num_candidates; This code introduces few bias unless num_candidates is a power of two, though. #Assuming rand() returns [0 .. power of two). Oh, please. I should probably just take that as a provocation and ignore it, but I am weak. :) The pseudo-code I posted was meant to illustrate the process by which you move an element to the end and then exclude it from the lottery. rand()%num_candidates is just a quick way of telling the reader pick a random integer in [0,num_candidates). Besides, some people didn't care if a point had probability that was twice as large as the rest. In my system, RAND_MAX is 2147483647, which means that in the worst case, some points will have a probability that is a factor of 5948709/5948708=1.0016810372941485 larger than the rest. Even I can live with that. Preemptive argument: Now someone will point out that the last few bits of rand() may not be very random in some common implementations, so in the case where num_candidates is a power of two I may have some biases. Please, reread two paragraphs above, or substitute rand() with the Mersenne twister. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
Don Dailey wrote: [EMAIL PROTECTED] wrote: For those currently coding this up, I think the most important thing about this playout algorithm is that it is *temporary*. You will almost certainly be?replacing it with something different and better just a little bit down the road. So you probably don't want to worry about hair-splitting tweaks except as an academic exercise. Yes, I agree. Also my hair brained scheme of pre-generated tables of list traversal orderings was just an academic exercise as you say. But the problem is that when you do heavy playouts you have the same problem except that the probabilities of the legal moves are no longer equal. Unless, of course, the board system keeps a list of legal moves, not just empty points and own eyes in playout mode have zero score which is the same as if they were illegal moves. Am I the only one doing this? I don't know if the impact is measurable in strength or not. But as the game advances, the own eyes are found in the root position. When that happens, the bias applies to the same move in all the playouts. In this case the program is favoring systematically the exploration of a move for no reason at all and it is always the same move. Since the number of simulations is limited, that pays less attention to other moves. I don't know if it is bad, but at least it is ugly. ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
Hi! Can you tell me some algorithm to compute the score ? (Both players pass, and who is the winner...) Thanks, Norbert ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
This probably explains it better than I could: http://senseis.xmp.net/?TrompTaylorRules - Don Norbert Gábor Papp wrote: Hi! Can you tell me some algorithm to compute the score ? (Both players pass, and who is the winner...) Thanks, Norbert ___ 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] 10k UCT bots
That's a function of how smart your bot is. If you play until you only have eye-filling moves, you can safely assume all of your opponent's stones are alive, all your groups with two eyes are alive, and everything else is dead. Note the asymetry - your opponent may use a different strategy. If you use random playouts, you could compute the probability of specific points being owned by each player, and use that for both passing and marking dead stones. There are many other variants that use life and death modules, but I'll assume you don't have them yet Sent from my iPhone On May 14, 2008, at 9:10 AM, Norbert Gábor Papp [EMAIL PROTECTED] m wrote: Thanks! How can I identify dead stones? I haven't seen algorithm for this, and it is a very important part of a go program 2008/5/14, Don Dailey [EMAIL PROTECTED]: This probably explains it better than I could: http://senseis.xmp.net/?TrompTaylorRules - Don Norbert Gábor Papp wrote: Hi! Can you tell me some algorithm to compute the score ? (Both players pass, and who is the winner...) Thanks, Norbert --- --- -- ___ 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: [computer-go] 10k UCT bots
Thanks! How can I identify dead stones? I haven't seen algorithm for this, and it is a very important part of a go program 2008/5/14, Don Dailey [EMAIL PROTECTED]: This probably explains it better than I could: http://senseis.xmp.net/?TrompTaylorRules - Don Norbert Gábor Papp wrote: Hi! Can you tell me some algorithm to compute the score ? (Both players pass, and who is the winner...) Thanks, Norbert ___ 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] 10k UCT bots
Thanks for your fast reply,but sorry, I don't really understand this... The situation - both player pass, end of the game, I need the score. I want to remove dead-stones which means : if (IsGameEnded) { for (int i=0, int ,j=0; itable.sizeX,ytable.sizeZ;i++,j++){ if dead(i,j) { table.remove(i,j); } } countterritories(); . . . } I'm interested in the function dead(), which is true when a stone is dead after both player pass,and the game is ended. 2008/5/14 Jason House [EMAIL PROTECTED]: That's a function of how smart your bot is. If you play until you only have eye-filling moves, you can safely assume all of your opponent's stones are alive, all your groups with two eyes are alive, and everything else is dead. Note the asymetry - your opponent may use a different strategy. If you use random playouts, you could compute the probability of specific points being owned by each player, and use that for both passing and marking dead stones. There are many other variants that use life and death modules, but I'll assume you don't have them yet Sent from my iPhone On May 14, 2008, at 9:10 AM, Norbert Gábor Papp [EMAIL PROTECTED] wrote: Thanks! How can I identify dead stones? I haven't seen algorithm for this, and it is a very important part of a go program 2008/5/14, Don Dailey [EMAIL PROTECTED]: This probably explains it better than I could: http://senseis.xmp.net/?TrompTaylorRules - Don Norbert Gábor Papp wrote: Hi! Can you tell me some algorithm to compute the score ? (Both players pass, and who is the winner...) Thanks, Norbert ___ 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: [computer-go] 10k UCT bots
On Wed, May 14, 2008 at 03:47:55PM +0200, Norbert Gábor Papp wrote: I want to remove dead-stones which means : [...] I'm interested in the function dead(), which is true when a stone is dead after both player pass,and the game is ended. The simple answer is that there is no such function! Most Monte-Carlo programs play the game out to the bitter end, when they can assume that all stones on board are alive, and all territory is segmented into one-point eyes. Then it is trivial to see who owns what. The alternative is to collect the stones into groups, and check which groups have (or can make) two eyes. This gets quite complex. Even humans make the occasional mistake in evaluating the position after both have passed, especially beginners. Some say that the game should never reach the point of counting, since at some point the loosing part will see that he can not win, and will resign on the spot. I think it will be a long time before programs can do that with confidence... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
On Wed, May 14, 2008 at 10:12 AM, Heikki Levanto [EMAIL PROTECTED] wrote: On Wed, May 14, 2008 at 03:47:55PM +0200, Norbert Gábor Papp wrote: I want to remove dead-stones which means : [...] I'm interested in the function dead(), which is true when a stone is dead after both player pass,and the game is ended. The simple answer is that there is no such function! In Tromp/Taylor rules, it's really easy to implement that function: All stones are alive. If you are playing and you think some of the opponent's stones are dead, don't pass; capture them instead. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
How do LD modules generally function? Is this discussed in the literature somewhere? The only open source LD module I am aware of is the one in GNU-go and I am not certain how good or bad it is since my own playing strength isn't that good. I have found some papers on this topic but most do not go into much detail on how they are evaluating LD and most just discuss performance issues and general algorithmic approaches (like proof-number-search). Regards, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] a few more questions
Thanks for the help with this. I suspect I will go directly for a heavy playout implementation and avoid writing some of the trickier the light playout code so I probably will be implementing this soon. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
I didn't against you, Álvaro, rather I just made a caution for programmers who will use your pseudo code as is. :) First, I prefer SFMT (SIMD-oriented Fast Mersenne Twister) rather than integer pseudo random number generators in practice where the quality of play-out is important. Modern processors execute floating operations as fast as interger ones and picked = mt_rand() * (double) num_candidates; is the simplest and safe. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html #Converting int to double is, in fact, not so fast that using double num_candidate through out the code may be faster. When using integer pseudo random number generators and keeping exact uniform distribution, following code can be used (slower twice). This discards extra random numbers that bias the distribution. #As Álvaro wrote, if n RAND_MAX the bias is very small and may be ignored. unsigned long exactly_uniform_random(unsigned long n) { unsigned long m, r; if (n == 0) return 0; m = RAND_MAX % n; do { r = rand(); } while (r = m) ; return r % n; } In addition, xor_shift is better than builtin rand() and faster and much smaller than MT. #Hiroshi, the author of Aya, uses this. http://en.wikipedia.org/wiki/Xorshift http://www.jstatsoft.org/v08/i14/paper unsigned long xorshiftrand(void) { static unsigned long x=123456789, y=362436069, z=521288629, w=88675123; unsigned long t; t = x ^ (x 11); x = y; y = z; z = w; return w = (w ^ (w 19)) ^ (t ^ (t 8)); } -Hideki Álvaro Begué: [EMAIL PROTECTED]: On Tue, May 13, 2008 at 11:57 PM, Hideki Kato [EMAIL PROTECTED] wrote: Álvaro Begué: [EMAIL PROTECTED]: Ooops! I hit sent before I finished writing the pseudo code. Sorry. int pick(Move *empties, int num_empties) { int num_candidates = num_empties; int picked; while(1) { picked = rand()%num_candidates; This code introduces few bias unless num_candidates is a power of two, though. #Assuming rand() returns [0 .. power of two). Oh, please. I should probably just take that as a provocation and ignore it, but I am weak. :) The pseudo-code I posted was meant to illustrate the process by which you move an element to the end and then exclude it from the lottery. rand()%num_candidates is just a quick way of telling the reader pick a random integer in [0,num_candidates). Besides, some people didn't care if a point had probability that was twice as large as the rest. In my system, RAND_MAX is 2147483647, which means that in the worst case, some points will have a probability that is a factor of 5948709/5948708=1.0016810372941485 larger than the rest. Even I can live with that. Preemptive argument: Now someone will point out that the last few bits of rand() may not be very random in some common implementations, so in the case where num_candidates is a power of two I may have some biases. Please, reread two paragraphs above, or substitute rand() with the Mersenne twister. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
Norbert Gábor Papp wrote: Thanks for your fast reply,but sorry, I don't really understand this... The situation - both player pass, end of the game, I need the score. I want to remove dead-stones which means : There is no known perfect algorithm for doing this in every case and it's a function of how good your program is. So if you figure out how to do it, please let us know. Typically, some kind of local search is done and the details of how to do that vary from program to program. Some do it better than others.It's not trivial.Search the web, there are papers and articles about it. If you use tromp/taylor scoring you don't worry about it. After 2 passes EVERY stone is considered alive. If there are dead stones then the opponent should not have passed. If you are asking because you want to implement monte carlo, you just play until there are no legal eye filling moves, then you pass. Then you score the board as is with no consideration of dead stones. It's very simple.Sometimes one side has no moves that fit this criteria but the other side does, so you just play until both players run out of non-eye filling moves, which gives 2 consecutive passes. A reasonable but slow algorithm for identifying dead stones is to play a few hundred random games (without filling eyes) and if existing stones rarely or never survive they are dead with a high probability. This covers most of the simple and visually intuitive cases. - Don if (IsGameEnded) { for (int i=0, int ,j=0; itable.sizeX,ytable.sizeZ;i++,j++){ if dead(i,j) { table.remove(i,j); } } countterritories(); . . . } I'm interested in the function dead(), which is true when a stone is dead after both player pass,and the game is ended. 2008/5/14 Jason House [EMAIL PROTECTED]: That's a function of how smart your bot is. If you play until you only have eye-filling moves, you can safely assume all of your opponent's stones are alive, all your groups with two eyes are alive, and everything else is dead. Note the asymetry - your opponent may use a different strategy. If you use random playouts, you could compute the probability of specific points being owned by each player, and use that for both passing and marking dead stones. There are many other variants that use life and death modules, but I'll assume you don't have them yet Sent from my iPhone On May 14, 2008, at 9:10 AM, Norbert Gábor Papp [EMAIL PROTECTED] wrote: Thanks! How can I identify dead stones? I haven't seen algorithm for this, and it is a very important part of a go program 2008/5/14, Don Dailey [EMAIL PROTECTED]: This probably explains it better than I could: http://senseis.xmp.net/?TrompTaylorRules - Don Norbert Gábor Papp wrote: Hi! Can you tell me some algorithm to compute the score ? (Both players pass, and who is the winner...) Thanks, Norbert ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
-Original Message- From: Jacques Basaldúa [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Wed, 14 May 2008 6:38 am Subject: Re: [computer-go] 10k UCT bots Don Dailey wrote: [EMAIL PROTECTED] wrote: For those currently coding this up, I think the most important thing about this playout algorithm is that it is *temporary*. You will almost certainly be replacing it with something different and better just a little bit down the road. So you probably don't want to worry about hair-splitting tweaks except as an academic exercise. Yes, I agree. Also my hair brained scheme of pre-generated tables of list traversal orderings was just an academic exercise as you say. But the problem is that when you do heavy playouts you have the same problem except that the probabilities of the legal moves are no longer equal. The problem doesn't go away but the trade-offs change considerably. This is an interesting and relevant discussion, but if I were trying to code up light MC playouts for the first time, right now, I would be feeling that this dead-simple algorithm was actually very difficult and confusing. For someone in that position (and only them), my advice is 1. Implement light playouts first. It's simple; you will find many bugs that way; it's standardized enough that other people will understand what you're talking about; it's a fast way to get a basic bot; it will be a very handy thing to have as a baseline when you test other things. 2. Get it working the standard way before improving it. It's your baseline that you'll be testing improvements against. 3. Make it fast but don't spend excessive effort optimizing. Better is the enemy of good enough. - Dave Hillis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
The 10k refers to ten thousand playouts, not rank, and yes it's 9x9. As for open source UCT, off the top of my head there's libego (C++) and Orego (Java). -Jeff On Wed, 2008-05-14 at 12:14 -0700, Carter Cheng wrote: I assume this implies that there arent any open-source basic-UCT bots which utilize the basic eye rule and a simple permute and retry scheme as described by many ppl on the group? When we speak of these sorts of bots playing at about 10kyu I assume what is meant is 10kyu at 9x9 not 19x19. --- On Wed, 5/14/08, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: From: [EMAIL PROTECTED] [EMAIL PROTECTED] Subject: Re: [computer-go] 10k UCT bots To: computer-go@computer-go.org Date: Wednesday, May 14, 2008, 10:44 AM -Original Message- From: Jacques Basaldúa [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Wed, 14 May 2008 6:38 am Subject: Re: [computer-go] 10k UCT bots Don Dailey wrote: [EMAIL PROTECTED] wrote: For those currently coding this up, I think the most important thing about this playout algorithm is that it is *temporary*. You will almost certainly be replacing it with something different and better just a little bit down the road. So you probably don't want to worry about hair-splitting tweaks except as an academic exercise. Yes, I agree. Also my hair brained scheme of pre-generated tables of list traversal orderings was just an academic exercise as you say. But the problem is that when you do heavy playouts you have the same problem except that the probabilities of the legal moves are no longer equal. The problem doesn't go away but the trade-offs change considerably. This is an interesting and relevant discussion, but if I were trying to code up light MC playouts for the first time, right now, I would be feeling that this dead-simple algorithm was actually very difficult and confusing. For someone in that position (and only them), my advice is 1. Implement light playouts first. It's simple; you will find many bugs that way; it's standardized enough that other people will understand what you're talking about; it's a fast way to get a basic bot; it will be a very handy thing to have as a baseline when you test other things. 2. Get it working the standard way before improving it. It's your baseline that you'll be testing improvements against. 3. Make it fast but don't spend excessive effort optimizing. Better is the enemy of good enough. - Dave Hillis___ 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] 10k UCT bots
On May 14, 2008, at 3:39 PM, Jeff Nowakowski [EMAIL PROTECTED] wrote: The 10k refers to ten thousand playouts, not rank, and yes it's 9x9. As for open source UCT, off the top of my head there's libego (C++) and Orego (Java). HouseBot is open source too (D). I really should add the random resampling move selector as an option to my bot. It's really easy to implement, I've even done it before... -Jeff On Wed, 2008-05-14 at 12:14 -0700, Carter Cheng wrote: I assume this implies that there arent any open-source basic-UCT bots which utilize the basic eye rule and a simple permute and retry scheme as described by many ppl on the group? When we speak of these sorts of bots playing at about 10kyu I assume what is meant is 10kyu at 9x9 not 19x19. --- On Wed, 5/14/08, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: From: [EMAIL PROTECTED] [EMAIL PROTECTED] Subject: Re: [computer-go] 10k UCT bots To: computer-go@computer-go.org Date: Wednesday, May 14, 2008, 10:44 AM -Original Message- From: Jacques Basaldúa [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Wed, 14 May 2008 6:38 am Subject: Re: [computer-go] 10k UCT bots Don Dailey wrote: [EMAIL PROTECTED] wrote: For those currently coding this up, I think the most important thing about this playout algorithm is that it is *temporary*. You will almost certainly be replacing it with something different and better just a little bit down the road. So you probably don't want to worry about hair-splitting tweaks except as an academic exercise. Yes, I agree. Also my hair brained scheme of pre-generated tables of list traversal orderings was just an academic exercise as you say. But the problem is that when you do heavy playouts you have the same problem except that the probabilities of the legal moves are no longer equal. The problem doesn't go away but the trade-offs change considerably. This is an interesting and relevant discussion, but if I were trying to code up light MC playouts for the first time, right now, I would be feeling that this dead-simple algorithm was actually very difficult and confusing. For someone in that position (and only them), my advice is 1. Implement light playouts first. It's simple; you will find many bugs that way; it's standardized enough that other people will understand what you're talking about; it's a fast way to get a basic bot; it will be a very handy thing to have as a baseline when you test other things. 2. Get it working the standard way before improving it. It's your baseline that you'll be testing improvements against. 3. Make it fast but don't spend excessive effort optimizing. Better is the enemy of good enough. - Dave Hillis___ 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/