[Computer-go] Go playing software accelerator development

Hideki Kato hideki_katoh at ybb.ne.jp
Wed May 22 01:31:14 PDT 2013


Another info for you.

There have been IEICE RECONF DESIGN CONTESTs (for games) held in 
Japan.
http://www.cs.tsukuba.ac.jp/~yoshiki/FPGA/Contest_eng/index.php

The target in 2013 is Blokus Duo, 2011 and 2012 were Connect6, for 
examples.

Hideki

=?koi8-r?B?8s/WxMXT1NfFztPLycog5M3J1NLJyg==?=: <1215021369210705 at web16d.yandex.ru>:
>Thanks a lot for these links. 

>

>Yes, the HW will run at 100-200 MHz. But it is not at all too hard to adapt it: it is 
>programmable logic, and it uses a high-level languages (Verilog derived from C and VHDL 
>derived from ADA). It obviously uses different philosophy, but making changes is as simple as 
>for CPU programs: just change the code and compile.

>

>Dmitry

>

>22.05.2013, 12:01, "Lars Schafers" <slars at upb.de>:

>> Nice to see somebody working on accelerator hardware for Go (again).

>>

>> There actually were some attempts in the past and even publications that

>> might be interesting for you [1][2].

>>

>> I think in principle you have two possible directions when looking at

>> accelerating basic MCTS for Go:

>> a) Accelerating the computation of single playouts

>> b) Computing a large number of playouts in parallel (likely using some

>> pipelining technique)

>>

>> The problem with b) is that N parallel simulations are less valuable

>> then N sequential ones, as simulations in MCTS are guided depending on

>> former simulation outcomes. See e.g. [3] for according experimental

>> results. You would likely end up with something that was called

>> leaf-parallelization [4].

>>

>> a) would be great, but is extremely difficult to achieve. The

>> computation of strong playouts doesn't pose to much points for

>> fine-grained parallelization and kind as well as amount of computations

>> that need to be done for the generation and placement of moves is pretty

>> inhomogeneous. Likely your hardware will run at a speed of about 150 to

>> 200 Mhz (?), making it difficult to achieve a significant speedup over

>> modern CPUs with 8 or more cores each running at more than 3 Ghz.

>>

>> I'm somehow convinced that looking at accelerator hardware for MCTS Go

>> might be a bit to early. The algorithm and heuristics used are still

>> changing a lot from year to year and adapting your HW design is likely

>> more involved than adapting software. But that's just my personal point

>> of view. Good luck!

>>

>> - Lars

>>

>> [1]

>> Gao, Haiying, Wang, Fuming, Lei, Wei, and Lin, Yun: Monte Carlo

>> simulation of 9x9 Go game on FPGA , IEEE International Conference on

>> Intelligent Computing and Intelligent Systems, 865–869, October 2010

>>

>> [2]

>> Koizumi, Kenichi, Inaba, Mary, Hiraki, Kei, Ishii, Yasuo, Miyoshi,

>> Takefumi, and Yoshizoe, Kazuki: Triple Line-Based Playout for Go - An

>> Accelerator for Monte Carlo Go, Proceedings of the 2009 International

>> Conference on Reconfigurable Computing and FPGAs, 161–166, 2009

>>

>> [3]

>> Segal, Richard B.: On the Scalability of Parallel UCT, International

>> Conference on Computer and Games, 36–47, 2010

>>

>> [4]

>> Chaslot, Guillaume M.J-B., Winands, Mark H.M., and van den Herik, H.

>> Jaap: Parallel Monte-Carlo Tree Search, Conference on Computers and

>> Games, 60–71, 2008

>>

>> On Wed, 2013-05-22 at 06:35 +0000, аюцфхёђтхэёъшщ Фьшђ№шщ wrote:

>>

>>>  Incredible, 100 nanoseconds is only about 300 instructions of a CPU.

>>>  Are you talking about 19x19? And 1 microsecond for my design will

>>>  probably be a worst-case (as I calculate freedom and capture

>>>  iteratively). When almost all stones have free places around it will

>>>  be down to ~100 nanoseconds.

>>>  As to the number of possible accelerators on-chip - it varies upon

>>>  price. I think it can be 5-250, for the price $250-$5000. So the cost

>>>  of a single simple accelerator will be $20-$50.

>>>

>>>  Dmitry

>>>

>>>  21.05.2013, 23:13, "Mark Boon" <tesujisoftware at gmail.com>:

>>>>  Sounds interesting. But 1 microsecond for a move is not particularly

>>>>  fast. There are already implementations that do that in the 100-300

>>>>  nanoseconds range on one core. 1 microsecond is probably considered

>>>>  as 'semi-light' playout. I suppose the question then becomes, how

>>>>  many of these could your accelerator do in parallel?

>>>>

>>>>  Mark

>>>>

>>>>  On Tue, May 21, 2013 at 8:06 AM, Alexander Kozlovsky

>>>>  <alexander.kozlovsky at gmail.com> wrote:

>>>>          п ђюцх ъёђрђш шч ЫШРЯр, ё їхђтх№ђюую єръѓыќђхђр, ьюцхђ ш

>>>>          ях№хёхърышёќ :)

>>>>

>>>>          On Tue, May 21, 2013 at 7:02 PM, аюцфхёђтхэёъшщ Фьшђ№шщ

>>>>          <divx4log at yandex.ru> wrote:

>>>>                  Hi all,

>>>>

>>>>                  I have got an idea to create a hardware accelerator

>>>>                  for Go playing software. It will probably be a USB

>>>>                  (or maybe PCI-Express) device that will be able to

>>>>                  do some basic, but very time-consuming for

>>>>                  general-purpose CPU calculations very fast. For

>>>>                  example load a goban layout, make a number of random

>>>>                  moves (as used in Monte-Carlo algorithm) and unload

>>>>                  result back to a computer.

>>>>

>>>>                  As long as it will be a hardware, it will be able to

>>>>                  do specified calculations only, but the speed will

>>>>                  be very high. For example, making just a copy of the

>>>>                  particular goban layout will require typically about

>>>>                  10 nanoseconds only (one internal clock cycle).

>>>>                  Calculation of the validity and results of a

>>>>                  particular move (including a check for ko and

>>>>                  captured stones) will probably take 1 microsecond.

>>>>                  This as usual may vary during debugging, but the

>>>>                  current move calculation engine draft I've started

>>>>                  to develop is about this figures.

>>>>

>>>>                  My nearest aims here are:

>>>>                  - to understand a demand from go playing software

>>>>                  developers, and

>>>>                  - to understand what particular calculation chains

>>>>                  are most demanded for hardware acceleration.

>>>>

>>>>                  Dmitry

>>>>                  _______________________________________________

>>>>                  Computer-go mailing list

>>>>                  Computer-go at dvandva.org

>>>>                  http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

>>>>

>>>>          _______________________________________________

>>>>          Computer-go mailing list

>>>>          Computer-go at dvandva.org

>>>>          http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

>>>>  ,

>>>>

>>>>  _______________________________________________

>>>>  Computer-go mailing list

>>>>  Computer-go at dvandva.org

>>>>  http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

>>

>> --

>> Lars Schaefers

>> Computer Engineering Group of Prof. Dr. Marco Platzner

>> Paderborn Center for Parallel Computing, University of Paderborn

>> Pohlweg 47-49, 33098 Paderborn, Germany

>> Tel: +49 (0)5251 60 4341, Fax: +49 (0)5251 60 5377

>> Office: Building O 3.119

>>

>> _______________________________________________

>> Computer-go mailing list

>> Computer-go at dvandva.org

>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

>_______________________________________________

>Computer-go mailing list

>Computer-go at dvandva.org

>http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
-- 
Hideki Kato <mailto:hideki_katoh at ybb.ne.jp>



More information about the Computer-go mailing list