Re: [computer-go] Most common 3x3 patterns
2007/5/27, Peter Drake [EMAIL PROTECTED]: 3197 occurrences of ... w?. BB. (7 transformations. Another full triangle.) This is called Turn. http://senseis.xmp.net/?Turn This is a standard Go term, originating from qu3(Chinese), magari(Japanese), guburim(Korean). -- Seo Sanghyeon ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Efficiently selecting a point to play in a random playout
As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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] Efficiently selecting a point to play in a random playout
i'd need to write a C interface for it, then try to maintain compatibility through new releases. (AKA i'd effectively end up rewriting it). it might seem like less of a burden for me to just write my code in C++, but i guess i'm just a caveman who is stuck in his old ways and would rather reinvent the wheel than switch language horses just to save some effort. s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, May 27, 2007 2:39:55 PM Subject: Re: [computer-go] Efficiently selecting a point to play in a random playout Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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/ Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Yeah, I suffer from this, too. (There's also the fact that using someone else's code would disqualify you from the formal division of the KGS tournaments.) Here's a heroic tale of not-invented-here syndrome for your amusement: http://worsethanfailure.com/Articles/slammerSCR.aspx Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 12:55 PM, steve uurtamo wrote: i'd need to write a C interface for it, then try to maintain compatibility through new releases. (AKA i'd effectively end up rewriting it). it might seem like less of a burden for me to just write my code in C++, but i guess i'm just a caveman who is stuck in his old ways and would rather reinvent the wheel than switch language horses just to save some effort. s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, May 27, 2007 2:39:55 PM Subject: Re: [computer-go] Efficiently selecting a point to play in a random playout Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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/ __ __Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ 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] Efficiently selecting a point to play in a random playout
Here is what I do, don't know if it's best Basically you want a list of empty points, since most of them are legal. When I apply a move to the board I then do any needed legality testing. At the beginning I start with a list of ALL points on the board. When a non-empty point is encountered I put it away, placing it behind a point in the list that represents all the occupied points. To find a random move I choose an index at random among the set of untested points. If that point is occupied, it gets put away, if it's not it's the next move (and it still get's put away since it will not be occupied.)If the point is not occupied but illegal, it gets set aside until a legal move is found - then it is good again. When a capture occurs, I have found nothing much faster than just starting all over, due to my very simplistic data structure.One could take the time to restore those points but this is expensive with naive data structures. It's often not productive to play to points that have been captured - often a complete waste of time for either side. There may be some enhancements where this fact is used to advantage, but I'm not sure how to reliably test when this should and shouldn't be done. Lukasz Lew does something far more sophisticated and very fast using the concept of pseudo liberties which you might want to look into. - Don On Sun, 2007-05-27 at 13:21 -0400, Jason House wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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] Efficiently selecting a point to play in a random playout
I'm a language caveman too then. I really avoid C++ even though I learned the basics long ago. I really hate it. It's not like I'm an old dog that can't learn new tricks - I have experimented and explored many computer languages and I am versatile in many. It's one of those languages that to me feels wrong - like a big ugly hack on top of something that isn't that pretty to start with.I tolerate C because it's the best at speed. I don't have a good reason to tolerate C++. Don't want to start a language flame war though. I love object oriented but I always reach for something else when I'm compelled to go that way. Maybe it's caveman of me, but I don't associate object oriented with super high performance programming. Of course I realize that c++ can be almost as fast as C if you know what you are doing and avoid certain things - but it seems like an insane combination to me - OOP is high level, C is low level. C++ seems like a bad marriage. I'm sure you can get used to anything. If you get really familiar and comfortable with C++ you probably can live with it and even believe it to be a wonderful thing. But that's no shocker - no matter how awful a language is you will get many fanatics who seem to believe it's the most wonderful thing ever invented! - Don On Sun, 2007-05-27 at 13:02 -0700, Peter Drake wrote: Yeah, I suffer from this, too. (There's also the fact that using someone else's code would disqualify you from the formal division of the KGS tournaments.) Here's a heroic tale of not-invented-here syndrome for your amusement: http://worsethanfailure.com/Articles/slammerSCR.aspx Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 12:55 PM, steve uurtamo wrote: i'd need to write a C interface for it, then try to maintain compatibility through new releases. (AKA i'd effectively end up rewriting it). it might seem like less of a burden for me to just write my code in C++, but i guess i'm just a caveman who is stuck in his old ways and would rather reinvent the wheel than switch language horses just to save some effort. s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, May 27, 2007 2:39:55 PM Subject: Re: [computer-go] Efficiently selecting a point to play in a random playout Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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/ Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ 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] Efficiently selecting a point to play in a random playout
On Sun, 2007-05-27 at 13:21 -0400, Jason House wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ If I had it to do over again, knowing what I know now, I would not spend a lot of time optimizing random games. These optimizations don't make much difference for heavy playouts and heavy playouts are better. - Dave Hillis Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
?ukasz Lew wrote: Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? I probably have a lot of little reasons. When it first came out, I already had my own C++ based framework and didn't really worry about switching or not. Of course, now that I'm rewriting my bot, using someone else's framework would make more sense. When I look at libego, the big turn offs would be the lack of documentation, coding style (the use of #defines, global variables, hard coding to a set board size, etc...), and lack of a collaborative environment such as sourceforge (repository access, bug tracking, etc...). My rewrite is using a little known language D. Here are some items that have been developed in the housebot rewrite that I really like: * Multi-threaded core routines * Inter-process communication with delegates (function objects) instead of fixed data structures and special handlers (like the MPI uses I've seen) * Decentralized GTP command registration. I originally used the GTP from Gnu Go but didn't like how many places in the code I had to modify when adding new (debug) functions. * Variable board sizes and shapes (currently, rectangular boards). Instead of just supporting one best implementation, I want to have a flexible framework that supports the interests of many programmers. Eventually, the core will allow a variety of plug and play components/algorithms... I want to support different types of boards (such as bit boards and 3D boards), different types of chain tracking (such as the disjoint set data structure or gnu style int chain ID), and different search methods (UCT, alpha beta, PN, df-PN, etc...). I'm always recruiting people to help if that inspires anyone ;) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
I struggled with unto a lot, too. In the current version of Orego, there is no undo, just a way to copy a board relatively quickly. This falls under keep the common case fast again: you only undo once per playout, so it's faster to make a copy. (For the real board, where actual games moves are played, maintain a stack of board state copies for undoing.) Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 5:28 PM, Jason House wrote: Don Dailey wrote: Lukasz Lew does something far more sophisticated and very fast using the concept of pseudo liberties which you might want to look into. Both pseudo liberties as well as disjoint set chain tracking. Curiously enough, they're both things I independently came up with when I was designing HouseBot the first time around, but included neither in the open source version. Pseudo liberties had a very negative response on the computer go mailing list at the time, so I chose something closer to real liberty tracking. When I implementing undo's I figured the disjoint set stuff was too complex and might scare away developers on an open source project (simple, easy to read code is a big plus). I still wonder if I was the original creator of either concept... ___ 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] Efficiently selecting a point to play in a random playout
Darren Cook wrote:
Jason House also mentioned hard coding to a set board size, I think
libego can be used at least up to 19x19, just by changing the
board_size setting in board.cpp (it also supports hexagonal boards).
Or did you mean being able to make one binary for all board sizes? I
feel that that flexibility doesn't justify the performance hit.
One binary for many board sizes is pretty easy and comes at nearly zero
runtime cost... Templates could at least allow common cases such as
running on KGS to work well (19x19, 13x13, 9x9)
template int boardsize
class board{
}
or the D equivalent...
class board(int boardsize){
}
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On Sun, 2007-05-27 at 19:31 -0400, [EMAIL PROTECTED] wrote: If I had it to do over again, knowing what I know now, I would not spend a lot of time optimizing random games. These optimizations don't make much difference for heavy playouts and heavy playouts are better. - Dave Hillis Yes, I absolutely agree with this. It's probably best to save the optimizations for specific versions - when you know what you want. With a program in constant development, it's not so easy to decide at what point this makes sense. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
I remember that conversation and the negative response. But to be fair to the ones who were negative, you presented this as an evaluation feature that could be calculated quickly, not as a pure performance optimization. The negative response was in response to the suggestion that it might be used as an evaluation feature instead of true liberties. At least that is how I remember it. - Don On Sun, 2007-05-27 at 20:28 -0400, Jason House wrote: Don Dailey wrote: Lukasz Lew does something far more sophisticated and very fast using the concept of pseudo liberties which you might want to look into. Both pseudo liberties as well as disjoint set chain tracking. Curiously enough, they're both things I independently came up with when I was designing HouseBot the first time around, but included neither in the open source version. Pseudo liberties had a very negative response on the computer go mailing list at the time, so I chose something closer to real liberty tracking. When I implementing undo's I figured the disjoint set stuff was too complex and might scare away developers on an open source project (simple, easy to read code is a big plus). I still wonder if I was the original creator of either concept... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Don Dailey wrote: I remember that conversation and the negative response. But to be fair to the ones who were negative, you presented this as an evaluation feature that could be calculated quickly, not as a pure performance optimization. The negative response was in response to the suggestion that it might be used as an evaluation feature instead of true liberties. At least that is how I remember it. Oh, I definitely didn't mean to say or imply that those who gave a negative reaction were wrong. I apologize if anyone took my post that way! At the time, MC wasn't a big push in computer go, and I know I wasn't thinking about rapid random games. You're absolutely right that I was looking to use it as some kind of quick and dirty evaluation feature. Honestly, I think the feedback was helpful too. I ended up making a concept of local liberties that were slightly smarter than pseudo liberties and were much more useful for non-MC computations. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
