Re: [computer-go] Re: Hahn system tournament and MC bots
Hi, Hahn go strategy is only relevant for a tournament (otherwise one can simply play normal go, it doesn't matter by how many points one wins). And thus it includes a meta-strategy involving the results in the other games and knowledge of one's opponents. One can also play a single game for instance with money bets based on the Hahn points, which makes Hahn go strategy relevant also for a single game. In the tournament setting, in your interpretation, the goal is not to maximize the (expected) number of Hahn points in each game, but to maximize the probability of having more Hahn points at the end of the tournament than your opponent(s). It would also be useful to see what is happening on the other boards during a tournament round, since it might affect your point goal. It might even be useful to spend time waiting in order to gather information from the other boards. ;-) Tapani -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
Vlad Dumitrescu wrote: On Tue, Nov 24, 2009 at 11:18, Tapani Raiko pra...@cis.hut.fi wrote: One can also play a single game for instance with money bets based on the Hahn points, which makes Hahn go strategy relevant also for a single game. Just a thought: if the bet is I can beat you with X points on the board or more, then it's exactly like trying to win a normal game with X points komi, right? Are there any other kind of bets? Yes, having to pay the amount of Hahn points in money. The Hahn system originates from the Korean betting system, mentioned also in the novel First Kyu by Sung-Hwa Hong. Both players deposit the amount for the maximum loss under the go board and the money is split after the game according to the score. See also: http://www.suomigo.net/wiki/HahnSystem Tapani -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] demonstration match
Hi, I will arrange a demonstration match between MoGo v. 4.86 vs. Javier-Aleksi Savolainen (Finnish 5d). Time: Saturday 24th Oct at 9-11 am UTC. Location: Helsinki, Finland, Alternative Party digital culture festival ( http://www.altparty.org/2009/ ) Virtual location: KGS ( http://www.gokgs.com/ ) in room Computer Go, match Assu vs. MoGoAltPar. The computer provided by CSC will be either a 56-core Cray CX1 available locally at the festival, or part of the 10864-core Cray XT5/XT4 (49th fastest on the latest top500 supercomputers list). I'd like to thank AltParty, CSC, KGS, and MoGo teams for the opportunity! Tapani Raiko -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Software for a supercomputer?
Hi all, I have a possibility to organize a demonstration match with a strong human against a supercomputer at the Alternative Party in Helsinki, Finland on Oct 23-25, http://www.altparty.org/ which is a fair for computer enthusiast. The expected participation is over 1000 people. The computer (Cray CX1) has a Linux operating system, but I might be able to boot it from a USB stick to Windows, too. It consists of nodes that each have a 2 x quad core Xeon E5472 3.0GHz CPU and 32 GB RAM. I heard that with OpenMP it could parallelize within one node, but to get the full power, one would need to use MPI. I am now asking for help. Do you know which program could be used for best performance (or most cores)? Is it easy to set up things running? (I need to decide soon whether I will organize it or not.) Thanks in advance, Tapani Raiko -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
I don't think the komi should be adjusted. Instead: Wouldn't random passing by black during the playouts model black making mistakes much more accurately? The number of random passes should be adjusted such that the playouts are close to 50/50. Adjusting the komi would make black play greedily, while random passing during playouts would make black play safe (rich men don't pick fights). Tapani Raiko Christoph Birk wrote: I think you got it the wrong way round. Without dynamic komi (in high ha ndicap games) even trillions of simulations with _not_ find a move that creates a winning line, because the is none, if the opponet has the same strength as you. WHITE has to assume that BLACK will make mistakes, otherwise there would be no handicap. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: hex robot
GTP you can simply use as-is, I don't see why that wouldn't work. GoGui is also open-source and can possibly also be easily adapted to Hex as well. But to be honest, I don't really need a Gui that much. But twogtp is really useful. HexGui already exists. It uses GTP. Here's a link: http://mgame99.mg.funpic.de/downloads.php -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] BOINC
milestone 1: All network-nodes compute pure Monte-Carlo (no search tree) scores for the possible moves, the scores are combined centrally to pick the move. It's easy, it will wring out the system, and the bandwidth is low. The playing performance will always be poor because this algorithm doesn't scale well. milestone 2: Each network-node builds its own tree using UCT, but information is only combined at the root. This version will play much better because each node is smarter. The bandwidth will be higher. I can only guess at the scaling behavior, but this milestone might be the 80% solution. milestone 3: Information from the search-nodes is shared between network-nodes, but only for search-nodes close to the root of the tree. Sounds innocent enough. You just limit the shared nodes to the first couple of plys. But it's a trap that will suck you in: best scaling behavior requires too much communication-but what if you made each Monte-Carlo simulation smarter...? Why not make each computer specialize in a certain branch of the tree? That way the (implicit) combination of the trees of all the computers could grow very large. Of course some central intelligence would need to allocate resources to different branches dynamically, so it would be more difficult to implement. In these three milestones, the different computers would do a lot of overlapping work with the deeper nodes, if I understood them correctly. -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
Chris Fant wrote: Ho can I find Go vids on youtube? Searching for go obviously does nothing. Atari was also a good keyword here. There it is: http://www.youtube.com/watch?v=qt1FvPxmmfE -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Former Deep Blue Research working on Go
May sound unpolite. But Deep Blue reached a very important step in IA. They will be known for ever. But, from a research point of view, they didn't much really. It was mainly a technological/technical achivement. Maybe they will reimplement Mogo, try a null-move tweak, use a supercomputer, and claim to have the strongest computer Go player ever. :-) -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Slightly improved MC algorithm
Ownership map is a good term! Go81 (and Go169) also uses the ownership map (since 2002). In Palm handhelds, I can afford to do just two playouts, so the ownership map is much more informative than the first moves. I look for large neutral areas (especially moves that are close to both white and black areas) and so on. Similar heuristics might be useful deeper in the UCT where there are very few play-outs. -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Slightly improved MC algorithm
I like your program and I actually tested it against yours during developement. But I didn't test Go169, what is that? I changed the name from Go81 to Go169 at the time I switched from PalmOS4 to PalmOS5. It also includes some 5x5 patterns which help with boards larger than 9x9=81. (Go81 only has 3x3 patterns.) There is also a GTP-supporting .exe so you can test the strength without a Palm. On a PC the two playouts don't take much time. ;-) http://www.cis.hut.fi/praiko/go169/ -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte Carlo (MC) vs Quasi-Monte Carlo (QMC)
I could see a case where it is possible to reduce a variance of a single variable even in the 0-1 case. Let us say that black has about 5% chances of winning. If we could (exactly) double the chances of black winning by changing the nonuniform sampling somehow (say, enforce bad moves by white), we could sample from that and divide the estimated black's winning chance in the end by 2. This would of course be very difficult in practice. (A binary random variable gives more information when the chances are closer to 50-50.) This could be useful in practice in handicap games, by for instance enforcing a black pass with 1% chance every move. Sampling would be distorted towards white win, which is realistic since white is assumed to be a stronger player, anyway. I don't understand this line of reasoning. Let my try again using the handicap example. Let's say MC player is given a huge handicap. In the simulations, it is winning all of its games, so there is no information helping to select the next move. Using information theory, each play-out gives one bit of information if the chances are 50:50, but if the chances are unbalanced, the information content is lower. (see http://en.wikipedia.org/wiki/Binary_entropy_function ) In the extreme case, there is no information at all. Now, let us use distorted MC where we enforce black to pass with a few percent chance every move. White begins to win some of the simulations, so MC is useful again. How this is related to reducing the variance? Let us say that a black move leads to a white win with probability p very close to zero. Let us also assume that distorting the simulations doubles white's chances to 2p. Using normal MC, the variance of our estimate of p using N samples is p*(1-p)/N and using distroted MC, the variance of 2p is 2p*(1-2p)/N estimating p by using the estimate of 2p, the variance is divided by 4: p*(1-2p)/2N which is less than p*(1-p)/N. In practice, we cannot know that distorting would increase the chances exactly by doubling them, but if we use the same distortion to estimate all moves, we can still compare them. Tapani ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte Carlo (MC) vs Quasi-Monte Carlo (QMC)
It seems that there are at least three cases: 1: Choosing a random move from a uniform distribution 2: Choosing a random move from a nonuniform distribution (patterns etc.) 3: Choosing a move taking into account what has been chosen before The concensus seems to be that numbers 1 and 2 are MC and 3 is QMC. Mogo uses QMC within the tree in memory and MC for the leaves, so which should it be called? And about reducing variance: In games you only care about estimating the goodness of the best moves (in order to select the best one). You don't care how bad a move is, if you are fairly certain that it is not the best one. You should thus reduce the variance of the best moves, that is, study them more often. This is exactly what UCT is about, reducing the variance of variables of interest. I could see a case where it is possible to reduce a variance of a single variable even in the 0-1 case. Let us say that black has about 5% chances of winning. If we could (exactly) double the chances of black winning by changing the nonuniform sampling somehow (say, enforce bad moves by white), we could sample from that and divide the estimated black's winning chance in the end by 2. This would of course be very difficult in practice. (A binary random variable gives more information when the chances are closer to 50-50.) This could be useful in practice in handicap games, by for instance enforcing a black pass with 1% chance every move. Sampling would be distorted towards white win, which is realistic since white is assumed to be a stronger player, anyway. To summarise, I agree that there are links to other MC research, and they should be explored. -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is skill transitive? No.
Would the results of kgs (or similar) games being appropriate if one considered only un-handicapped games? Yes, I think so. At least when considering only those who have played lots of games against lots of opponents. I imagine that the most significant intransitivity would be would be in relation to the bots (principally GnuGo?), because some players have played dozens (maybe hundreds) of games against these bots and their playing style is likely to have been modified by the experience. True. Another effect that might appear is if part of the players are developing in skill and at the same time switching to stronger opponents. Or perhaps some are better in changing their style (risk level) according to opponent strength. Maybe CGOS data would be the best: lots of games between a limited number of stable players. Tapani ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Interesting problem
I assume that cannot be captured by the opponent means that the opponent, playing first, cannot capture it. I accept that it is unclear whether this opponent is the actual one present in the game, or a hypothetical competent one. In an unresolved semeai it is not clear who is the one trying to capture and should thus get the first move. One more vote for simple rules. :) -- Tapani Raiko, [EMAIL PROTECTED], +358 50 5225750 http://www.cis.hut.fi/praiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/