Author: Robert Hyatt
Date: 19:39:12 01/12/06
Go up one level in this thread
On January 11, 2006 at 20:19:46, Vincent Diepeveen wrote:
>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;
>
what does that have to do with backing up values, etc? defining a typedef
doesn't reserve anything. I assume you have an array of those. Just as I
indicated...
>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 :)
So? The Titanic was the world's largest ship. We all know how well that
"world's largest" worked, right?
>
>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.
Pretty funny. I did it iterative in Cray Blitz. I do it recursive in Crafty.
And both work just fine. And since I have done it both ways, and happen to like
recursive better from a readability point of view, I have a "lack of insight
in data structures and programming?" :) Recursion introduces some issues for a
DTS-like program, but even with recursion, DTS could be done if someone wants to
do the work of being able to unwind and rewind a recursive search... _my_
current recursive program seems to work just fine. What does it say about yours
when one written by someone with "a lack of insight in data structures and
programming" keeps managing to beat you tournament after tournament? Wouldn't
it look better if the "supposedly superior programmer" would win one every now
and then? Rather than making asinine statements??? All you want to do is put
others down. Is that because you can't produce anything worthy of mention
yourself, and so you spend your time knocking others? As you fall farther and
farther behind, while claiming to be far superior to everyone else???
_somebody_ has a significant lack of understanding about key issues, but I doubt
it is me...
> What matters more
>is that all variables from 1 position you put in a structure, *that* is very
>interesting for a parallel search.
All values from one position in a contiguous block of memory may or may not be a
good idea. Depends on the temporal locality of the references to all that data.
>
>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.
that is not the most cache-friendly way to write the code, of course. But do it
however you want. I don't use a fixed length per ply move list myself...
>
>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
Why do you continue to worry about others? Seems like you have more than enough
problems to worry about, without stepping outside your own private world???
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.