Author: Vincent Diepeveen
Date: 17:19:46 01/11/06
Go up one level in this thread
On January 11, 2006 at 09:40:38, Robert Hyatt wrote:
>On January 11, 2006 at 02:14:53, Andrew Wagner wrote:
>
>>This is going to sound like a really odd question. That's because it is. But I
>>really do have a good reason for asking it. Anyway, here goes...
>>
>>Is it feasible to implemet a typical alpha-beta search in an iterative fashion?
>>I'm not talking about iterative deepening, but I want to do alphabeta without
>>any recursion. If it's possible, can you give me a suggestion what it might look
>>like?
>
>
>Yes, but it simply looks ugly.
>
>The idea is that instead of recursive values for alpha/beta/etc, you have arrays
>alpha[n]/beta[n]/etc. And instead of recursively calling search, you add one to
>"ply" and go back to the top. Where you access everything as alpha[ply],
>beta[ply], move_list[ply], etc...
Doh.
>The problem after doing that is that you then have to deal with the "negamax"
>type issue of at each depth, before copying alpha[ply] to alpha[ply-1] (that
>would be backing up the value) you have to negate the value, so that it is
>easier to deal with alpha/beta cutoffs.
>
>I would not do this unless you are dead set on doing a parallel search this way.
> My search is recursive, and my parallel search works just fine, keeping the
>readability of the recursive search. Cray Blitz used the "iterative" type
>search because when it was initially created in the very late 1960's, FORTRAN
>didn't support recursion (recursion was hardly used back then, except maybe in
>Algol/PL-1/etc) so using it wasn't an option... It can be done, but the
>resulting code is much harder to read, and with everything "global" (thanks to
>the big arrays) it is quite easy to introduce bugs that are then difficult to
>find.
In Diep:
typedef struct BlockElt {
struct HashKey hash;
struct Move *volatile movelistend;
..
..
int bestscore;
struct Move SemiLegals[220];
} Recursionblock;
Note i doubt whether Diep sourcecode is less readable than crafty,
for Dutch speaking programmers that is, and apart from fact that it
has worlds largest chess evaluation :)
Note i don't feel that being recursive versus iterative is a major difference.
Bob has the idea that for a parallel search it matters a lot. This shows a
fundamental lack of insight in datastructures and programming. What matters more
is that all variables from 1 position you put in a structure, *that* is very
interesting for a parallel search.
There is even better ways to do it,
but i'll leave it to the reader to figure that out.
Now i have a challenge for Uri Blass; instead of going to ask the question
whether it is clever to have a maximum of 220 semi legal moves, he'll have to
prove the opposite, namely that he can find a position with more than 220 semi
legal moves which could happen in diep's search tree. Diep doesn't search on in
illegal positions.
If there is positions possible with more than 220 semi legal moves, then Diep
will obviously crash. Can Uri Blass find such a position now?
Vincent
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.