Re: [computer-go] FPGA

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

How can you evaluate a go position without doing local search?  The only 
way I can think
of is having a huge pattern database, and that won't fit on an FPGA.  The 
reason go programs
seem slow is that they are doing lots of local search as part of the 
evaluation function.  Even the
most trivial local tactics that any 10 kyu player knows need over 10 ply of 
local search.  It's much
more efficient to ten 10-ply local searches and combine them in an 
evaluation function than to
do one full width 10 ply search, which I think is what you propose.  When 
someone says that their
go program does one play local search, you aren't hearing that within each 
evaluation is many local
searches perhaps 30 ply deep.

If you were talking about making a fast local searcher, to speed up a 
conventional go evaluation by 10x or
100x I would think you have some chance at this bet.  But if you just do a 
single global search I think
there is no chance.  Still, it will be interesting to see how well you 
do.  Global search does avoid the big problem
in go programs that often the best move is pruned and not considered at all.

David Fotland

At 09:31 AM 12/5/2003 +0100, chrilly wrote:
> Dear all,
>
> The speed an FPGA design can run depends on the logical complexity of the 
> design. In Brutus I use the somewhat outdated XiLinx-Virtex-I V1000E.
> Brutus runs with 30 MHz. Not very fast, but it takes only 8-9cycles to 
> evaluate a position. The Go design I have in mind should run - at a faster 
> chip - with about 100MHz. So even if it needs 100 cycles to evaluate a 
> position, it would make 1 MPos/Sec. (My goal is 10-15 cycles).
> The gate count is difficult to say. Nominally the Virtex-I 1000E has 1000 
> KGates. But these are marketing gates. There are much bigger (and faster) 
> FPGAs available. I think the number of gates is no serious restriction any 
> more. Especially the evaluation of Brutus is fairly complex and I use 70% 
> of the Virtex-1000.
> Configuring the Virtex takes for the Alpha-Data ADMXRC-board I am using 
> about 1 second. Theoretically I could switch programms during a game (e.g. 
> by using a special endgame module).
>
> There are other practical problems:
> a) The prices of FPGAs are quite high. An FPGA is not sufficient, you need 
> a board/card too. XiLinx has now a very interesting chip, the Spartan-3. 
> Its build in 90nm technology and it is announced to become very cheap (12$ 
> for 1000 kGates). But currently this is only an announcement. (The whole 
> FPGA business is primarly an announcement business).
> b) For complex designs it takes quite a while till the synthesis 
> (comparable to compiling) is done. On my rather fast PC a full synthesis 
> cycle takes at the moment 2 hours.
> c) The communication between the CPU and the FPGA is done via the PCI-bus. 
> This is a serious bottleneck. There are some designs which interface 
> directly memory mapped, but this is a rather fragile concept. It usually 
> works only for one specific motherboard.
> One consequence of this bottleneck is, that one has to write a full blown 
> FPGA-programm (including search). One can not implement the evaluation or 
> a move generator alone. Calling this evaluation over the bus takes longer 
> than doing it on the PC (at least in chess).
> The new PCI-express standard will improve on this situation.
>
> Last but not least: Hardware design is quite different to software. It 
> takes a very steep learning curve. I needed about 1 year till I mastered 
> the concept. In software there is no notion of time. In Hardware time is 
> extremly important. Every operation must be done at the correct cycle. The 
> order of statements does not matter. As a software programmer one is used, 
> that if one writes first statement A and then B, A will be executed before 
> B. This assumption is in Hardware-programming totally wrong.
>
> Chrilly
>
> _______________________________________________
> 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