Re: FYI & my annoyment

[Christian Bauer <Christian.Bauer@xxxxxx>]

Hello Xu (is Xu your Firstname, or is it Mousheng??)

I did the same as you for the 2x2, 3x3 and 4x4 board. But its about 2 years ago and I
can't tell you, which computer I has used. (Maybe a Pentium I, 90 MHz, or something like
that.) I used C++ for my program.

2x2 took some seconds
3x3 tooks very long, but it finished (after some hours?)
4x4 tooks much longer (some days, as I remember well)

But I must tell you, that I only generated the primitive game tree, but checked no go
specific things, in my program. I did not check if some stones could be captured, for
example. My program should give me only a first idea, how fast such small boards could
be evaluated.

In the first version, I had screen-output (with printf()) during the tree-generation,
but I could not wait for the end of the 3x3, so I removed the output (and stored all
information only on memory and/or disc); this makes it much faster.
I also used the sysmetry of the board. That means, I checked every position on all kinds
of symetry, which are possible on a go bord:
x-axis symetry
y-axis symetry
xy-axis symetry
left diagonal symetry
right diagonal symetry
left/right diagonal symetry
xy-axis and left/right diagonal symetry
180 degree rotation symetry
90 degree rotation symetry

Symetric positions occour very often on small go boards, so it brings much more time for
tree restriction, compared with the time of the symetry tests. There are also many ways
of checking this symetry - it could be done very fast, if you do it clever. Of cause,
testing board symetry is a useless overhead on a 19x19 board; but I'm shure that it is a
good deal at least up to the 5x5 board.

As I checked the symetry, the tree grows much slower than (n x n)!, but it's very hard
to say how much slower. It was not possible for me, to wait until the 5x5 has finished.

If you have some questions on the symetry check, ask me.

Good luck with your algorithm,

    Christian Bauer


======================================================
Mousheng Xu wrote:

> Ladies & Gentlemen,
>
>         Just give you some impression how powerless a computer is at computing.
>         I did an exhausted tree build/search on a 2 x 2 board, it takes several
> seconds. Well, that's not bad. While I tried a 3 x 3 board, it didn't
> finish in 2 hours and I killed it. :) Man, 3 x 3 ! I had planned for a 9 x
> 9 ! :)
>         From 2 x 2 to 3 x 3, it's from 4! to 9!. 9!/4! = 15120. It grows VERY
> FAST. I know I could reduce the calculation by 2^n, but even a 4 x 4
> calculation is still ambitious.
>         Pruning has to be taken if you want to handle 19 x 19. Is that clear now? :)
>
>         The problem then is how to prune? This question can be divided into
> multiple sub questions:
>         1. what do you use for pruning? 1) patterns; 2) go knowledge & theories.
>         2. when or where do you want pruning? While you try to get candidates of
> moves? While you do calculation? Or while you evaluate the strength of a
> group? Or while you estimate the value of a group? It seems you need
> patterns & go knowledge every where. I am still trying to get a cleaner
> solution other than messing up patterns & go theories here & there -- maybe
> I will have to?
>         BTW, what pattern bases are publically available now?
>
>         Thanks a lot.
>
> Mousheng Xu
> -- an ox is slow, but the earth is patient
>
>
>
>