Re: [Computer-go] Fwd: News on Tromp-Cook ?
On Mon, Jan 03, 2011 at 08:24:43AM +0800, Aja wrote: Zen uses sequence-like AND probabilistic simulation. Basically it plays around the previous move randomly like MoGo, and these moves are biased by gamma values like Crazy Stone. I am also trying to use probabilistic simulation on the whole board, but it does not yet succeed. The main problem is how to combine the semeai, seki and useless-move detection with it. Very surprised that Zen is using partly sequence-like simulation like Mogo. Erica uses probabilistic simulation completely. I am not sure if my implementation is good enough to be called succeed , but I am sure that you will succeed. Hmm, I thought based on your paper that Erica uses a sort of a hybrid - probabilistic simulation completely, but with all but 3x3 feature filled in only around the last move anyway. So, one could say, Zen-like, but with 3x3-based tenuki sampling or whatever you want to call it. :-) Has this changed recently? Petr Pasky Baudis ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Combinatorics of Go
Hi Robert, Perhaps my answer was a bit cryptic. I'll try to explain. In a computer go program it is indeed needed to detect cycles when you want to claim, for example, a tie or no-result. So you're right about that. However, to evaluate a position and infer the best move it is generally not needed as long as you don't care about distinguishing between not having a final result due to the position being too complex to reach a terminal state and not having a final result because the search will never reach a final state. (Notice though that in both cases eventually the optimal move can still be found). Say for simplicity we select our move based on an iterative deepening alpha beta search that ignore some aspects of the history. In case of a potential long cycle the search will simply not return a final result unless the komi is high or low enough for one side to deviate from the cycle. The way I think about it is that a cycle is only a true cycle when nothing in the state distinguishes the first occurrence of a position form later occurrences. Superko requires adding something to the state that distinguishes the first occurrence from later occurrences, so in that sense I meant that the cycle is no longer a true cycle (i.e., it is broken). Regarding the conjecture you propose, I'd rather formulate it as: Under Japanese style ko rules, the long-term history is never needed to infer the best move. Some short-term history is however still needed for things like basic-ko end game-ending passes. Best, Erik On Mon, Jan 3, 2011 at 7:57 AM, Robert Jasiek jas...@snafu.de wrote: On 02.01.2011 22:04, Erik van der Werf wrote: to 'not return a result' you don't need the history. How? A cycle is a presupposition for the result No Result (or long cycle tie). (Of course, hashing by numbers of stones on the board or Cycle Law's prisoner difference etc. may often be sufficient, but if it is not, then determining a cycle by referring to history is necessary.) When optimal play leads to a cycle a) necessarily b) optionally then any state in that cycle should lead to an equivalent cycle. I am not sure exactly what you mean by this. Do you want to say that, given the game's move-sequence so far, its last moves, if they are about to be in cycles, then necessarily they are in the same cycle? You still need to establish the fact whether they are in a cycle. Superko rules, always returning a result, just need more because they break more. How do they break more? They break less by not creating any repetition:) Maybe you want to say: They have to detect the first repetition before it is executed. Ok, let us assume that under Japanese style rules the programs just recycle a bit, using the same or different cycles, until trying to apply the long cycle rule. They still need to detect that they have been playing some cycle at all. See above: You need the history because hashing does not guarantee detection. So, you or Olivier tell me why not having to use history! Are you having some insight I overlook? (In CG practice, the history can be ignored as a first approach - under superko or Japanese style ko rules. To be sure though, history is needed.) Do we need to do the maths? Your conjecture seems to be: Under Japanese style ko rules, the history is never needed to apply the No Result / long cycle tie rule. I claim the opposite (might be needed). -- robert jasiek ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Combinatorics of Go
On 03.01.2011 12:11, Erik van der Werf wrote: Under Japanese style ko rules, the long-term history is never needed to infer the best move. Do you mean long2 or longcycle_length? -- robert jasiek ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Fwd: News on Tromp-Cook ?
Hi Petr, Hmm, I thought based on your paper that Erica uses a sort of a hybrid - probabilistic simulation completely, but with all but 3x3 feature filled in only around the last move anyway. So, one could say, Zen-like, but with 3x3-based tenuki sampling or whatever you want to call it. :-) Has this changed recently? No, at the time of our simulation balancing paper, Erica was using probabilistic simulation completely, without seki knowledge. That also surprised Remi and me much, that balanced simulation is so powerful: achieved 80% against Fuego 0.4 without dealing with seki completely. I don't understand what do you mean by 3x3-based tenuki sampling. Right now Erica is using a difference approach. I have already described to Yamato in private. Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Some newbie questions
On Jan 3, 2011, at 10:47 AM, Joona Kiiski wrote: Hi everyone! In last few years I've spend a lot of time with computer chess, but in general I found Go much more interesting than chess. I have zero experience in writing go program, but I've read with great interest about Monte Carlo playouts being a highly effective new weapon in computer go. Question 1: How does one playout go? Are you using completely random moves or something smarter? Biasing the playouts to smarter moves often helps, although there can be paradoxical behavior. One basic trick almost everyone uses is to never play in a possible eye, which is a vacant point surrounded orthogonally by friendly stones, with no more than one (away from the edge) or zero (at the edge or corner) diagonal neighbors occupied by enemy stones. Question 2: Are there some (preferably high-quality) open-source programs around? I took a look at GnuGo, but it's terribly complex and seems to presents era before MC-breakthrough. A very clean, readable version of Orego will be released in the next week. Several people have used it in their research, and it's a good place to start (assuming you know Java). In tournaments, Orego generally comes in above the weak programs and below the very strong programs. Question 3: Are there standardized protocols which allow programs easily play against each others? Are there GUIs or tourney managers to easily play a lot of engine-engine matches. GTP is the standard protocol: http://www.lysator.liu.se/~gunnar/gtp/ Tournaments are held monthly on the KGS Go Server. Watch this list for details. If the conditions are right, I might want to try Go-programming in near future... Joona Kiiski Best of luck! Peter Drake http://www.lclark.edu/~drake/ ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Some newbie questions
Hi Joona! Good to see you pop up here. I think there are several open source go programs. I think fuego is one of the better ones but I could be wrong. The playouts started out as simply uniformly random games with the only condition that you did not fill your own 1 point eye.But then it was found that some intelligence could be added to how the random games were played. GTP is by far the standard protocol for Go programs. I'm sure others will give you much more detailed information. Don On Mon, Jan 3, 2011 at 1:47 PM, Joona Kiiski joona.kii...@gmail.com wrote: Hi everyone! In last few years I've spend a lot of time with computer chess, but in general I found Go much more interesting than chess. I have zero experience in writing go program, but I've read with great interest about Monte Carlo playouts being a highly effective new weapon in computer go. Question 1: How does one playout go? Are you using completely random moves or something smarter? Question 2: Are there some (preferably high-quality) open-source programs around? I took a look at GnuGo, but it's terribly complex and seems to presents era before MC-breakthrough. Question 3: Are there standardized protocols which allow programs easily play against each others? Are there GUIs or tourney managers to easily play a lot of engine-engine matches. If the conditions are right, I might want to try Go-programming in near future... Joona Kiiski ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Some newbie questions
Hey Don, I doubt anyone would have faulted you for mentioning CGOS, which is very valuable for testing go programs. Cheers, David On 3, Jan 2011, at 10:57 AM, Don Dailey wrote: Hi Joona! Good to see you pop up here. I think there are several open source go programs. I think fuego is one of the better ones but I could be wrong. The playouts started out as simply uniformly random games with the only condition that you did not fill your own 1 point eye.But then it was found that some intelligence could be added to how the random games were played. GTP is by far the standard protocol for Go programs. I'm sure others will give you much more detailed information. Don ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Some newbie questions
One basic trick almost everyone uses is to never play in a possible eye, which is a vacant point surrounded orthogonally by friendly stones, with no more than one (away from the edge) or zero (at the edge or corner) diagonal neighbors occupied by enemy stones. Just curious. Does this mean that x cant kill o at #? #xxox xxoox .oo.x oo.x. ..x.. xx... . Stefan ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Some newbie questions
Welcome, On Mon, Jan 3, 2011 at 10:47 AM, Joona Kiiski joona.kii...@gmail.comwrote: Hi everyone! In last few years I've spend a lot of time with computer chess, but in general I found Go much more interesting than chess. I have zero experience in writing go program, but I've read with great interest about Monte Carlo playouts being a highly effective new weapon in computer go. Question 1: How does one playout go? Are you using completely random moves or something smarter? Question 2: Are there some (preferably high-quality) open-source programs around? I took a look at GnuGo, but it's terribly complex and seems to presents era before MC-breakthrough. There are many choices here, some already mentioned. Basic and educational is the classic Brown engine, which features a 'heavy' random move generator (no search) On the list you can search for source-code for several reference bots (RefBot, in Java, C, C++, Go [Gongo], and some other languages) LibEgo is an elegant and efficient (earlier versions, anyway) open source C++ MCTS-engine Orego is an open source Java MCTS-engine Fuego is a fully featured and well documented C++ MCTS-engine (several engines on a general framework) A bitmap-based implementation of light playouts can be found searching for BitmapGo in the list Browse around on Sensei-library for more suggestions Question 3: Are there standardized protocols which allow programs easily play against each others? Are there GUIs or tourney managers to easily play a lot of engine-engine matches. Others already mentioned gtp as the protocol, but look for GoGui as a GUI frontend (implemented in Java), that also allows automated bot-to-bot matches. Gomill is a recent, more extensive framework for bot-to-bot matchups. Finally, CGOS is an often used bot-server for 9x9, 13x13, and 19x19 play, where you can establish a rating against other bots. Play against humans on KGS. Good luck, René If the conditions are right, I might want to try Go-programming in near future... Joona Kiiski ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Some newbie questions
Hi! On Mon, Jan 03, 2011 at 12:50:31PM -0800, René van de Veerdonk wrote: LibEgo is an elegant and efficient (earlier versions, anyway) open source C++ MCTS-engine Orego is an open source Java MCTS-engine Fuego is a fully featured and well documented C++ MCTS-engine (several engines on a general framework) You might also find Pachi interesting. It is one of the stronger engines, with strength comparable to Fuego, but with much smaller and more straightforward codebase; none of its code is game-agnostic like in Fuego, but if you care just about Go, you might find it much easier to find your way around. -- Petr Pasky Baudis Computer science education cannot make an expert programmer any more than studying brushes and pigment can make an expert painter. --esr ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] Combinatorics of Go
On Mon, Jan 3, 2011 at 2:13 PM, Robert Jasiek jas...@snafu.de wrote: On 03.01.2011 13:44, Erik van der Werf wrote: This is handled trivially by observing that one sided passes/captures more in each cycle. How do you distinguish that from the opposing program passing as a tactical mistake (or as a psychological trick)? If the opponent passes this knowledge becomes available by the small finite list of extra features I described before. BTW I don't see how one could play a psychological trick against a program. I suppose the best one could hope for is to trigger a bug. can work out the details. Easy: almost never is a better description. The word 'almost' to me suggests that you would know for sure that there exists an exception. I'm not convinced that is the case. Erik ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] Computer Go blog
I started a blog about computer Go on http://computer-go-adventures.blogspot.com/ So far there are three posts on UEC cup (long), John Tromp's shodan bet games against Many Faces (short) and the upcoming BIRS workshop (short). Enjoy! Martin ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go