[computer-go] MC Opening stage
Hi guys, It would be interesting to know how everyone limits the number of possible moves at the beginning of the game. Assuming the board is 19x19 with no handicap and black placed a stone, that leaves (in theory) 390 possible positions which translates to 390 children from the root (empty board). With my understanding of UCT it appears that all 390 positions have to be simulated numerous times and the node with the highest winrate gets explored further. *please correct me if im wrong* Do most people limit their play in corners and sides, if so how? Pruning entire branches at this stage would be a bad idea due to well documented reasons, but i have heard pruning being employed at this stage, if so what algorithms are used to smartly prune. Thanks, Please link me to the thread if this has already been discussed. _ Live Search presents Big Snap II - win John Lewis vouchers http://clk.atdmt.com/UKM/go/117442309/direct/01/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
On Wed, 2008-12-10 at 18:56 +, tony tang wrote: Hi guys, It would be interesting to know how everyone limits the number of possible moves at the beginning of the game. Assuming the board is 19x19 with no handicap and black placed a stone, that leaves (in theory) 390 possible positions which translates to 390 children from the root (empty board). With my understanding of UCT it appears that all 390 positions have to be simulated numerous times and the node with the highest winrate gets explored further. *please correct me if im wrong* Do most people limit their play in corners and sides, if so how? Pruning entire branches at this stage would be a bad idea due to well documented reasons, but i have heard pruning being employed at this stage, if so what algorithms are used to smartly prune. Some of my programs do not place any stone on the edge, unless it touches some other stone. I also count the diagonal, so if there is a stone diagonally next to an edge point, I allow a move to that point. But if there is nothing diagonally or orthogonally adjacent, I do not allow a move to that point. This is not a perfect rule. But a modification might be to not allow any move on the edge if there is a stone of either color within Manhattan distance 2 or 3 or so.Of course if you use patterns, you can start to get much more specific and consider exceptions to this rule. I think with some creativity you can produce other kinds of rules that can at least limit the choices for the first several moves. I'm too weak to know how to construct these rules. If you have a large enough database of strong master games, you might be able to construct some rules and use the database to verify that your rules are good. It could be based on building a hypothesis, then testing to see if your hypothesis holds. One must be very careful how to interpret things - because if there are 350 possible moves, the hit rate must be extremely high. So if your test rule is to prohibit one of these 350 moves, then 1 hit out of 350 is probably way too many because that is what we would expect from any average move. You want to find rules to discard moves that are close to certainty not the best move. - Don Thanks, Please link me to the thread if this has already been discussed. __ Get Windows Live Messenger on your Mobile. Click Here! ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
From: Don Dailey [EMAIL PROTECTED] On Wed, 2008-12-10 at 18:56 +, tony tang wrote: Some of my programs do not place any stone on the edge, unless it touches some other stone. I also count the diagonal, so if there is a stone diagonally next to an edge point, I allow a move to that point. But if there is nothing diagonally or orthogonally adjacent, I do not allow a move to that point. Is that only for the opening? It would exclude many monkey-jump invasions, which can be very valuable in the early end-game. Back to the original question - accounting for symmetry, there 55 distinct opening moves on a 19x19 board. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] MC Opening stage
Back to the original question - accounting for symmetry, there 55 distinct opening moves on a 19x19 board. Are there a noted collection of these opening moves? if so could you direct me to the material? cheers ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Get a bird’s eye view of the world with Multimap http://clk.atdmt.com/GBL/go/115454059/direct/01/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
From: tony tang [EMAIL PROTECTED] Back to the original question - accounting for symmetry, there 55 distinct opening moves on a 19x19 board. Are there a noted collection of these opening moves? if so could you direct me to the material? cheers Do you mean the 55 distinct opening moves? Divide a 19x19 grid along the two diagonals, and the vertical and horizontal midlines; you have eight identical pie slices. The number of points in any triangular slice is the sum of 1,2,3..10 - or 55. The slices share points along the common edges. Most of those 55 distinct moves are rarely used in the opening. I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
On Wed, 2008-12-10 at 12:03 -0800, terry mcintyre wrote: From: Don Dailey [EMAIL PROTECTED] On Wed, 2008-12-10 at 18:56 +, tony tang wrote: Some of my programs do not place any stone on the edge, unless it touches some other stone. I also count the diagonal, so if there is a stone diagonally next to an edge point, I allow a move to that point. But if there is nothing diagonally or orthogonally adjacent, I do not allow a move to that point. Is that only for the opening? It would exclude many monkey-jump invasions, which can be very valuable in the early end-game. Back to the original question - accounting for symmetry, there 55 distinct opening moves on a 19x19 board. But that number very rapidly increases after the first move as soon as the symmetry is destroyed. That would be a big reduction for the root node if the opening position is the only one we are searching. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
On Wed, Dec 10, 2008 at 12:39:55PM -0800, terry mcintyre wrote: I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. And the occasional funny guy playing the center point... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
On Wed, 2008-12-10 at 12:39 -0800, terry mcintyre wrote: Most of those 55 distinct moves are rarely used in the opening. I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. If you consider the 5th line as valid, this works on 9x9 too. The 5th line in 9x9 is the single point e5. - Don signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] MC Opening stage
And 6-7 every now and then (humans imitating MC bots?). Do you play go competitively, Tony? Dave Van: [EMAIL PROTECTED] namens Heikki Levanto Verzonden: wo 10-12-2008 21:50 Aan: computer-go Onderwerp: Re: [computer-go] MC Opening stage On Wed, Dec 10, 2008 at 12:39:55PM -0800, terry mcintyre wrote: I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. And the occasional funny guy playing the center point... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ 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 Opening stage
On Wed, Dec 10, 2008 at 09:57:18PM +0100, [EMAIL PROTECTED] wrote: And 6-7 every now and then (humans imitating MC bots?). Well, didn't Bruce Wilcox recommend an opening that built a line across the board, starting at 4-10 (middle of the side). Was supposed to be effective against people who didn't expect it, and not too bad even against those who knew it... Not something I would dare to play in a serious tournament, but then again, I don't play serious tournaments these days. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
From: Heikki Levanto [EMAIL PROTECTED] On Wed, Dec 10, 2008 at 12:39:55PM -0800, terry mcintyre wrote: I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. And the occasional funny guy playing the center point... That may be the most interesting opening! On a 9x9 board, it may be a winning strategy by Black, and it is playable on 19x19 as well; see http://senseis.xmp.net/?TengenFuseki Quote follows: Tengen has been researched by professional players in the past, and the results weren't negative. Aside of occasional historical experimentation, Kubomatsu Katsukiyo was the first to thoroughly research tengen opening, playing it in all of his spring 1934 Oteai games (when he held black). Tengen was also an important part of the shin fuseki movement that started at about that time as well. Go Seigen vs Kitani Minoru mirror go game is particularly famous. The reason why tengen opening is not played very often in practice is best summed up in the following quote Kubomatsu Katsukiyo's article Researches on Tengen: I cannot say definitely that tengen is bad. However, the reason tengen is hardly ever seen today in pro games is not that tengen is disadvantageous, but that, as that venerable old man Taisaku? said, its variations are limitless. And since one cannot analyse it as thoroughly as the four corners, everyone plays safe and does not even contemplate playing tengen. (from John Fairbairn's MindZine article describing tengen research by Kubomatsu Katsukiyo: http://www.msoworld.com/mindzine/news/orient/go/history/kubomatsu.html). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] MC Opening stage
Grandad taught me how to play when i was a kid (touching story etc) But no, just thought i'll do a go project for fun. Did anyone record how much memory it took to simulate and record 360 moves? From my understanding you have to play atleast a few hundred games of each position to give a fair estimation(light playout) ?? Subject: RE: [computer-go] MC Opening stageDate: Wed, 10 Dec 2008 21:57:18 +0100From: [EMAIL PROTECTED]: computer-go@computer-go.org And 6-7 every now and then (humans imitating MC bots?). Do you play go competitively, Tony? Dave Van: [EMAIL PROTECTED] namens Heikki LevantoVerzonden: wo 10-12-2008 21:50Aan: computer-goOnderwerp: Re: [computer-go] MC Opening stage On Wed, Dec 10, 2008 at 12:39:55PM -0800, terry mcintyre wrote: I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however.And the occasional funny guy playing the center point...-H--Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk___computer-go mailing [EMAIL PROTECTED]://www.computer-go.org/mailman/listinfo/computer-go/ _ Get Windows Live Messenger on your Mobile http://clk.atdmt.com/UKM/go/msnnkmgl001001ukm/direct/01/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
People sometimes play all kinds of silly things. It's not necessary to anticipate it all, just make sure you can keep playing reasonable moves when the other side plays strangely. There's little problem with continuing to play in the corners and sides when your opponent decides to do something else. Mark On Wed, Dec 10, 2008 at 7:02 PM, Heikki Levanto [EMAIL PROTECTED] wrote: On Wed, Dec 10, 2008 at 09:57:18PM +0100, [EMAIL PROTECTED] wrote: And 6-7 every now and then (humans imitating MC bots?). Well, didn't Bruce Wilcox recommend an opening that built a line across the board, starting at 4-10 (middle of the side). Was supposed to be effective against people who didn't expect it, and not too bad even against those who knew it... Not something I would dare to play in a serious tournament, but then again, I don't play serious tournaments these days. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ 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 Opening stage
It might be a good idea then to look at some games of competitive players to get an idea of how a game develops from the opening to the middle game and the endgame. There are some online game collections, but you could also register an account on an online go server to watch some games while they are being played (KGS for instance: www.gokgs,com). Dave Van: [EMAIL PROTECTED] namens tony tang Verzonden: wo 10-12-2008 22:08 Aan: go mailing list Onderwerp: RE: [computer-go] MC Opening stage Grandad taught me how to play when i was a kid (touching story etc) But no, just thought i'll do a go project for fun. Did anyone record how much memory it took to simulate and record 360 moves? From my understanding you have to play atleast a few hundred games of each position to give a fair estimation(light playout) ?? Subject: RE: [computer-go] MC Opening stage Date: Wed, 10 Dec 2008 21:57:18 +0100 From: [EMAIL PROTECTED] To: computer-go@computer-go.org And 6-7 every now and then (humans imitating MC bots?). Do you play go competitively, Tony? Dave Van: [EMAIL PROTECTED] namens Heikki Levanto Verzonden: wo 10-12-2008 21:50 Aan: computer-go Onderwerp: Re: [computer-go] MC Opening stage On Wed, Dec 10, 2008 at 12:39:55PM -0800, terry mcintyre wrote: I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. And the occasional funny guy playing the center point... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Read amazing stories to your kids on Messenger. Try it Now! http://clk.atdmt.com/UKM/go/117588488/direct/01/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
I've experimented with simple stuff like pruning symmetrical moves for the first two moves, and disallowing 1st and 2nd line moves for the first N moves. I toyed with the idea of rotatable zorbist hashes, but never implemented it. You should look up Remi's technique of progressive widening and Frank De Groot's statistical move likelihood. Sent from my iPhone On Dec 10, 2008, at 1:56 PM, tony tang [EMAIL PROTECTED] wrote: Hi guys, It would be interesting to know how everyone limits the number of possible moves at the beginning of the game. Assuming the board is 19x19 with no handicap and black placed a stone, that leaves (in theory) 390 possible positions which translates to 390 children from the root (empty board). With my understanding of UCT it appears that all 390 positions have to be simulated numerous times and the node with the highest winrate gets explored further. *please correct me if im wrong* Do most people limit their play in corners and sides, if so how? Pruning entire branches at this stage would be a bad idea due to well documented reasons, but i have heard pruning being employed at this stage, if so what algorithms are used to smartly prune. Thanks, Please link me to the thread if this has already been discussed. Get Windows Live Messenger on your Mobile. Click Here! ___ 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 Opening stage
and there are nontrivial arguments concerning points way out near the center. s. On Wed, Dec 10, 2008 at 3:39 PM, terry mcintyre [EMAIL PROTECTED] wrote: From: tony tang [EMAIL PROTECTED] Back to the original question - accounting for symmetry, there 55 distinct opening moves on a 19x19 board. Are there a noted collection of these opening moves? if so could you direct me to the material? cheers Do you mean the 55 distinct opening moves? Divide a 19x19 grid along the two diagonals, and the vertical and horizontal midlines; you have eight identical pie slices. The number of points in any triangular slice is the sum of 1,2,3..10 - or 55. The slices share points along the common edges. Most of those 55 distinct moves are rarely used in the opening. I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. ___ 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 Opening stage
Most of those 55 distinct moves are rarely used in the opening. I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. Wandering off the opening theme a bit, but the book, Oriental Strategy in a Nutshell, by Bruce and Sue Wilcox has numerous rules of thumb of this nature. It will probably appeal to the people on this list more than the wishy-washy play here because it feels good style of most traditional go books. The rules might be useful in MC heavy playouts. Going back to the topic, for 19x19 at least, I would suggest make an opening book from pro and strong amateur games. Only start using MCTS once you leave the book. Using MCTS on the first move is like trying to use a precision screwdriver to hammer in a three-inch nail: your tool will break before you get any worthwhile results. Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
