Re: [computer-go] euler numbers
On Nov 27, 2007 1:58 PM, Stuart A. Yeates [EMAIL PROTECTED] wrote: Could you give us a quick reference for exactly _which_ Euler numbers you're using? Wikipedia has three separate ones and the MathWorld site a similiar number. I cannot speak for Don, but in the work on solving Go I calculated the zeros-joined Euler number from independent bitmaps for Black and White with the border set to zero. IIRC half-joined and ones-joined performed worse (in the sense that the tree got bigger). An interesting alternative may be to combine colours so that the quad-counts directly use all the local information (that way, e.g., the diagonal miai-connection can be distinguished from one where the opponent is interfering). Back in 2002 I did not use this because the binary version has a smaller lookup table. The ICGA article contains a bit less information than my thesis. E.g., an explanation of the Euler numbers can be found on page 28 of the thesis. Here's a link: http://erikvanderwerf.tengen.nl/publications.html Erik On 26/11/2007, Don Dailey [EMAIL PROTECTED] wrote: After reading the paper on solving go on small boards, I am curious about the use of euler numbers as a simple evaluation element. I implemented a little euler number test program and it works correctly from a sample of about 50 positions of various types. I'm using the fast version where you scan 2 lines at a time with a lookup table. However, it calculates holes inside of groups and this does not detect eyes or holes on the edges of the board.It's not clear how to deal with this. I'm experimenting with a version that wraps a border around the whole board so that even the empty position looks like a 1 group with one big hole.This causes a lot of silly anomalies - for instance if you surround a big chunk of safe opponent stones it looks like a big hole.If you own half the board and the opponent owns the other half, his half contributes favorably to your euler number (it looks like a big hole of yours.) Of course I realize that this is just a quick and dirty calculation but I was curious about any tricks that others use to deal with it. - Don ___ 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/
Re: [computer-go] euler numbers
Could you give us a quick reference for exactly _which_ Euler numbers you're using? Wikipedia has three separate ones and the MathWorld site a similiar number. Maybe I'm just being stupid. cheers stuart On 26/11/2007, Don Dailey [EMAIL PROTECTED] wrote: After reading the paper on solving go on small boards, I am curious about the use of euler numbers as a simple evaluation element. I implemented a little euler number test program and it works correctly from a sample of about 50 positions of various types. I'm using the fast version where you scan 2 lines at a time with a lookup table. However, it calculates holes inside of groups and this does not detect eyes or holes on the edges of the board.It's not clear how to deal with this. I'm experimenting with a version that wraps a border around the whole board so that even the empty position looks like a 1 group with one big hole.This causes a lot of silly anomalies - for instance if you surround a big chunk of safe opponent stones it looks like a big hole.If you own half the board and the opponent owns the other half, his half contributes favorably to your euler number (it looks like a big hole of yours.) Of course I realize that this is just a quick and dirty calculation but I was curious about any tricks that others use to deal with it. - Don ___ 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] euler numbers
Stuart, Here is the deal on euler numbers and implementations: It's difficult to find any articles on the web that you don't have to pay for.So it was difficult for me to implement this. I resorted to scanned texts of the images that I found after a lot of work - then you have to work your way through the papers - which are designed more for academic style than understandability but I eventually ended up with an implementation. The basic idea of euler numbers is that a 2 dimensional bit map can be analyzed to determine the number of objects and number of holes in the object.The euler number is the number of objects minus the number of holes (and can be negative.) If you can figure out how, there is a way to calculate this number very efficiently. After a lot of pain and agony I eventually figured out how. In my implementation an object is connected groups of stones. A stone is connected to another stone even on the diagonals, although you can use other definitions of connectivity.A hole is exactly what you think it is in GO, a connected set of empty points (and diagonals are not counted in this case.) In image processing, this is the most visually intuitive definition. The object is connected groups of printed pixels on a white piece of paper and the holes are the white background showing through. Visually we see diagonally connected pixels as part of the same object.And that probably works best in Go too when used as an element in an evaluation function. I believe the canonical text on the subject is a paper by Stephen B. Gray called Local Properties of Binary Images in Two dimensions. I eventually found a copy of this paper on the web that you don't have to pay for - it looks like a scanned image of it. It was even harder for me to figure out how to implement this efficiently using scan lines. It's mentioned on the web in several places, but there is no freely available code and no clearly available explanation that I could find.Perhaps I just missed it. - Don Stuart A. Yeates wrote: Could you give us a quick reference for exactly _which_ Euler numbers you're using? Wikipedia has three separate ones and the MathWorld site a similiar number. Maybe I'm just being stupid. cheers stuart On 26/11/2007, Don Dailey [EMAIL PROTECTED] wrote: After reading the paper on solving go on small boards, I am curious about the use of euler numbers as a simple evaluation element. I implemented a little euler number test program and it works correctly from a sample of about 50 positions of various types. I'm using the fast version where you scan 2 lines at a time with a lookup table. However, it calculates holes inside of groups and this does not detect eyes or holes on the edges of the board.It's not clear how to deal with this. I'm experimenting with a version that wraps a border around the whole board so that even the empty position looks like a 1 group with one big hole.This causes a lot of silly anomalies - for instance if you surround a big chunk of safe opponent stones it looks like a big hole.If you own half the board and the opponent owns the other half, his half contributes favorably to your euler number (it looks like a big hole of yours.) Of course I realize that this is just a quick and dirty calculation but I was curious about any tricks that others use to deal with it. - Don ___ 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/
Re: [computer-go] euler numbers
There was a thread on this list, started by Chrilly, around 30 Mar 2006: http://computer-go.org/pipermail/computer-go/2006-March/005127.html Note: there is an error in the 16-element table, corrected later in the thread. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] euler numbers
Don Dailey wrote: Stuart, Here is the deal on euler numbers and implementations: It's difficult to find any articles on the web that you don't have to pay for. Hi, I remember I read a description by Mark Winands long ago: http://www.cs.unimaas.nl/m.winands/documents/The_Quad_Heuristic_in_Lines_of_Action.pdf Euler numbers were mentioned here one year ago: http://computer-go.org/pipermail/computer-go/2006-April/005231.html Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] euler numbers
In message [EMAIL PROTECTED], Don Dailey [EMAIL PROTECTED] writes Stuart, Here is the deal on euler numbers and implementations: It's difficult to find any articles on the web that you don't have to pay for.So it was difficult for me to implement this. I resorted to scanned texts of the images that I found after a lot of work - then you have to work your way through the papers - which are designed more for academic style than understandability but I eventually ended up with an implementation. The basic idea of euler numbers is that a 2 dimensional bit map can be analyzed to determine the number of objects and number of holes in the object.The euler number is the number of objects minus the number of holes (and can be negative.) If you can figure out how, there is a way to calculate this number very efficiently. After a lot of pain and agony I eventually figured out how. If you take a polyhedron, and calculate (faces + vertices - edges), you get what is called its Euler number. For example, the Euler number of a cube is 6+8-12 = 2. Indeed, for any normal polyhedron, the Euler number is 2. This is because normal polyhedra, like the cube and the dodecahedron, are topologically equivalent to spheres, and the Euler characteristic of a sphere is 2. Other 2-manifolds have other Euler characteristics - that of the torus is 0, and that of the double-torus (with two holes) is -2. I am unsure whether this has anything to do with what you are calling Euler numbers. Nick In my implementation an object is connected groups of stones. A stone is connected to another stone even on the diagonals, although you can use other definitions of connectivity.A hole is exactly what you think it is in GO, a connected set of empty points (and diagonals are not counted in this case.) In image processing, this is the most visually intuitive definition. The object is connected groups of printed pixels on a white piece of paper and the holes are the white background showing through. Visually we see diagonally connected pixels as part of the same object.And that probably works best in Go too when used as an element in an evaluation function. I believe the canonical text on the subject is a paper by Stephen B. Gray called Local Properties of Binary Images in Two dimensions. I eventually found a copy of this paper on the web that you don't have to pay for - it looks like a scanned image of it. It was even harder for me to figure out how to implement this efficiently using scan lines. It's mentioned on the web in several places, but there is no freely available code and no clearly available explanation that I could find.Perhaps I just missed it. - Don Stuart A. Yeates wrote: Could you give us a quick reference for exactly _which_ Euler numbers you're using? Wikipedia has three separate ones and the MathWorld site a similiar number. Maybe I'm just being stupid. cheers stuart On 26/11/2007, Don Dailey [EMAIL PROTECTED] wrote: After reading the paper on solving go on small boards, I am curious about the use of euler numbers as a simple evaluation element. I implemented a little euler number test program and it works correctly from a sample of about 50 positions of various types. I'm using the fast version where you scan 2 lines at a time with a lookup table. However, it calculates holes inside of groups and this does not detect eyes or holes on the edges of the board.It's not clear how to deal with this. I'm experimenting with a version that wraps a border around the whole board so that even the empty position looks like a 1 group with one big hole.This causes a lot of silly anomalies - for instance if you surround a big chunk of safe opponent stones it looks like a big hole.If you own half the board and the opponent owns the other half, his half contributes favorably to your euler number (it looks like a big hole of yours.) Of course I realize that this is just a quick and dirty calculation but I was curious about any tricks that others use to deal with it. - Don ___ 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/ -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] euler numbers
After reading the paper on solving go on small boards, I am curious about the use of euler numbers as a simple evaluation element. I implemented a little euler number test program and it works correctly from a sample of about 50 positions of various types. I'm using the fast version where you scan 2 lines at a time with a lookup table. However, it calculates holes inside of groups and this does not detect eyes or holes on the edges of the board.It's not clear how to deal with this. I'm experimenting with a version that wraps a border around the whole board so that even the empty position looks like a 1 group with one big hole.This causes a lot of silly anomalies - for instance if you surround a big chunk of safe opponent stones it looks like a big hole.If you own half the board and the opponent owns the other half, his half contributes favorably to your euler number (it looks like a big hole of yours.) Of course I realize that this is just a quick and dirty calculation but I was curious about any tricks that others use to deal with it. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
