Mark Boon wrote: > I did an experiment that looks rather similar. I generated patterns > and only kept the ones that had a minimum amount of 'urgency' and a > minimum number of occurrences. But I noticed two things when using > these patterns in a MC playout: > > 1) There are many important moves missing. Apparently they were not > picked up from the game-database even though the number of games is in > the 10-thousands.
Are these fixed patterns or wildcard patterns? I'm interested in wildcard patterns too and how to automatically generate them. A wildcard pattern is exactly the same as a decision tree (it can be represented perfectly by a decision tree.) There are several methods in AI that have similar function and performance to decision trees - and that's why these methods are interesting to me. They are different ways of looking at wildcard pattern generation. > > 2) When I used these patterns during simulation the playouts suddenly > look surprisingly like normal Go compared to random playouts. However, > the program started to play worse. Much worse. Even when I let it > compute as many playouts as a program without patterns. This of course is now a well known phenomenon. > > The first observation made me wary to rely on harvested patterns. I > think it shows at least it needs to be used in combination with > hand-crafted patterns. Also it means that the fact you harvest a large > number of patterns isn't necessarily meaningful. It isn't necessarily the quality of the moves that is important it seems. All playouts, including uniformly random playouts, set up certain type of bias. Uniformly random playouts have the characteristic that stupid errors are compensated by stupid errors by the opponent and so tend to weakly balance out and return a "reasonable" evaluation. Heavier playouts have been shown to be far superior, but just placing stronger moves in the playouts does not seem to be the right formula. My guess is that if you place arbitrary knowledge into the playouts, you create terrible imbalances. Perhaps the secret (I'm entering uncharted territory here) is that it's ok to create imbalance if it's the type the tree is easily able to correct. This is my working theory, let's call it "maximum information gain." The early Mogo paper showed that it's good to look at defending opponents atari. Defending an atari tends to be either one of the better or one of the worst moves on the board. It's a horrible move if it cannot be defended. HOWEVER, what you can say is that Mogo's playout strategy pushes the search right away in the direction of "finding out for sure" so this appears to cause the playouts to create a hypothesis that is either quickly refuted or quickly confirmed. I really think you want to push towards positions that "work out" what is really going on, even if you have to insert bias into the the playouts to get this (which you probably do.) > > The second observation I think may have been caused by not enough > randomness. But that means I first have to find an answer to how much > randomness I need to put into the patterns. I'm first looking at this > question with some hand-crafted patterns to get a better handle on > this issue. Let us know. The whole issue is pretty interesting. I think randomness is required only to counteract systematic biases because obviously if you playouts played perfectly, there would be no need for randonmess. And yet better than random playouts can also lead to worse play in general. - Don > > Mark > > > On 30-mrt-08, at 09:14, Jacques Basaldúa wrote: > >> Mark Boon wrote: >> >> >> >There are 16 4-distance points, so if you spill ino that by one >> > point you get 315 or a little over 14 million patterns. Multiplied >> > by 3 for every don't-care point within less than 4 distance. Ouch. >> >> True, but the number of patterns is learned automatically. When I >> first learn the 55K+ games, there are so many patterns that I can >> only create a pattern file of less than 2000 games. I create 32 >> such files an call "importance" the number of files in which each >> pattern is found. (a value from 1 to 32). The number of patterns >> are: >> >> # of imp = 32 97132 (97132) >> # of imp = 31 26493 (123625) >> # of imp = 30 21460 (145085) >> # of imp = 29 19335 (164420) >> # of imp = 28 18415 (182835) >> # of imp = 27 18703 (201538) >> # of imp = 26 18619 (220157) >> # of imp = 25 19345 (239502) >> # of imp = 24 20390 (259892) >> # of imp = 23 21611 (281503) >> # of imp = 22 22959 (304462) >> # of imp = 21 24675 (329137) >> # of imp = 20 26808 (355945) >> # of imp = 19 29081 (385026) >> # of imp = 18 31938 (416964) >> # of imp = 17 35319 (452283) >> # of imp = 16 39188 (491471) >> # of imp = 15 43899 (535370) >> # of imp = 14 50391 (585761) >> # of imp = 13 57259 (643020) >> # of imp = 12 67062 (710082) >> # of imp = 11 79013 (789095) >> # of imp = 10 95292 (884387) >> # of imp = 9 117109 (1001496) >> # of imp = 8 147810 (1149306) >> >> Depending on the threshold value used (and also the number >> of times the pattern is seen) I can create databases from about >> 100K patterns to 1M patterns, more than that means including >> patterns that are too seldom, their urgency information won't be >> very accurate either due to the small sample size. >> >> Jacques. >> >> _______________________________________________ >> 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/
