Hello Ray and all: "Euler number" (an ambiguous designation, not recognized by most mathematicians) is easily calculated this way. Let Q1=the number of 2x2 neighborhoods with this configuration: X 0 0 1, and let Q3 be the number of these: X 1 1 0, where X is don't care. Then E=Q1-Q3. The Q's are counted with a raster sweep that moves across and down by one cell, so a given pixel is examined four times. Also E=B-H where B is the number of blobs (connected sets of 1's) and H is the number of holes (connected sets of 0's inside blobs). This formula for E does not treat the following patterns optimally, but it can be improved by making it slightly more complicated. 1 0 0 1 and 0 1 1 0. Holes on the edge can be counted by surrounding the image with a frame of 1's, but separate blobs touching the edge will become connected. It's been 36 years since I published this work (IEEE Trans. Computers, May 1971) so I may not recall everything perfectly. Incidentally, 2x2 neighborhoods are much better for tracing boundaries than 3x3, being faster and less ambiguous in crowded areas. I thought about the Go problem a little but never wrote any code. I'm not sure how much help the Euler number stuff would be. I got to be about low intermediate as a player. Steve Gray Ray Tayek wrote:
steve, hi, someone using your paper on the go list.
dave, my last post to steve went unreplied to, do you have a more recent address? thanks
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 <drdailey@cox.net> 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/
--- vice-chair http://ocjug.org/