For identifying points that look like eyes, it's useful to have a 16-bit value at each position of the board that contains the colors of the 8 neighbors (2 bits per neighbor, with an encoding like 00=empty, 01=black, 10=white, 11=outside). You can maintain this incrementally when a point on the board changes color. Then a single table lookup will tell you if this looks like an eye or not. That should speed up your light playouts considerably.
Other arrays are useful, depending on what kinds of queries you want to make fast. Álvaro. On Wed, Apr 5, 2017 at 10:41 AM, Michail Drozdov <michail.droz...@gmail.com> wrote: > Hello, > I'm trying to write my own go playing program. Right now it is GnuGo style > program - no dedicated search is performed. It is pleasure to see bot > improving, but recently I decided to learn and implement MCTS, meaning I > have to use my go board implementation often (for playouts). > I see some fundamental performance problems, but can't decide if it is > lack of my programming knowledge or need of paradigm shift. I'm having > around 1000 playouts/s with very light playouts (which, as I understand, is > very small number). My playouts consist of selecting all empty fields, > which are not potential eyes of player to move and playing one at random. > Benchmarking shows, that current biggest offender is function, which checks > if field is potential eye, by checking values of color array around point > of interest. > My board implementation is strightforward - one dimensional array of > colors of intersections (black, white, empty or border) and some additional > info like player to move, ko position, etc. Not going into programming part > I would like to ask, if there would be benefit of also having other arrays > for liberties, numbers of neighbours and so on, which I would update > incrementally and then check? Looks like such libraries like Fuego or > libego use this approach. Or I am looking at this problem from wrong side > and need to search for bottlenecks in code itself? Thank you in advance. > > _______________________________________________ > Computer-go mailing list > 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
