Re: [computer-go] Monte-Carlo Go simulation
Le jeudi 8 février 2007 22:09, Sylvain Gelly a écrit : It seems i was ambiguous: I was speaking of the simulation player too. What i meant is a random simulation player is not biased, whereas a better simulation player is biased by its knowledge, and thus can give wrong evaluation of a position. I think we have to start defining what the bias. For me the bias is the difference between the expected value of the outcomes of playouts by the simulation player and the real minimax value. In this definition the uniform random simulation player is VERY biased and gnugo much less. OK, by i used bias in common sense, to mean that the strong simulator has preferences for some moves, and doesn't consider them equally, or worse doesn't consider some moves. So it will miss some good points due to its knowledge, whereas the random player will find the move. A trivial example is GNU Go: its analyze is sometimes wrong. Of course, if not computer go would be solved :-). Even if it is obviously much stronger than a random player, it would give wrong result if used as a simulation player. Hum, are you sure? I m 100% sure of this :-) I think that GnuGo with randomisation, (and much faster of course) would make a very good simulation player (much better than any existing simulation player). Even with randomization, GNU Go considers only a few dozen of possible moves, and makes systematic errors. Some times ago Rémi Coulom asked for positions illustrating computer stupidity (2006-11-22) http://computer-go.org/pipermail/computer-go/2006-November/007107.html and GNU Go provided some nice examples where its (wrong/misunderstood) knowledge induces a failure in play. One very impressive was GNU GO 3.6 not invading where obviously it is possible to invade (Steven Clark 2006-11-27) http://computer-go.org/pipermail/computer-go/2006-November/007184.html But a weaker player than GnuGo can make an even better simulation player. yes. David Doshay experiments with SlugGo showed that searching very deep/wide does not improve a lot the strength of the engine, which is bound by the underlying weaknesses of GNU Go. Yes, this a similar non trivial result. I think there are more existing experimental and theoritical analysis of this, though. Perhaps such an analysis already exist for MC also, it is just that I don't know. Or maybe i just understood nothing of what you explained ;) It was not really explanations, just thoughts. I have no the solution, just think that it is an interesting question, and that it may be discussed. May be from a strong explanation of this phenomenon could come new ideas. I understand all these counter examples, I just think that it is more complicated than that. Sylvain I fully agree. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
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/
[computer-go] pure random mode
Hi Sylvain, In the MoGo report paper, you make this statement: We also privilege the moves eating some stones. This refers to a version of MoGo that doesn't have the pattern knowledge and you call it the pure random mode. My program does this too but in a probabilistic way. I'm curious about how you did that in Mogo. Did you always play a capture when one was available for instance? Were you selective about which captures to play? - Don P.S. Here is more context from your paper: In our pure random mode, legal moves are played on the Go board uniformly randomly, with few rules preventing the program from filling its own eyes. This is probably like what the other Monte-Carlo programs use. We also privilege the moves eating some stones. On CGOS the bot named MoGo using exactly this mode has achieved rank 1647. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Serializing a very large object in Java
Peter, java serialization is not a good way to do persistent storage of any kind, especially large data structures. It has some pretty severe drawbacks: - It is slow - It breaks easily (ie, becomes unable to load older data sets) when you make even small changes in your code. - It makes inefficient use of space - The format is difficult to decode or manipulate in any way other than reading or writing with the exact .class file used to generate the serialization code. Java serialization is excellent for RMI, but is pretty poor for any other use. I've used serialization myself several times and I regretted it every time (except for when I used it for RMI). My advice would be to come up with your own data format and use that. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Serializing a very large object in Java
Is this opening book database used for the UCT portion, or the playout portion of Orego? In the UCT portion, speed of access may not be that important; a database would probably be ideal. If used during the playout, then speed of access is more crucial. Terry McIntyre UNIX for hire software development / systems administration / security [EMAIL PROTECTED] - Original Message From: Nick Apperson [EMAIL PROTECTED] What type of data are you trying to serialize or rather store to disk? Do you have pointers in the data. Don't tell me you don't have pointers just because it is java. Java has pointers, it just preteneds it doesn't. Show us the datastructure and we can probably help you more. If each entry has no pointers than your task should be pretty straightforward. If you do have them, you are going to need to find a way to store those so that they are able to be redetermined. In a language like java, where you can't do pointer arithmetic or anything of the sort this can get rather difficult. Also, have you considered using a database instead of a flat file to store this data? - Nick On 2/9/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Peter, java serialization is not a good way to do persistent storage of any kind, especially large data structures. It has some pretty severe drawbacks: - It is slow - It breaks easily (ie, becomes unable to load older data sets) when you make even small changes in your code. - It makes inefficient use of space - The format is difficult to decode or manipulate in any way other than reading or writing with the exact .class file used to generate the serialization code. Java serialization is excellent for RMI, but is pretty poor for any other use. I've used serialization myself several times and I regretted it every time (except for when I used it for RMI). My advice would be to come up with your own data format and use that. ___ 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/ Any questions? Get answers on any topic at www.Answers.yahoo.com. Try it now.___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Serializing a very large object in Java
On Feb 9, 2007, at 10:48 AM, Nick Apperson wrote: What type of data are you trying to serialize or rather store to disk? Do you have pointers in the data. Don't tell me you don't have pointers just because it is java. I wouldn't dream of it. Java has pointers and I use the hell out of 'em. Java has pointers, it just preteneds it doesn't. Show us the datastructure and we can probably help you more. If each entry has no pointers than your task should be pretty straightforward. If you do have them, you are going to need to find a way to store those so that they are able to be redetermined. Java's serialization mechanism does this automagically. In a language like java, where you can't do pointer arithmetic or anything of the sort this can get rather difficult. Also, have you considered using a database instead of a flat file to store this data? I'm going to try Terry's idea of storing individual Nodes instead of storing the entire Node pool. Stay tuned... Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Serializing a very large object in Java
The UCT portion. I'm storing/loading a pre-built UCT tree once at startup; the disk is not accessed during the game. Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ On Feb 9, 2007, at 11:08 AM, terry mcintyre wrote: Is this opening book database used for the UCT portion, or the playout portion of Orego? In the UCT portion, speed of access may not be that important; a database would probably be ideal. If used during the playout, then speed of access is more crucial. Terry McIntyre UNIX for hire software development / systems administration / security ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach
I don't seem to have any numbers on this anymore, but I should be able to try some experiments this weekend. I do have some code that does what I describe below. It is also using an all moves as first heuristic. According to my notes, I made this change in an attempt to avoid severely conservative (in my non-expert opinion) moves near the beginning of the game, which seem to be preferred when using all-moves-as-first. It specifically aims for a 30-point lead at the beginning of the game, and reduces this by one point for each turn into the game. I should point out that I am not averaging scores, but simply changing which games I count as wins for the evaluation of a move. This is perhaps not quite what Steve Uurtamo had in mind when he was originally musing about being greedy at the beginning of the game. Nevertheless, it is a very similar sort of idea to what he described, so I thought that I would mention it. Weston On 2/8/07, Chris Fant [EMAIL PROTECTED] wrote: On 2/8/07, Weston Markham [EMAIL PROTECTED] wrote: I believe that I have had some success with an approach like this, actually. I believe that I initially only tally games that are won by a certain margin, and reduce that margin to zero as the game progresses. I am pretty sure that this improves upon straight Monte Carlo. I think that I can get some numbers on it, if anyone is interested. Weston Yes, please. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Serializing a very large object in Java
Three alternative options to Java's native serialisation: * Object database db4o: http://db4o.com * WOX (Web Objects in XML) (my own) http://algoval.essex.ac.uk/wox/serial/readme.html * JSON (JavaScript Object Notation) - also has Java libraries. Simon Lucas -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] Sent: 09 February 2007 18:40 To: computer-go@computer-go.org Subject: Re: [computer-go] Serializing a very large object in Java Peter, java serialization is not a good way to do persistent storage of any kind, especially large data structures. It has some pretty severe drawbacks: - It is slow - It breaks easily (ie, becomes unable to load older data sets) when you make even small changes in your code. - It makes inefficient use of space - The format is difficult to decode or manipulate in any way other than reading or writing with the exact .class file used to generate the serialization code. Java serialization is excellent for RMI, but is pretty poor for any other use. I've used serialization myself several times and I regretted it every time (except for when I used it for RMI). My advice would be to come up with your own data format and use that. ___ 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] Zobrist hashing with easy transformation comparison
On 2/10/07, Antoine de Maricourt [EMAIL PROTECTED] wrote: Hi, did you read Anti Huima's paper? The idea looks similar, but unfortunately it does not work. I provided a proof of the defect on this list (end of 2002 if I remember well). It's not that easy to get a working scheme. In fact there is only one combination with 8 chunks of data. In 2002 I exchanged a lot of email with Nici Schraudolph, and we found the right scheme. We wanted to write a paper, but we did not (it takes time, and I had not that much time - mathematic and computer go is just a hobby for me). After having the right scheme, the tricky part is to perform a statistical analysis: unfortunately introducing constraints to deal with symetries weakens the hash key. The probability of collision becomes non uniform and depends on the board configuration. In short: if you take two different random board configurations, then the probability that they have the same key becomes higher if one of the configuration has self symetries. If there is strong interest, I can post the scheme. Please do. But I'm not sure I will post the statistical analysis (it was almost ten hand writen pages, and I'm not sure I still have them). Have You performed an empirical test for collisions? Best, Łukasz Lew Antoine. ___ 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] Zobrist hashing with easy transformation comparison
Sorry for posting then, I didn't realize that it had been tried. I may work through the problem and try to get it to work in order to fully understand why it in fact does not work. If by some miracle I manage to get something working with a collision rate of 1/(2^61) I'll certainly post it. Thanks for the info. - Nick On 2/9/07, Erik van der Werf [EMAIL PROTECTED] wrote: Nick, The basic idea of what you're describing is well known. It was first published by Antti Huima several years ago. Unfortunately though, his implementation was flawed. I didn't check your code but likely it suffers from a similar defect. It is possible to fix the defects in Huima's scheme. If you ignore colour symmetry it's relatively easy to find a defect-free xor-based scheme that works with 8 segments. The more interesting part is in finding the minimal number of segments, and then proving correctness. Nic Schraudolph has done some interesting work on this, but as far as I know he still hasn't published it. Maybe if we all sit on him we can finally get him to finish it :-) Erik On 2/9/07, Nick Apperson [EMAIL PROTECTED] wrote: Hey all, I was thinking about our conversation and i decided to design a zobrist class that allows for easy comparison to check and see if 2 different zobrist values are equivalent after a rotation etc... It updates the zobrist in such a way that it can transform them and after trying 8 possiblilities, it can determine if they are equal. There are actually quite a few optimizations that could be performed on it, but I just wanted to post the basic idea. See the following source code for the basic idea: http://www.nicholasapperson.com/computergo/zobrist.h Essentially it works so that it hashes the played stone as each of the rotated forms and stores that in each of the 8 bytes used. The bytes are arranged in an order such that flipping the 2 DWORDs results in the zobrist value for if there was a rotation in the x axis, flipping WORDs results in a reflection across the y axis and swapping bytes results in a reflection across the y=x line. Order obviously matters in the case of xy so the transformation is assumed to take place after the other reflections. For example: if we have 0x1234567890ABCDEF as a zobrist value, 0x90ABCDEF12345678 would be the zobrist of the position with a reflection across the x-axis Anyway, I'm sure there is a bug or two, but I wanted to get your alls thoughts. - Nick ___ 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] Serializing a very large object in Java
At 09:55 AM 2/9/2007, you wrote: ..., Java has a stack overflow error. i assume you have tried the java -Xss to set the stack size (type java -X for help on these)? thanks --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
