Re: [computer-go] MC Go Effectiveness
Unknown wrote: BTW: once you choose the /8 gain by implementing canonicalization, you'll probably want to implement /2 color-swaps, too. (but this will only be profitable for libraries, not for 'history' such as in Don's case.) The /2 with color-swaps would work fine with librarys that don't store the whole gamestate, but I doubt it's worth implementing it in fuseki-librarys: Since there are usually no or very few captures during the fuseki, the player whos turn it is is determined by the gamestate itsself: Black if both colors have the same number of stones on the board, white if it differs. This means that color reflected positions can only occur if there was a capture or if you don't rely on the whole gamestate (eg. pattern-librarys, fuseki-librarys that allow ? fields that are undetermined). eph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Fri, 2007-02-09 at 13:19 +0100, Ephrim Khong wrote: The /2 with color-swaps would work fine with librarys that don't store the whole gamestate, but I doubt it's worth implementing it in fuseki-librarys: Since there are usually no or very few captures during the fuseki, the player whos turn it is is determined by the gamestate itsself: Black if both colors have the same number of stones on the board, white if it differs. This means that color reflected positions can only occur if there was a capture or if you don't rely on the whole gamestate (eg. pattern-librarys, fuseki-librarys that allow ? fields that are undetermined). Or if there is a pass. You can throw my program out of book by passing on one of the first moves :-) eph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Quoting Don Dailey [EMAIL PROTECTED]: Doing 8 searches is time-consuming, but I really prefer a book that has a LOT of variety. This is also one reason I now hand edit my book. Every time I correct a bad move there are often several ways of playing that I cannot tell which is better or worse and then I add all of them, and often moves that Valkyria would never consider. The idea is that humans on KGS will find Valkyria less predictable and other programs will have a harder time adapting to the book of Valkyria. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Magnus Persson wrote: This is not a problem for scalability for MC/UCT. It just means that a program .. You are right. I didn't mean it is not scalable, of course it is. What I mean is complexity is not, as one could expect, about ~boardsize^4. (The square of legal moves times the square of simulation length.) But even more due to the increase in variance. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:55 -0500, Don Dailey wrote: The children of one parent almost certainly will have different 64 bit keys than the children of the other parent. Not if the parents collide. (apart from symmetry/canonical considerations): if H(A)==H(B), then after applying move 'm' -- H(A) ^ some_constant == H(B) ^ some_constant So if you use Zobrist[move] as a some_constant value (which I understand you do), then if both parent moves A,B have a successor move (coordinate+color) in common, the resulting hashes for the successors will also collide. I don't see how you can conclude that I'm not getting much extra safety. By the way, I use zobrist hashing with XOR to generate these keys and do all the rotations - choosing the smallest key of the 8 possible tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... hash to this same key but the positions are symetrically equivalent. You mean: _after the canonisation_ they hash to the same key. You could of course look at it backwards, what are the odds that 2 child keys will match? If you can find 2 that do match, what are For two children of the same parent, this is (given an adequate Zobrist table) impossible. After canonisation, this is unclear (but can be guaranteed by careful construction of the Zobrist tables). the odds that their parents will also have a matching key? I think this is very unlikely. I think this is just as likely as the other way around, since the ^ is its own inverse function. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
We had this same problem and wasted a huge amount of time and energy on trying to determine the right canonical key. I felt both proud and stupid when I realized: it really does not make any difference which is the canonical key, so we just declare the first one that we find to be the canonical. The rest are the transformed versions. Cheers, David On 8, Feb 2007, at 3:18 PM, Unknown wrote: Don wrote: - choosing the smallest key of the 8 possible tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... It's not quite as good as using 64 bits free and clear because there is compression towards the lower bits. i must be missing something here -- the whole point of canonicalization is that you want to be able to recognize a 'book line' when it appears, even if you have to rotate and/or reflect your board in order to match the book line, right? you save 8x the space by only stashing one copy of the book line, and by using some canonical version of the hash key and doing 8 transforms on every board position when the game move is less than the longest known line length, or somesuch. if you're only storing a few hundred lines, or a few thousand, why not store all 8 copies? then it's just a lookup with no extra transforms. s. Need a quick answer? Get one in minutes from people who know. Ask your question on www.Answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:58 -0800, steve uurtamo wrote: tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... It's not quite as good as using 64 bits free and clear because there is compression towards the lower bits. i must be missing something here -- the whole point of canonicalization is that you want to be able to recognize a 'book line' when it appears, even if you have to rotate and/or reflect your board in order to match the book line, right? you save 8x the space by only stashing one copy of the book line, and by using some canonical version of the hash key and doing 8 transforms on every board position when the game move is less than the longest known line length, or somesuch. Yes. But Don's confusion was independent of the canonicalization, though it was probably caused by it. if you're only storing a few hundred lines, or a few thousand, why not store all 8 copies? then it's just a lookup with no extra transforms. Sure. It is just an engineering decision: do you want to waste the RAM-space, or only the CPU-time. For a few hundred records, optimising for space is probably not worth the effort. For a larger fuseki / joseki /pattern book, it probably is. CPU is cheaper than RAM, and a cache miss is worth tens of instructions. It depends. (though travel light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) BTW: once you choose the /8 gain by implementing canonicalization, you'll probably want to implement /2 color-swaps, too. (but this will only be profitable for libraries, not for 'history' such as in Don's case.) HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] MC Go Effectiveness
light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) More like 10 bits per move to store the joseki DAG, moves, pointers, and good/bad/trick flags. I would never do anything like that now, but back then the entire go program including joseki library had to fit in about 300 KB of memory (DOS) on PCs that typically only had 512 KB to 1 MB total memory. The library fit about 50K positions in about 60 KB. David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:36 -0800, David Doshay wrote: We had this same problem and wasted a huge amount of time and energy on trying to determine the right canonical key. I felt both proud and stupid when I realized: it really does not make any difference which is the canonical key, so we just declare the first one that we find to be the canonical. The rest are the transformed versions. Yes, that would work here perfectly. You just search all 8 until you find it or you don't. Cheers, David On 8, Feb 2007, at 3:18 PM, Unknown wrote: Don wrote: - choosing the smallest key of the 8 possible tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... ___ 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] MC Go Effectiveness
It depends. (though travel light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) this reminds me of an old-school optimized piece of scrabble-playing code. there was a routine that would take an ascii list of words and create a DAG out of them, as a ready-made object file, with headers and everything. the makefile linked the playing routine against it, creating a ready-made array that existed at runtime. http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt truly an awesome piece of software. it requires some minor modification to work on a modern machine, but it's well worth the effort. s. Food fight? Enjoy some healthy debate in the Yahoo! Answers Food Drink QA. http://answers.yahoo.com/dir/?link=listsid=396545367 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:58 -0800, steve uurtamo wrote: tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... It's not quite as good as using 64 bits free and clear because there is compression towards the lower bits. i must be missing something here -- the whole point of canonicalization is that you want to be able to recognize a 'book line' when it appears, even if you have to rotate and/or reflect your board in order to match the book line, right? you save 8x the space by only stashing one copy of the book line, and by using some canonical version of the hash key and doing 8 transforms on every board position when the game move is less than the longest known line length, or somesuch. if you're only storing a few hundred lines, or a few thousand, why not store all 8 copies? then it's just a lookup with no extra transforms. Well then my collision rate would go up signficantly. I don't think it's a big issue with 64 bits but there is no performance issues with lookup speed and the routine to do the tranforms has to be there no matter what - it's now isolated to one routine. And why waste the memory if there is no performance issues? I current keep the book sorted in memory and I would prefer to keep it reasonably small in the case I may someday have tens of thousands of moves. Of course by then I probably would have chosen a different storage scheme.This discussion has generated enough ideas that I may consider some changes. - Don s. Need a quick answer? Get one in minutes from people who know. Ask your question on www.Answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 18:43 -0800, steve uurtamo wrote: It depends. (though travel light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) this reminds me of an old-school optimized piece of scrabble-playing code. there was a routine that would take an ascii list of words and create a DAG out of them, as a ready-made object file, with headers and everything. the makefile linked the playing routine against it, creating a ready-made array that existed at runtime. http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt truly an awesome piece of software. it requires some minor modification to work on a modern machine, but it's well worth the effort. I wrote a scrabble program demo in perl with Tk because someone told me it would be too slow to be practical (several years ago.) Even then it found a good move within a second or two. The way I stored the dictionary was interesting, but I can't quite remember the details. I think each word was stored several times in the dictionary, a hash of each starting prefix. a,ap,app,appl,apple something like that. I was fun and it was pretty but it wasn't good, it basically maximized it's choices which isn't a good strategy against good players. - Don s. Food fight? Enjoy some healthy debate in the Yahoo! Answers Food Drink QA. http://answers.yahoo.com/dir/?link=listsid=396545367 ___ 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] MC Go Effectiveness
On 8, Feb 2007, at 6:42 PM, Don Dailey wrote: On Thu, 2007-02-08 at 15:36 -0800, David Doshay wrote: We had this same problem and wasted a huge amount of time and energy on trying to determine the right canonical key. I felt both proud and stupid when I realized: it really does not make any difference which is the canonical key, so we just declare the first one that we find to be the canonical. The rest are the transformed versions. Yes, that would work here perfectly. You just search all 8 until you find it or you don't. No, we opted to store all 8 and have every hash jump to its canonical hash for the followup. You either get a hash hit with whatever you calculate off of the board or it is the first time you have seen it. After you have the followup then you transform that move back. We chose this method because we do all of our book storage while NOT in a game, but offline at another time. I also took this path because I feel that RAM is free. Cheers, David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Matt Gokey wrote: But what are some of the reasons MC is not even better? 1-Since MC engines don't deal with tactics directly, they're not likely going to play tactical sequences well for low liberty strings, securing eye space, cutting and connecting, ko fights, or ladders, etc. 2-Also because most of the play-outs are usually nonsense, they may have trouble dealing with meaningful nuances because the positions that will lead to these distinctions just don't arise with enough statistical frequency in the play-outs to affect the result. Yet when very selective moves are used in the play-outs, too many possibilities can be missed. 3-Finally, with 19x19 anyway, the size of the board and game tree probably limits the practical effectiveness of the sampling and move ordering. I don't try to address this last point any further in this message. Very good analysis and I would like to contribute a 4th reason: As Luke Gustafson pointed out, we have to contemplate the simulation as a _stochastic process_. We want to determine the conditional probability of a win given a particular move is made. And that depends on the _length of the simulation_. Dramatically! This is a reason against scalability of global search MC/UCT. If the simulation is 500 moves long (Chinese rules with recaptures, etc.) the observed variance at an early move blurs out everything. Just a simple stochastic process: Count a dollar each time you correctly predict a p=1/2 coin thrown n=500 times. The expected average is (obviously) 250, but the expected variance of that measure is n·p·(1-p) = 125 proportional to n. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Jacques Basaldúa wrote: Very good analysis and I would like to contribute a 4th reason: As Luke Gustafson pointed out, we have to contemplate the simulation as a _stochastic process_. We want to determine the conditional probability of a win given a particular move is made. And that depends on the _length of the simulation_. Dramatically! This is a reason against scalability of global search MC/UCT. If the simulation is 500 moves long (Chinese rules with recaptures, etc.) the observed variance at an early move blurs out everything. Just a simple stochastic process: Count a dollar each time you correctly predict a p=1/2 coin thrown n=500 times. The expected average is (obviously) 250, but the expected variance of that measure is n·p·(1-p) = 125 proportional to n. Good point. This leads to another thought that I have been wondering about. That is I question whether using more time to search more simulations in the opening is the best approach. For the opening, selecting reasonable robust moves that tend to lead to more favorable options is probably a good objective. The lengths of the simulation are perhaps too long to expect anything better. Later towards the pre-middle to middle game it is very critical to play such that the positions tactical potential is exploited such to secure connections and eye space, etc. It would seem to me that focusing the highest concentration of time and number of simulations during this part of the game might be most advantageous. It would be interesting for someone with a decent MC player to do an experiment like this with one version concentrating highest number of simulations in the opening and one concentrating in the middle game, but otherwise equal and see which version wins more often. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Two qick comments: Quoting Matt Gokey [EMAIL PROTECTED]: Jacques Basaldúa wrote: Very good analysis and I would like to contribute a 4th reason: against scalability of global search MC/UCT. If the simulation is 500 moves long (Chinese rules with recaptures, etc.) the observed variance at an early move blurs out everything. This is not a problem for scalability for MC/UCT. It just means that a program that is 5 kyu with 10 minutes on 9x9 might be 35 kyu with 10 minutes on 19x19. Yet for both 9x9 and 19x19 it holds that a bugfree implementation of MC/UCT will assymptotically reach perfect play when thinking time goes towards infinity. True is that going from 9x9 to 19x19 is frustrating. But this is because 19x19 is more complex than 9x9. An MC/UCT program is still very much better than random play because random plays need more than 100 free handicap stones to have a chance on 19x19. Good point. This leads to another thought that I have been wondering about. That is I question whether using more time to search more simulations in the opening is the best approach. For the opening, selecting reasonable robust moves that tend to lead to more favorable options is probably a good objective. The lengths of the simulation are perhaps too long to expect anything better. Later towards the pre-middle to middle game it is very critical to play such that the positions tactical potential is exploited such to secure connections and eye space, etc. It would seem to me that focusing the highest concentration of time and number of simulations during this part of the game might be most advantageous. It would be interesting for someone with a decent MC player to do an experiment like this with one version concentrating highest number of simulations in the opening and one concentrating in the middle game, but otherwise equal and see which version wins more often. My experience with Valkyria is that most time must be allocated towards early moves. If you make a mistake on 9x9 it is very hard to come back. MC/UCT programs such as MoGo are very good at defending a won position. Therefore it is important to get a won position as early as possible. The longer it thinks the better it plays. In the opening it always critical to find the best move - but later on games are often either won or lost so saving time for those positions are not so important. Valkyria saves time in the opening by using an opening library, but as soon as it leaves the library it spends a lot of time on the first move. Moves it spends a lot of time on is also stored in the library. And later on I might correct moves that was played in lost hand myself. I am actually rarely satisfied with the opening moves of Valkyria. It needs more time for those moves... -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Magnus Persson wrote: Quoting Matt Gokey [EMAIL PROTECTED]: (snip) Good point. This leads to another thought that I have been wondering about. That is I question whether using more time to search more simulations in the opening is the best approach. For the opening, selecting reasonable robust moves that tend to lead to more favorable options is probably a good objective. The lengths of the simulation are perhaps too long to expect anything better. Later towards the pre-middle to middle game it is very critical to play such that the positions tactical potential is exploited such to secure connections and eye space, etc. It would seem to me that focusing the highest concentration of time and number of simulations during this part of the game might be most advantageous. It would be interesting for someone with a decent MC player to do an experiment like this with one version concentrating highest number of simulations in the opening and one concentrating in the middle game, but otherwise equal and see which version wins more often. My experience with Valkyria is that most time must be allocated towards early moves. If you make a mistake on 9x9 it is very hard to come back. MC/UCT programs such as MoGo are very good at defending a won position. Therefore it is important to get a won position as early as possible. The longer it thinks the better it plays. In the opening it always critical to find the best move - but later on games are often either won or lost so saving time for those positions are not so important. I agree with this last statement for the early end-game / end-game phase. For the pre-middle to middle I'm not sure. This is the critical part of the game where you need to solidify the winning positions. As long as reasonable opening moves that provide robust options are made and it can play into the middle game stronger than the opponent, winning positions should result. I'm not saying not to spend time up front, just less than when in the middle. On 9x9, the stage where this becomes tactically critical is probably much earlier than on 19x19. Even with 9x9 I predict an MC/UCT program that spent X simulations per move for the first 8 moves, and 2X for the next 8 would tend to beat the same player doing the reverse, where X is some reasonably large number of simulations needed to open decently. I could be wrong, but it would be an interesting experiment anyway. However IMO 9x9 is too small to see the real complications come out. Valkyria saves time in the opening by using an opening library, but as soon as it leaves the library it spends a lot of time on the first move. Moves it spends a lot of time on is also stored in the library. And later on I might correct moves that was played in lost hand myself. I am actually rarely satisfied with the opening moves of Valkyria. It needs more time for those moves... I was wondering if anyone was combining an opening library with MC/UCT by running a large number of the simulations and storing the results. This seems like a pretty natural extension to save simulation time in the opening. How strong a player are you? You are probably unfairly evaluating Valkyria based on your strong expert play/perspective. I'm rather amazed that MC simulations find good moves at all given that most of the playouts are nonsense games. That is why I say MC/UCT is finding reasonably robust moves with more favorable options (strategic play) not necessarily great/best moves. Because of mostly meaningless playouts it misses nuances and tactics deeper into the game that would show otherwise. It seems the deeper the simulations the worse this effect would be. -Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Wed, 2007-02-07 at 14:10 -0600, Matt Gokey wrote: I was wondering if anyone was combining an opening library with MC/UCT by running a large number of the simulations and storing the results. This seems like a pretty natural extension to save simulation time in the opening. This is not particular effective if you mean to just save the tree. But here is what I do about the opening which seems to help some: 1. Note the very first move out of book that the program is asked to search. Write the move sequence to a file. 2. Have a program running off-line that processes the positions first encountered out of book. The program searches each position 8 times using several minutes per search. This is to provide variety. The moves returned from the search are placed into the opening book. 3. The moves are played in the same proportion they were chosen. For instance if e5 is chosen 7 times and d5 1 time, the program will play e5 7 out of 8 times. The book searching code of course does all the board rotations and reflections - and when a move is chosen a random orientation is chosen if it's appropriate.For instance after the opening move e5 if d5 is a choice then it's equally likely to play d5, f5, e4 or e6. I'm building the book off-line and new positions are presented faster than new book responses can be generated.So I'm taking Lazarus off-line once in a while so the book building procedure can catch up. I don't know how much this really helps - it seems to not help much until the book gets fairly large.There are 2 ways it helps of course - the opening moves are deep searched so presumably they might be higher quality, and the time saved can be spent to improve the quality of the later moves. Lazarus spends a lot more time on early moves so this makes it possible to save a lot of time on the first 2 or 3 moves and spend it on later moves. I'm in a building phase now - the book is still quite small and has 91 positions at the moment. Most of the moves it's generating are 3 or 4 ply (moves) into the game, but some are as deep as 10 ply into the game. Probably positions from opponents who have fixed playing algorithms or books. At some point I intend to do some kind of analysis on the win/loss percentage of certain moves. One possibility is to mini-max the book lines. This way of making a book has severe disadvantages. I think it works great on 9x9 but if the program is improved, the book is suddenly not very relevant and you have to start over. Since I am not a strong player I have no way of fixing up the book. I can't recognize when it chooses a weak move or when a stronger move is available even if it doesn't like it. I have a hash funciton that creates a 64 bit cannonical hash of the position. The same hash is produced after a rotation for example. A book entry is a record with 3 fields, a priority value (how many times the deep search selected this position), the cannonical hash of the parent position and the cannonical hash of the posiiton AFTER the move is played.This makes collision very unlikely.The cannonical hash takes into consideration simple ko, so if a ko is possible it will hash differently than the same position where the ko is illegal. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Wed, 2007-02-07 at 16:17 -0500, Don Dailey wrote:
I have a hash funciton that creates a 64 bit cannonical hash of
the position. The same hash is produced after a rotation for
example. A book entry is a record with 3 fields, a priority
value (how many times the deep search selected this position),
the cannonical hash of the parent position and the cannonical
hash of the posiiton AFTER the move is played.This makes
collision very unlikely.The cannonical hash takes into
consideration simple ko, so if a ko is possible it will hash
differently than the same position where the ko is illegal.
Here is some more detail to make this clearer:
typedef struct
{
intcount; // number of times this position/response seen
(priority)
u64key; // cannonical position key
u64resp;// resulting cannonical position
} book_entry;
These book_entry records are stored in a file and I keep them
sorted. So the procedure to see if there is a book move is
to binary search the file on the parent position key,
collect all of these records together (making sure there is a
legal move which leads to the cannonical response key) and then
choose one of the available moves in proportion to the
priority values (the count field.)
- Don
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Quoting Matt Gokey [EMAIL PROTECTED]: Magnus Persson wrote: Quoting Matt Gokey [EMAIL PROTECTED]: I was wondering if anyone was combining an opening library with MC/UCT by running a large number of the simulations and storing the results. This seems like a pretty natural extension to save simulation time in the opening. I actually first tried to save the entire search tree for every position. Then it would load the position and search deeper every time it was encountered. The problem was simply disk storage, and there is always positions where the program itself cannot in a reasonable time find strong moves by searching. How strong a player are you? You are probably unfairly evaluating Valkyria based on your strong expert play/perspective. I'm rather amazed that MC simulations find good moves at all given that most of the playouts are nonsense games. That is why I say MC/UCT is finding reasonably robust moves with more favorable options (strategic play) not necessarily great/best moves. Because of mostly meaningless playouts it misses nuances and tactics deeper into the game that would show otherwise. It seems the deeper the simulations the worse this effect would be. I am european 2Dan. I agree that MC/UCT finds robust moves, it is more important to avoid mistakes in go rather than finding the best move. There often little difference between alternative bestlooking moves but a blunders can be huge. I still disagree though a little on misses nuances and tactics. I think there is always a signal from the simulations that MC can pick up to some degree. The signals that get lost or cannot be distinguished are discoverd by searching deeper with UCT. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Wed, 2007-02-07 at 16:28 -0500, Don Dailey wrote:
On Wed, 2007-02-07 at 16:17 -0500, Don Dailey wrote:
I have a hash funciton that creates a 64 bit cannonical hash of
the position. The same hash is produced after a rotation for
Most people do incremental hashing, which is cheaper even if 8(16)
symmetric copies are to be maintained. YMMV.
example. A book entry is a record with 3 fields, a priority
value (how many times the deep search selected this position),
the cannonical hash of the parent position and the cannonical
hash of the posiiton AFTER the move is played.This makes
collision very unlikely.The cannonical hash takes into
consideration simple ko, so if a ko is possible it will hash
differently than the same position where the ko is illegal.
Here is some more detail to make this clearer:
Since you seem to be replying to yourself, I'll add some comments.
typedef struct
typedef is useless here, IMO.
(but this is a matter of style, I agree)
{
intcount; // number of times this position/response seen
(priority)
Warning: alignment will cause this struct to be 3* sizeof(U64), wastong
32 bits.
Warning2: if the count is never negative, unsigned would be more
appropiate.
u64key; // cannonical position key
u64resp;// resulting cannonical position
Warning: you are wasting (64- ~9) bits here, since the response stems
from a set of 361+1 choices, maximal.
(this would be different if you intend to search backwards in the
tree/dag, with 'resp' as search key)
} book_entry;
That could reduce your struct to:
struct booklet {
u64 key;
u32 count;
u16 move;
/* you *could* store the de-canonilisation-info here: */
u16 spare;
};
, which will take only 2*64 bits.
These book_entry records are stored in a file and I keep them
sorted. So the procedure to see if there is a book move is
Sorted on key? (Keep them sorted == resort periodically)
In that case, some kind of hashing would seem more appropiate, IMHO
to binary search the file on the parent position key,
collect all of these records together (making sure there is a
legal move which leads to the cannonical response key) and then
You are not clear here.
Is there only a one-move-step between key and resp ?
Why not store the move in the first place ? (instead of the resulting
hash)
choose one of the available moves in proportion to the
priority values (the count field.)
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On 2/7/07, Unknown [EMAIL PROTECTED] wrote: to binary search the file on the parent position key, collect all of these records together (making sure there is a legal move which leads to the cannonical response key) and then You are not clear here. Is there only a one-move-step between key and resp ? Why not store the move in the first place ? (instead of the resulting hash) 128 bits of hash vs 64 bits. From his first post: This makes collision very unlikely. Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 01:00 +0100, Unknown wrote:
On Wed, 2007-02-07 at 16:28 -0500, Don Dailey wrote:
On Wed, 2007-02-07 at 16:17 -0500, Don Dailey wrote:
I have a hash funciton that creates a 64 bit cannonical hash of
the position. The same hash is produced after a rotation for
Most people do incremental hashing, which is cheaper even if 8(16)
symmetric copies are to be maintained. YMMV.
I'm an expert in zobrist incremental hashing and have been doing
it since the early years of computer chess. However, I have
some other considerations here:
No hashing is still faster than incremental hashing - which is why
I don't do any hashing during the play-out phase.
Since I am only hashing for the purpose of building or looking up
a book position, this is the best approach. If I wanted to get
clever, I could pass a flag to the move maker to tell it whether
to do hashing or not and then do it incrementally, but for all
this trouble I would not get a speedup I would ever notice since
I only hash to find a book move.
example. A book entry is a record with 3 fields, a priority
value (how many times the deep search selected this position),
the cannonical hash of the parent position and the cannonical
hash of the posiiton AFTER the move is played.This makes
collision very unlikely.The cannonical hash takes into
consideration simple ko, so if a ko is possible it will hash
differently than the same position where the ko is illegal.
Here is some more detail to make this clearer:
Since you seem to be replying to yourself, I'll add some comments.
typedef struct
typedef is useless here, IMO.
(but this is a matter of style, I agree)
There are some advantages to NOT doing it my way, but I prefer
the concise way - I don't like having to define it as
struct book_entry all over my code. It's a matter of style.
{
intcount; // number of times this position/response seen
(priority)
Warning: alignment will cause this struct to be 3* sizeof(U64), wastong
32 bits.
Warning2: if the count is never negative, unsigned would be more
appropiate.
I'm not concerned about space usage in the slightest because I have
about 100 book positions currently, and in my dreams I might get
to a few thousand.
But you are right, I could save a few bits if I didn't worry about
structure alignment.
u64key; // cannonical position key
u64resp;// resulting cannonical position
Warning: you are wasting (64- ~9) bits here, since the response stems
from a set of 361+1 choices, maximal.
(this would be different if you intend to search backwards in the
tree/dag, with 'resp' as search key)
But if I use the compact approach I lose a lot of safety. These
are hash keys and if I get a collision in key, then it's extremely
unlikely that I will get a collision in any of the child hash keys.
But if I use your scheme, I have very little extra safety (although
I still have a little bit since a move might prove to be legal in
one and not in the other, but this is probably only worth an extra
bit or two.)
To be honest, 64 bits is probably safe enough for a few hundred moves,
unlikely to cause a collision.
} book_entry;
That could reduce your struct to:
struct booklet {
u64 key;
u32 count;
u16 move;
/* you *could* store the de-canonilisation-info here: */
u16 spare;
};
, which will take only 2*64 bits.
Based on the considerations I have presented, a better layout is
something like this:
u64 key;
u32 child_key:32;
u32 count;
I'm extremely unlikely to get a collision with a 64 bit parent
and a 32 bit child, so I would use something like this to save
space.
If I wanted to use bit fields I could do something like this if
I want to sacrafice a few more bits of safety:
u64 key;
uint child_key:28;
uint count:4;
I would be happy with just a few bits in child_key because
64 bits is reasonably safe by itself.
These book_entry records are stored in a file and I keep them
sorted. So the procedure to see if there is a book move is
Sorted on key? (Keep them sorted == resort periodically)
In that case, some kind of hashing would seem more appropiate, IMHO
I don't need a complicated scheme. The book is small and always
will be small and when I insert a record I just used insertion
sort, on the fly, which is faster than quicksort on a file that
is already sorted except for one record. This is trivial easy
stuff and is bug-free. I dump the book to a file using fwrite
and it's trivial.
If I use a hashing scheme, I have to worrry about resizes and
other complexities and how to put them on the disk.
If I really get to the point where I think I can generated a
huge book, my plan would be to use the sqlite library and
I would store them using this very easy to use embedded database.
to binary search the file on the parent position key,
Re: [computer-go] MC Go Effectiveness
After looking at your message I'm not sure you understand how I set this up. On Thu, 2007-02-08 at 01:00 +0100, Unknown wrote: to binary search the file on the parent position key, collect all of these records together (making sure there is a legal move which leads to the cannonical response key) and then You are not clear here. Is there only a one-move-step between key and resp ? Why not store the move in the first place ? (instead of the resulting hash) The book has 1 record per playable move. If there are 4 responses to some position in the book, there will be 4 records, one for each possible response. Those 4 keys will have the same key field which is a cannonical key of the position. But they will have separate child keys (resp for resulting position) which are also cannonical. From some actual position it's trivial to convert the cannonical child keys to actual moves using the cannoical hash. The count is just a priority system which right now happens to corespond to how many times the book searcher wanted to play the move in question (and since I set an arbitrary limit of 8 searches, all the moves for a given position would total 8 if all the lookups have been completed.) Doing 8 searches is time-consuming, but I really prefer a book that has a LOT of variety. If I decide that the book stuff is really useful, I will probably convert it to use a sqlite3 database which is quite nice and easy to use and manage, I might even place search data such as the score and number of nodes searched in such a database. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] MC Go Effectiveness
It seems to me, the fundamental reason MC go (regardless of details) works as it does is because it is the only search method (at least that I am aware of) that has found a way to manage the evaluation problem. Evaluation is not as problematic because MC goes to the bitter end where the status is known with certainty. With random distributions it probably tends to find robust moves that leave a lot favorable options open. With MoGo, Sylvain has shown that better simulation policies can achieve much better results. But what are some of the reasons MC is not even better? -Since MC engines don't deal with tactics directly, they're not likely going to play tactical sequences well for low liberty strings, securing eye space, cutting and connecting, ko fights, or ladders, etc. -Also because most of the play-outs are usually nonsense, they may have trouble dealing with meaningful nuances because the positions that will lead to these distinctions just don't arise with enough statistical frequency in the play-outs to affect the result. Yet when very selective moves are used in the play-outs, too many possibilities can be missed. -Finally, with 19x19 anyway, the size of the board and game tree probably limits the practical effectiveness of the sampling and move ordering. I don't try to address this last point any further in this message. So here is an idea for MC research: Incorporate multiple types of distributions in one MC player. Available time resources would be divided between the different distribution methods. Then the results of these could be combined in some kind of sum/rank/vote/etc. For UCT this could be used to direct the search at those most interesting nodes. As an example, distributions such as these could be used: 1. A random or near random distribution 2. A more selective pattern based distribution 3. A simple tactical reader based distribution - this might not be obvious how to implement, but perhaps it could play tactical sequences if such conditions (based on heuristics) existed on the board, otherwise switch to one of the others. With regard to variance reduction techniques, #2 and #3 might be examples of importance sampling and conditional sampling. And the above overall method might fall under the category of stratified sampling. Thoughts? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
