Re: [Computer-go] Beginner question : how to choose a board, representation
Thanks for all advices ! I have a lot of informations to start :-) I hope I'll be back soon with some code to show ! Jean-Francois > There isn't a lot of info on this[1], so it will probably be a hard > journey for a fast representation. But the things a Go board > representation usually focus on are > > 1. simulating play and then undoing (or telling what happens after a > play: liberties left, stone captures) > 2. fast pattern hashing > 3. ascertaining qualities of groups of stones, safety, neighbors, etc > > The need for these things makes itself apparent little by little. > > Pachi has its state representation commented a lot, maybe even too much: > https://github.com/pasky/pachi/blob/master/board.h > > I think the starting point of any representation is that a single point > is needed for testing ko. :-) > > [1] Some actual examples: > Emil H.J. Nijhuis's thesis, "Learning Patterns in the Game of Go" > Martin Müller, "Computer Go" (2002) > https://www.gnu.org/software/gnugo/gnugo_17.html > https://www.gnu.org/software/gnugo/gnugo_15.html > > Gonçalo ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Beginner question : how to choose a board representation
Look at: https://github.com/lukaszlew/libego it is a much better start than Fuego. Fuego is a fine program if you are an expert C++ programmer, but is a pretty big package to understand well if you wish to do so quickly. Libego is much easier to understand and is also sometimes very clever. Cheers, David G Doshay ddos...@mac.com > On 10, Apr 2016, at 12:19 AM, Jean-Francois Romangwrote: > > Hello to everyone ; I'm a newcomer in this list and computer go programming. > I have a chess programming background, but I want to start something new. :-) > I'm currently in the early phases of developing GTP compatible go engine ; > now it's time for me to choose a board representation : are there some > articles or tips on this ? > Thanks, > Jean-Francois > ___ > 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
Re: [Computer-go] Beginner question : how to choose a board representation
Hi! On Sun, Apr 10, 2016 at 09:19:17AM +0200, Jean-Francois Romang wrote: > Hello to everyone ; I'm a newcomer in this list and computer go programming. > I have a chess programming background, but I want to start something new. > :-) > I'm currently in the early phases of developing GTP compatible go engine ; > now it's time for me to choose a board representation : are there some > articles or tips on this ? I agree with the advice that it's not worth overthinking too much. You will likely be interacting with your board through a set of methods anyway, so you can always optimize the backend easily. For example, some more optimized board representations use union-find chain representation to be able to quickly join stone chains; but I'm not sure if any of the higher level programs actually bothered to do it. I'd also recommend that you do not overoptimize your board representation for a simple Go engine - you may squeeze out a lot of performance from your board representation, but then suddenly you realize that for a more sophisticated Go-playing you also need to quickly find out say the number of liberties of your group (or find the actual liberties efficiently) - and at that moment, a lot of your earlier tricks become quite worthless. -- Petr Baudis If you have good ideas, good data and fast computers, you can do almost anything. -- Geoffrey Hinton ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Beginner question : how to choose a board representation
What programming language and OS environment have you chosen? On Apr 10, 2016 2:19 AM, "Jean-Francois Romang"wrote: > Hello to everyone ; I'm a newcomer in this list and computer go > programming. I have a chess programming background, but I want to start > something new. :-) > I'm currently in the early phases of developing GTP compatible go engine ; > now it's time for me to choose a board representation : are there some > articles or tips on this ? > Thanks, > Jean-Francois > ___ > 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
Re: [Computer-go] Beginner question : how to choose a board representation
On 4/10/2016 12:19 AM, Jean-Francois Romang wrote: Hello to everyone ; I'm a newcomer in this list and computer go programming. I have a chess programming background, but I want to start something new. :-) I'm currently in the early phases of developing GTP compatible go engine ; now it's time for me to choose a board representation : are there some articles or tips on this ? i've only fooled around with this a /little/, bit at the lowest level, but i would start with something like below. i suspect there is a lot more stuff that can be precalculated for a particular board size. thanks public class Go { enum Color { black,white,vacant,edge; // edge can be useful } enum Direction { n,s,e,w,ne,nw,se,sw } class Neighbors { Neighbors(int width,int depth) { this.width=width; this.depth=depth; this.size=(width+2)*(depth+2); n=new int[size]; s=new int[size]; e=new int[size]; w=new int[size]; ne=new int[size]; nw=new int[size]; se=new int[size]; sw=new int[size]; // lots more init required, but it this is constant for any width and depth } final int width,depth,size; int[] n,s,e,w,ne,nw,se,sw; // index of neighbor } class Board { Board(Neighbors neighbors) { this.neighbors=neighbors; colors=new Color[neighbors.size]; } final Color[] colors; final Neighbors neighbors; } } -- Honesty is a very expensive gift. So, don't expect it from cheap people - Warren Buffett http://tayek.com/ ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Beginner question : how to choose a board representation
Hi, I also did computer chess before go (and checkers before chess). I would start with a straight-forward implementation and learn with it. If you end up finding your board representation limiting, rewrite it. Here's some code from my program: int const N = 19; int const XN = N + 2; int const XN2 = XN * XN; enum class Color : char { Empty, Black, White, Outside }; inline bool is_occupied(Color c) { return c == Color::Black || c == Color::White; } inline Color enemy(Color c) { return c == Color::Black ? Color::White : c == Color::White ? Color::Black : Color::Empty; } struct Board { Color array[XN2]; int chain_id[XN2]; int chain_size[XN2]; int chain_liberties[XN2]; int next_in_chain[XN2]; int age[XN2]; [...] On Sun, Apr 10, 2016 at 3:19 AM, Jean-Francois Romangwrote: > Hello to everyone ; I'm a newcomer in this list and computer go > programming. I have a chess programming background, but I want to start > something new. :-) > I'm currently in the early phases of developing GTP compatible go engine ; > now it's time for me to choose a board representation : are there some > articles or tips on this ? > Thanks, > Jean-Francois > ___ > 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
Re: [Computer-go] Beginner question : how to choose a board representation
Jean-Francois Romang wrote " I want to start something new. :-)" do you mean an engine new to Go programming, or just something new to you? if the latter, you could copy and paste a published algorithm or recode alphago which is fully described by its Nature paper. that would be like reinventing the steam engine or colouring in a paint-by-numbers picture; it will keep you busy and you would doubtless learn a lot about programming in the process, but it won't be anything new. but if the former, you could consider starting to build a new kind of engine that works using a truly new method, such as the one i have described in earlier postings to this list, or (much easier) writing a few lines of interface code to get NAO to play Go. either way, i venture to suggest that a fine detail like a board representation is just about the last thing you should worry about, unless you plan to build your engine by a process of trial and error without first thinking through how it's going to work. ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Beginner question : how to choose a board representation
There are several open source go programs. I would start by investigating Fuego and Pachi code 2016-04-10 11:34 GMT+03:00 Gonçalo Mendes Ferreira: > There isn't a lot of info on this[1], so it will probably be a hard > journey for a fast representation. But the things a Go board > representation usually focus on are > > 1. simulating play and then undoing (or telling what happens after a > play: liberties left, stone captures) > 2. fast pattern hashing > 3. ascertaining qualities of groups of stones, safety, neighbors, etc > > The need for these things makes itself apparent little by little. > > Pachi has its state representation commented a lot, maybe even too much: > https://github.com/pasky/pachi/blob/master/board.h > > I think the starting point of any representation is that a single point > is needed for testing ko. :-) > > [1] Some actual examples: > Emil H.J. Nijhuis's thesis, "Learning Patterns in the Game of Go" > Martin Müller, "Computer Go" (2002) > https://www.gnu.org/software/gnugo/gnugo_17.html > https://www.gnu.org/software/gnugo/gnugo_15.html > > Gonçalo > > > On 10/04/2016 09:00, Oliver Lewis wrote: > > There's a discussion of some of the issues in Petr Baudis' PhD thesis: > > http://pachi.or.cz/ > > > > > > > > On Sun, Apr 10, 2016 at 9:19 AM, Jean-Francois Romang > > > wrote: > > > >> Hello to everyone ; I'm a newcomer in this list and computer go > >> programming. I have a chess programming background, but I want to start > >> something new. :-) > >> I'm currently in the early phases of developing GTP compatible go > engine ; > >> now it's time for me to choose a board representation : are there some > >> articles or tips on this ? > >> Thanks, > >> Jean-Francois > >> ___ > >> 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 > > > ___ > 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
Re: [Computer-go] Beginner question : how to choose a board representation
There isn't a lot of info on this[1], so it will probably be a hard journey for a fast representation. But the things a Go board representation usually focus on are 1. simulating play and then undoing (or telling what happens after a play: liberties left, stone captures) 2. fast pattern hashing 3. ascertaining qualities of groups of stones, safety, neighbors, etc The need for these things makes itself apparent little by little. Pachi has its state representation commented a lot, maybe even too much: https://github.com/pasky/pachi/blob/master/board.h I think the starting point of any representation is that a single point is needed for testing ko. :-) [1] Some actual examples: Emil H.J. Nijhuis's thesis, "Learning Patterns in the Game of Go" Martin Müller, "Computer Go" (2002) https://www.gnu.org/software/gnugo/gnugo_17.html https://www.gnu.org/software/gnugo/gnugo_15.html Gonçalo On 10/04/2016 09:00, Oliver Lewis wrote: > There's a discussion of some of the issues in Petr Baudis' PhD thesis: > http://pachi.or.cz/ > > > > On Sun, Apr 10, 2016 at 9:19 AM, Jean-Francois Romang> wrote: > >> Hello to everyone ; I'm a newcomer in this list and computer go >> programming. I have a chess programming background, but I want to start >> something new. :-) >> I'm currently in the early phases of developing GTP compatible go engine ; >> now it's time for me to choose a board representation : are there some >> articles or tips on this ? >> Thanks, >> Jean-Francois >> ___ >> 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 > ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Beginner question : how to choose a board representation
There's a discussion of some of the issues in Petr Baudis' PhD thesis: http://pachi.or.cz/ On Sun, Apr 10, 2016 at 9:19 AM, Jean-Francois Romangwrote: > Hello to everyone ; I'm a newcomer in this list and computer go > programming. I have a chess programming background, but I want to start > something new. :-) > I'm currently in the early phases of developing GTP compatible go engine ; > now it's time for me to choose a board representation : are there some > articles or tips on this ? > Thanks, > Jean-Francois > ___ > 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
[Computer-go] Beginner question : how to choose a board representation
Hello to everyone ; I'm a newcomer in this list and computer go programming. I have a chess programming background, but I want to start something new. :-) I'm currently in the early phases of developing GTP compatible go engine ; now it's time for me to choose a board representation : are there some articles or tips on this ? Thanks, Jean-Francois ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go