Author: Bo Persson
Date: 14:22:59 02/17/04
Go up one level in this thread
On February 16, 2004 at 19:08:38, Dann Corbit wrote:
>On February 15, 2004 at 18:00:37, Bo Persson wrote:
>
>>On February 15, 2004 at 14:43:06, Bob Durrett wrote:
>>
>>>On the other hand, maybe there are parts of crafty which could be used in the
>>>beginning so that the newbie programmer could concentrate on creating his/her
>>>own code for the really important parts.
>>
>>The problem is that the really important parts are those that are hard to write,
>>and easiest to copy.
>>
>>The parts that are simple and non-important, you could just as easily write
>>yourself in an evening or three.
>
>The search is more important than the evaluation, in my opinion.
I think that they are both important, but that a simple alpha-beta routine is
explained in many books on algorithms. It is also rather short and well
researched and documented.
An evaluation is much harder to start from scratch, IMO. Partly because there is
much less solid material to read up on.
>
>>>Dann Corbit seems to have suggested that starting with an existing search
>>>algorithm, such as alpha/beta, might be a prudent way to get started.
>>
>>That part you can get from a text book, so you don't have to "borrow" it from
>>some program source.
>
>If you borrow it from a book, that is exactly the same thing.
I wasn't talking about a verbatim copy, but that the algoritm is well described
and easy to find in standard text books. It is also no rocket science - like
this piece from my feeble attempt:
// Start regular search
SCORE Score = -Infinity;
bool LegalMoveFound = false;
for (MoveSequencer::iterator CurrentMove = Replies.begin();
CurrentMove != Replies.end(); ++CurrentMove)
{
ASSERT(!CurrentMove->CapturesKing());
ASSERT(LookAheadBoard.WhiteToMove() ==
CurrentMove->MovedPiece().IsLite());
if (RemainingDepth + Extension > 1)
{
Score = -Search(-Beta, -Alpha,
GameState(LookAheadBoard, *CurrentMove),
RemainingDepth + Extension - 1,
Ply + 1);
}
else
{
Score = -Quiescence(-Beta, -Alpha,
GameState(LookAheadBoard, *CurrentMove),
Ply + 1);
}
if (Score != IllegalMoveScore)
LegalMoveFound = true;
if (Score >= Beta)
{
SCORE LowerBound = AdjustBoundForStoring(Score);
MyTranspositionTable.StoreLowerBound(LookAheadBoard.Signature(),
RemainingDepth,
LookAheadBoard.WhiteToMove(),
*CurrentMove, LowerBound);
MoveHistory.AddHistory(*CurrentMove, RemainingDepth);
if (!CurrentMove->IsCapture())
Killers.AddKiller(Ply, *CurrentMove);
return Score;
}
}
Hardly worth stealing, is it?
>
>> The alpha/beta code is also less than a page long, out of
>>the 60k(?) lines of Crafty.
>
>~42000, unless you add in the EGTB stuff of Eugene, in which case it will be
>larger:
Well, I didn't actually count it but "borrowed" the number from one of Bob's
posts.
> snip
>>>It is not so clear about the position evaluation [and maybe move generator]. I
>>>do not read about well known algorithms for position evaluation.
>>
>>Exactly, so here we have the hard-to-write parts. Using Crafty's evaluation
>>function is definitely cloning.
>
>Except that it did not use Crafty's evaluation function. It did use many of the
>terms from Crafty's evaluation function.
I said that "Using Crafty's evaluation function is definitely cloning." from a
principal point of view, I have no idea what pieces of the code are (or are not)
present in some other chess program.
Using some ideas is ok, using all 4000 lines of Bob's evaluate.cpp is not. It is
also one thing to peek at some code like Crafty to see what's going on there and
get some inspiration, and an entirely different thing to just copy and paste
from it.
I can give you an example, from my own experience:
Like many others, I learned about rotated bitboards from Bob. Of course I also
took a quick peek at Crafty's source, to get the general idea, before I did my
own version.
Only years later did I discover that my bitboards are rotated 0, 45, 90, and 135
degrees instead of Crafty's 0, 90, and +/- 45.
Bob has also numbered the bits in the "wrong" direction. Can't he get anything
right? :-)
If you do a binary compare on the helper tables in my program, you will not get
many matches against Crafty. Probably none at all. Still both programs use
rotated bitboards, based on the same ideas.
Bo Persson
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.