Re: computer-go: FPGA

[Vincent Diepeveen <diep@xxxxxxxxx>]

Exactly,

for nodes a seconds nothing beats minimax then.
for search depth nothing beats selectivity. In chess
the nullmove gets applied bigtime, basically this was the big progress
in the 90s in computerchess. Last few years progress is realizing
that knowledge and good preparing like books, a good endgame (that
would be a good openingsplay in GO) is deciding the game.

So in contradiction to common believe: the nullmove selectivity sure
isn't a brute force way of searching. When using nullmove with a 
Go program you also search a lot of plies extra, as it has the habit
to cutoff lines bigtime. Especially for got it will kick butt. Note
there must be a lot of other work to limit the branching factor in
the openings stage, but it's already a cool form of selectivity which
with increasing computing power will kick more and more butt.




At 11:49 AM 8/31/00 -0400, you wrote:
>
>   X-Sender: diep@xxxxxxxxxxxxxxxxx
>   X-Mailer: Windows Eudora Pro Version 3.0 (32)
>   Date: Thu, 31 Aug 2000 15:57:40 +0100
>   From: Vincent Diepeveen <diep@xxxxxxxxxxxxxxxxx>
>   Mime-Version: 1.0
>   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
>   Precedence: bulk
>   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
>   Content-Type: text/plain; charset="us-ascii"
>   Content-Length: 1342
>
>   At 02:18 PM 8/31/00 CEST, you wrote:
>   >Hi!
>   >
>   >>Some of the early work on AI algorithm development for chess was 
>   >>interesting.
>   >>That was when computers were too slow to do a brute-force, iterative 
>   >>deepening
>   >>search.  If Go succumbs to a brute-force, iterative deepening search,
then
>   >>it would seem that only imperfect information games can be used for AI
>   >>algorithm development.  That will eliminate all "typical 2 player
game(s) 
>   >>we
>   >>are used to playing."  Heavy sigh.
>   >
>   >Why such a sad conclusion? It would still be a challenge to write a
program 
>   >that plays well WITHOUT brute-force search (especially since as you say, 
>   >humans don't use that method). Moreover, such an intelligent program
should 
>   >be definitely faster than a brute-force one (on the same hardware) - and 
>   >thus better!
>
>   The conclusion sounds weird to me: why would something more selective
>   be faster? For brute force you don't lose speed. You do everything.
>   When being selective 
>     a) you lose speed to the selection
>     b) smaller branching factor ==> more speed loss (partly result of a)
>
>   >regards,
>   >Vlad
>
>
>
>I  think the  terminology  confuses us.   What  do we   really mean by
>"Faster"?  If  this is a pure "nodes  per second" notion then  I agree
>with Vincent, more AI in general will mean slower.
>
>Maybe you mean deeper?  A selective search is supposed to "simulate" a
>brute force search and in that abstract sense is "faster."
>
>By the way, there  were some  interesting  ideas before  computers got
>faster, but most of them we either useless, or not very well developed
>(and now have been dropped).  
>
>Actually, the statment that computers were  too slow to do brute-force
>iterative  deepening  searches is  not really   true!  However it  was
>BELIEVED at the time to be true.  The only method that had much chance
>of success  back then was a full  width iterative deepening search and
>it worked quite  well to everyones surprise.  If   I could go  back in
>time and write a program to run on a  2 MHZ computer, I could probably
>extract a small benefit  from selectivity, but it  would  be a  lot of
>work  for little gain.   Selective    search  seems to  benefit   with
>increasing depth.  And as Vincent says,  it takes more computing power
>to make well informed decisions about when to cutoff a line.
>
>Don
>
>
>