Adding patterns is very cheap: encode the patterns as an if/else tree, and it is O(log n) to match.
Pattern matching as such did not show up as a significant component of Pebbles. But that is mostly because all of the machinery that makes pattern-matching cheap (incremental updating of 3x3 neighborhoods, and related tricks) was a large component. But I think that is the basic idea: pre-compute or incrementally compute some basic functions of the board position so that pattern matching is cheap. Then add as many patterns as possible. From: Computer-go [mailto:computer-go-boun...@computer-go.org] On Behalf Of Jim O'Flaherty Sent: Monday, April 17, 2017 7:05 AM To: computer-go@computer-go.org Subject: Re: [Computer-go] Patterns and bad shape It seems chasing down good moves for bad shapes would be an explosion of "exception cases", like combinatorially huge. So, while you would be saving some branching in the search space, you would be ballooning up the number of patterns for which to scan by orders of magnitude. Wouldn't it be preferable to just have the AI continue to make the better move emergently and generally from probabilities around win placements as opposed to what appears to be a focus on one type of local optima? On Mon, Apr 17, 2017 at 5:07 AM, lemonsqueeze <lemonsque...@free.fr <mailto:lemonsque...@free.fr> > wrote: Hi, I'm sure the topic must have come up before but i can't seem to find it right now, i'd appreciate if someone can point me in the right direction. I'm looking into MM, LFR and similar cpu-based pattern approaches for generating priors, and was wondering about basic bad shape: Let's say we use 6d games for training. The system becomes pretty good at predicting 6d moves by learning patterns associated with the kind of moves 6d players make. However it seems it doesn't learn to punish basic mistakes effectively (say double ataris, shapes with obvious defects ...) because they almost never show up in 6d games =) They show up in the search tree though and without good answer search might take a long time to realize these moves don't work. Maybe I missed some later paper / development but basically, Wouldn't it make sense to also train on good answers to bad moves ? (maybe harvesting them from the search tree or something like that) I'm thinking about basic situations like this which patterns should be able to recognize: A B C D E F G H J K L M N O P Q R S T +---------------------------------------+ 19 | . . . . . . . . . . . . . . . . . . . | 18 | . . . O O . O . . . . . . . . . . . . | 17 | . . X . X O . X O . . . . . . . . . . | 16 | . . X . X O . O O . . . . . . X . . . | 15 | . . . . . X X X X . . . . . . . . . . | 14 | . . X . . . . . . . . . . . . . . . . | 13 | . O . . . . . . . . . . . . X . O . . | 12 | . . O . . . . . . . . . . . . . O . . | 11 | . . O X . . . . . . . . . . . X . . . | 10 | . . O X . . . . . . . . . . . X O . . | 9 | . . O X . . . X . . . X O . . X O . . | 8 | . . O X . . . O X X X O X)X X O O . . | 7 | . O X . . . . . O O X O . X O O . . . | 6 | O X X . X X X O . . O . . . X O X . . | 5 | . O O . . O X . . . . . O . . . . . . | 4 | . X O O O O X . . . O . . O . O . . . | 3 | . X X X X O . . X . X X . . . . . . . | 2 | . . . . X O . . . . . . O . . . . . . | 1 | . . . . . . . . . . . . . . . . . . . | +---------------------------------------+ Patterns probably never see this during training and miss W L9, For example : In Remi's CrazyPatterns.exe L9 comes in 4th position: [ M10 N10 O6 L9 ... With Pachi's large patterns it's 8th: [ G8 M10 G9 O17 N10 O6 J4 L9 ... Cheers, Matt ---- MM: Computing Elo Ratings of Move Patterns in the Game of Go https://www.remi-coulom.fr/Amsterdam2007/ LFR: Move Prediction in Go – Modelling Feature Interactions Using Latent Factors https://www.ismll.uni-hildesheim.de/pub/pdfs/wistuba_et_al_KI_2013.pdf _______________________________________________ Computer-go mailing list Computer-go@computer-go.org <mailto:Computer-go@computer-go.org> http://computer-go.org/mailman/listinfo/computer-go
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
