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/
