[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] A chess programmer at the Go-Olympiad
We can all agree that i am a very poor go player, not worth a 1 Dan level
yet. Not even close.
I'll be fighting Chrilly's FPGA creation at 9x9 and will kick it!
I'm tactical not so bad, considering that i am a titled chess player, for
me a 9x9 go board is like simple tactics in chess. So i won't be making
many tactical mistakes there.
I advice Chrilly to beat within 11 months at home some commercial go
programs when playing 9x9
Programs like many faces are not even close to Dan level at 9x9. I beat
those progs at 9x9 easily (usually a few points difference as i get lost
after a few moves in the opening but i fight back and cut some chains).
I'll be there in Israel july 2004, so i volunteer to give Chrilly's simple
go program a shot.
Note that i doubt he'll get something efficient to work in hardware.
All those extensions you need for ladders and surrounded groups, no way to
do that efficiently in hardware.
Also distributing it over different nodes is going to be a hard task.
Just see my search output at 460 processors when i run it 'distributed'.
Note this is still way more efficient than hardware ever will be.
The first output is the version i played with in the world champs at a very
hard chess position. After 2 hours and a few minutes 17 ply has been
finished and 18 ply is started.
It is using the local hashtable in the qsearch (250MB) and it is using the
global hashtable at all depthlefts >= 1 ply:
Now the normal version, which doesn't store the quiescencesearch but does
store all depths > 0.
00:00 0 0 0 (460) 1 (0,0) 2.119 b4xc5
00:00 0 0 0 (460) 2 (0,0) 2.119 b4xc5 Qc7xc5
00:02 0 0 0 (460) 3 (0,0) 2.237 b4xc5 Ra8-e8 Nc3-e4 Bd6xc5
00:02 0 0 0 (460) 4 (0,0) 2.237 b4xc5 Ra8-e8 Nc3-e4 Bd6xc5
00:40 0 0 0 (460) 5 (0,0) 1.883 b4xc5 Rf8-e8 Nc3-e2 Qc7-a5 c2-c3
00:45 0 0 0 (460) 6 (0,0) 1.846 b4xc5 Ra8-e8 Nc3-e4 Ne7-f5
Nf3-g5 Bd6xc5
00:53 0 0 0 (460) 7 (0,0) 2.406 b4xc5 Rf8-e8 Nc3-e4 Ne7-f5
Nf3-g5 Qc7xc5 c2-c3
00:56 0 0 0 (460) 8 (0,0) 1.739 b4xc5 Rf8-e8 Nc3-e4 Ne7-f5
Nf3-g5 Qc7xc5 Ra1-b1 Nf5-d4
01:07 0 0 0 (460) 9 (0,0) 1.970 b4xc5 Rf8-e8 Nc3-e4 Ne7-f5
Nf3-g5 Qc7xc5 Qd1-d2 Nf5-d4 c2-c3
01:34 563556 53024985 0 (460) 10 (15969,151439) 1.204 b4xc5 Rf8-e8
Nf3-g5 Ne7-f5 Nc3-e4 Bd6xc5 Qd1
-g4 Nf5-d6 Ng5-e6 Re8xe6 d5xe6
depth=10 nps=607055 ttl=72846666 egtb=0 aborted=48692678
(afh=25543,splits=261134) time=120.00s
03:08 758373 142589422 0 (460) 11 (47875,499297) 1.095 b4xc5 Rf8-e8
Nc3-e2 Qc7xc5 c2-c4 Ba6xc4 Ba2
xc4 Qc5xc4 Qd1-d4 Qc4xd5 O-O
depth=11 nps=813654 ttl=182877066 egtb=0 aborted=112295422
(afh=67685,splits=693612) time=224.76s
03:58 908254 216881978 0 (460) 12 (78112,841881) 1.050 b4xc5 Rf8-e8
Nc3-e2 Qc7xc5 c2-c4 Ba6xc4 Ba2
xc4 Qc5xc4 Qd1-d4 Qc4-c2 Qd4-c3 Qc2-e4
depth=12 nps=957532 ttl=386182356 egtb=0 aborted=241106908
(afh=127633,splits=1400567) time=403.31s
09:36 1298189 748172751 0 (460) 13 (245417,2398027) 0.444 b4xc5
Rf8-e8 Nc3-e2 Qc7xc5 c2-c4 Ne7xd5
Qd1-d4 Qc5xd4 Nf3xd4 Nd5-c3 Ke1-f2 Bd6-c5 Kf2-f3
depth=13 nps=3168138 ttl=3095778486 egtb=0 aborted=1759560355
(afh=1258955,splits=8177463) time=977.16s
19:20 3364631 3906067861 0 (460) 14 (1603537,10670458) 0.117 b4xc5
Rf8-e8 Nc3-e2 Qc7xc5 c2-c4 Ne7x
d5 Qd1-d4 Qc5xd4 Nf3xd4 Nd5-c3 a3-a4 f4-f3
50:54 5317603 16243842977 0 (460) 14 (5403791,33550882) 0.212 b4-b5
Ba6-b7 Qd1-d2 Ne7-f5 O-O Nf5-e
3 Rf1-f2 Rf8-e8 Qd2-d4 Ra8-c8 Bc1xe3 f4xe3 Rf2-e2 Nc5-d3
depth=14 nps=5015287 ttl=17096414590 egtb=0 aborted=9662055619
(afh=5723154,splits=36131262) time=3408.86s
01:00:31 5064710 18392394781 0 (460) 15 (6077444,39451488) 0.264
b4-b5 Ba6-b7 Qd1-d2 Ne7-f5 O-O Nf
5-e3 Rf1-f2 f7-f5 Qd2-d4 Ra8-e8 Ba2-c4 Nc5-e4 Bc1xe3 f4xe3 a3-a4
depth=15 nps=4294115 ttl=20628201297 egtb=0 aborted=11380590805
(afh=6773788,splits=45841476) time=4803.83
s
01:31:30 4466087 24521993032 0 (460) 16 (7723311,52786168) 0.160
b4-b5 Ba6-b7 Qd1-d2 Ne7-f5 O-O Nf
5-e3 Rf1-f2 f7-f5 Nf3-g5 Qc7-b6 Qd2-d4 h7-h6 Ng5-e6 Nc5xe6 Qd4xb6 a7xb6
01:37:35 4518356 26456741081 0 (460) 16 (8419398,57816187) 0.165
b4xc5 Rf8-e8 Nc3-e2 Qc7xc5 c2-c4
Ne7xd5 Qd1-d4 Qc5xd4 Nf3xd4 Nd5-c3 Ke1-f1 Nc3xa2 Ra1xa2 Ba6xc4 Nd4-f5 Bc4xa2
depth=16 nps=4454773 ttl=32181820283 egtb=0 aborted=16950269941
(afh=10504865,splits=74699573) time=7224.1
2s
02:22:43 5110928 43766052604 0 (460) 17 (13940238,91131639) 0.609
b4xc5 Rf8-e8 Nc3-e2 Bd6xc5 d5-d6
Bc5xd6 O-O Ne7-f5 Ne2-d4 Qc7-c5 c2-c4 Ra8-d8 Kg1-h1 Bd6-e5 Nf3xe5 Qc5xe5
Qd1-g4
depth=17 nps=4860131 ttl=49287275195 egtb=0 aborted=25516239384
(afh=15928214,splits=109235230) time=10141
.14s
03:22:12 5265541 63882491771 0 (460) 18 (19968586,133598028) 0.466
b4xc5 Rf8-e8 Nc3-e2 Qc7xc5 c2-c
4 Ne7xd5 Qd1-d4 Qc5xd4 Nf3xd4 Nd5-c3 Ke1-f1 Nc3xa2 Ra1xa2 f4-f3 Nd4xf3
Ba6xc4 Ra2-c2 Bc4-d3
depth=18 nps=5272397 ttl=83276304020 egtb=0 aborted=42072953528
(afh=26561999,splits=181805307) time=15794
.77s
05:47:57 5993449 125127338136 0 (460) 19 (37271002,235161437) 0.293
b4xc5 Rf8-e8 Nc3-e2 Bd6xc5 d5-
d6 Bc5xd6 O-O Ne7-f5 Ne2-d4 Nf5xd4 Nf3xd4 Ba6xf1 Kg1xf1 Ra8-d8 Bc1-b2
Bd6xa3 Ba2xf7 Kg8-h8 Ra1xa3
depth=19 nps=6361727 ttl=200869193368 egtb=0 aborted=98884061155
(afh=62657776,splits=376446069) time=3157
4.63s
11:05:57 6941105 277350209487 0 (460) 20 (81637568,463819222) 0.228
b4xc5 Rf8-e8 Nc3-e2 Bd6xc5 d5-
d6 Bc5xd6 O-O Ne7-f5 Ne2-d4 Nf5xd4 Nf3xd4 Ba6xf1 Kg1xf1 Ra8-d8 Ra1-b1
Bd6-c5 c2-c3 Bc5-d6 Qd1-f3 Qc7-e7
The version that can do communication between all processors at 20% of the
total nodes searched (qsearch is 80% of all nodes) is finishing 17 ply and
soon after that starts 18 ply.
Now the same version with 1 modification. It stores in the local hashtable
plydepth left <= 10 and it stores in the global hashtable >= 11 ply.
:00 0 0 0 (460) 1 (0,0) 2.119 b4xc5 Qc7xc5
00:00 0 0 0 (460) 2 (0,0) 2.119 b4xc5 Qc7xc5
00:02 0 0 0 (460) 3 (0,0) 2.237 b4xc5 Ra8-e8 Nc3-e4 Bd6xc5
00:02 0 0 0 (460) 4 (0,0) 2.237 b4xc5 Ra8-e8
00:14 0 0 0 (460) 5 (0,0) 1.883 b4xc5 Rf8-e8 Nc3-e2
00:27 0 0 0 (460) 6 (0,0) 1.846 b4xc5 Ra8-e8
00:36 0 0 0 (460) 7 (0,0) 2.406 b4xc5 Ne7-f5
01:04 0 0 0 (460) 8 (0,0) 1.824 b4xc5 Bd6xc5
03:25 0 0 0 (460) 9 (0,0) 1.970 b4xc5 Rf8-e8 Nc3-e4
08:38 1222567 633607672 0 (460) 10 (148568,1326106) 0.632 b4xc5
Ra8-e8 Nc3-e4
depth=10 nps=1248100 ttl=725720560 egtb=0 aborted=348576875
(afh=194021,splits=1732467) time=581.46s
58:45 1540704 5431214025 0 (460) 11 (889614,7134097) 1.110 b4xc5
Qc7xc5
depth=11 nps=1552287 ttl=5519793255 egtb=0 aborted=2338418994
(afh=940275,splits=7579001) time=3555.91s
01:14:21 1567045 6991421375 0 (460) 12 (1415222,10794611) 1.065 b4xc5
depth=12 nps=1592326 ttl=7402982085 egtb=0 aborted=3454686069
(afh=1595556,splits=12242496) time=4649.16s
02:51:20 1859415 19115107780 0 (460) 13 (2874460,21811050) 0.444 b4xc5
depth=13 nps=2204845 ttl=24139966284 egtb=0 aborted=10848686727
(afh=4834769,splits=32419200) time=10948.60s
So after nearly 3 hours it has the mainline of 13 ply (6.5 moves).
The same time, the normal version searches 17 ply.
So Chrilly can really try hard, but it will be hard to succeed; the
overhead in hardware is just too much and the blessing of shared memory is
really important.
Now imagine how inefficient a search becomes without hashtable :)
Losing 4 ply, or a factor in 19x19 go of 10^4 is just the start then...
At 23:20 3-12-2003 +0100, chrilly wrote:
>>>>
Dear Go programmers Besides playing with me FPGA-chess programm Brutus at
the WC I was operating together with Stefan Mertin GoAhead at the
Computer-Olympiad. The Go-Olympiad was definitely more fun. Not only
because GA became 2nd in 19x19 and Brutus "only" 4th in chess. The
computer chess atmosphere is - at least under the top 4 programmes -
extremly compitetive. GA did not support the Modem-Protocoll. I aggreed
with all other operators, that the internal clock of each programm is the
valid time. This takes away much stress, but it would be completly
impossible in a chess tournament. Everybody would suspect that the other
side cheats on his clock. In the game against NeuroGo GA crashed. I did
not know how to setup the position again. Markus Enzesberger gave me the
position on a floppy, but the computer provided by Siemens had no floppy
drive. The memory stick did not work with Markus Linux. I started to enter
the 200 moves made so far by hand. Having only little Go-experience, this
was a hard job. Martin Mueller saw my problems and took the job over
(enpassant he commented the game and especially NeuroGO´s somewhat
unfortunate moves). Many thanks to Martin for saving the game. One of the
strangest experience was the game against Jimmy. Chess programs react
immediatly, if they are in the book (or have guessed the move correctly).
At first I found the immediate Jimmy-reply natural. After all there should
be also a Go book. But after 30 moves I got suspicious and found the real
reason. Jimmy (or its autor) does not know what to do with time. This is
for a chess programmer a shocking experience. Like every chess programmer
I am a believer in search and I do not really understand why Go programms
do not use it (Martin gave me some good reasons, but the believe is too
deep that one can be converted while drinking one beer). I was therefore
deeply impressed by Aya. It seems to be one of the first real searchers.
GA had not much trouble with Aya on 19x19, but it was helpless against the
7 Ply search in 9x9. The same holds with NeuroGO. On 19x19 it was a
clear-cut win of GA. In 19x19 NeuroGo searches 1 Ply. In 9x9 the 3 Ply
searching NeuroGo was clearly better than GA. The node count of
Go-programs is unbelievable slow. I also thought that the number 620 on
Ayas screen means 620 Kilo-Nodes. But Hiroshi explained me, its nodes. My
impression from looking at the Gnu-Go and the GA code is. It is not only
the complexity of the game. Go programmers obviously do not spend months
to save a few nano-seconds in their time critical parts (maybe because
there is no time critical part). E.g. GA is written in Basic, it also does
not use the time of the opponent for its own calculations. I do not know
of any attempts to parallelize a Go-Programm. It seems to be complicated
enough to get everything right. The 50 Liter beer bet: There are some
plans that I write a 9x9 FPGA Go programm. This is yet not fixed, it
depends on the result of the negotiations with a potential investor (I can
not finance such a project from my own pocket. Especially I would not be
able to produce a few thousand Go-cards). In case I get the project money,
I have made with Martin Müller and Markus Enzesberger the following bet: I
can write a 1-Dan 9x9 Go programm within 1 year. There is a similar bet
with Ingo Althoeffer. I suggest that Ingo organizes a tournament with 11
1-Dan players. I will inform everybody when the contract is signed - or
when it has become clear, that the project does not start due to lack of
money. In case of signing the contract I will accept additional offers to
join the bet (as long as the deposit is reasonable). If you think this
bet is a very save way to get a few bottle of beer, wine, whisky.. etc.
Keep in mind, that this programm will be able to search in the
Mega-Positions/Second range. I do not know if this is enough for playing
at 1-Dan (I do not even know, what it really means to have 1-Dan). But
maybe Hiroshi could make a guess how strong an 1000 times faster Aya would
be. Chrilly Donninger _______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go