| |
Main
Date: 14 Nov 2006 11:18:05
From: Azlan
Subject: Forced Mate Sequence in Alpha-Beta?
|
I'm writing a chess program in VB6 that features a 'mate solver'. It
uses the alpha-beta algorithm and generally follows the pseudo-code
below.
Code:
int AlphaBeta(int depth, int alpha, int beta)
{ if (depth == 0)
return Evaluate();
GenerateLegalMoves();
while (MovesLeft())
{
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}
My program is able to correctly determine if a checkmate can be forced
in a given position and can even determine how many moves it will
take. Something has me stumped, however.
How do I output the moves to the forced line of play that was found?
The algorithm above just outputs a 'value' indicating checkmate was
found but not the moves themselves. I need the moves. Thanks in
advance.
|
|
| |
Date: 15 Nov 2006 01:28:55
From: Tony M
Subject: Re: Forced Mate Sequence in Alpha-Beta?
|
On Tue, 14 Nov 2006 11:18:05 GMT, [email protected] (Azlan) wrote:
>I'm writing a chess program in VB6 that features a 'mate solver'. It
>uses the alpha-beta algorithm and generally follows the pseudo-code
>below.
>
>Code:
>
>int AlphaBeta(int depth, int alpha, int beta)
>{ if (depth == 0)
> return Evaluate();
> GenerateLegalMoves();
> while (MovesLeft())
> {
> MakeNextMove();
> val = -AlphaBeta(depth - 1, -beta, -alpha);
> UnmakeMove();
> if (val >= beta)
> return beta;
> if (val > alpha)
> alpha = val;
> }
>return alpha;
>}
>
>My program is able to correctly determine if a checkmate can be forced
>in a given position and can even determine how many moves it will
>take. Something has me stumped, however.
>
>How do I output the moves to the forced line of play that was found?
>The algorithm above just outputs a 'value' indicating checkmate was
>found but not the moves themselves. I need the moves. Thanks in
>advance.
It looks like you got your routine from Bruce Moreland's web site.
Take a look at his page on collecting the PV (Principal Variation, ie
the main thinking line):
http://www.seanet.com/~brucemo/topics/pv.htm
Tony
|
| |
Date: 14 Nov 2006 10:11:52
From: Mr. Question
Subject: Re: Forced Mate Sequence in Alpha-Beta?
|
You keep track of the moves made.
You pass an array to each ply and you update it with the move made, and let
it back up, etc. etc.
Just like with a regular search.
"Azlan" <[email protected] > wrote in message
news:[email protected]...
> I'm writing a chess program in VB6 that features a 'mate solver'. It
> uses the alpha-beta algorithm and generally follows the pseudo-code
> below.
>
> Code:
>
> int AlphaBeta(int depth, int alpha, int beta)
> { if (depth == 0)
> return Evaluate();
> GenerateLegalMoves();
> while (MovesLeft())
> {
> MakeNextMove();
> val = -AlphaBeta(depth - 1, -beta, -alpha);
> UnmakeMove();
> if (val >= beta)
> return beta;
> if (val > alpha)
> alpha = val;
> }
> return alpha;
> }
>
> My program is able to correctly determine if a checkmate can be forced
> in a given position and can even determine how many moves it will
> take. Something has me stumped, however.
>
> How do I output the moves to the forced line of play that was found?
> The algorithm above just outputs a 'value' indicating checkmate was
> found but not the moves themselves. I need the moves. Thanks in
> advance.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
| |
Date: 14 Nov 2006 15:39:39
From: David Richerby
Subject: Re: Forced Mate Sequence in Alpha-Beta?
|
Azlan <[email protected] > wrote:
> I'm writing a chess program in VB6 that features a 'mate solver'. It
> uses the alpha-beta algorithm and generally follows the pseudo-code
> below.
> [...]
> How do I output the moves to the forced line of play that was found?
> The algorithm above just outputs a 'value' indicating checkmate was
> found but not the moves themselves. I need the moves. Thanks in
> advance.
You need two data-structures: one to keep track of the line the
program is currently thinking about and one to remember the best line
(shortest mate, in your case) found so far.
So, your AlphaBeta() routine needs to be modified to be something like
this, but you'll need to check the sign of val and bestval.
> int AlphaBeta(int depth, int alpha, int beta)
> { if (depth == 0)
> return Evaluate();
> GenerateLegalMoves();
> while (MovesLeft())
> {
> MakeNextMove();
AppendThatMoveToEndOfCurrentLine();
> val = -AlphaBeta(depth - 1, -beta, -alpha);
> UnmakeMove();
if (val > bestval)
{
bestval=val;
CopyCurrentLineToBestLine();
}
DeleteLastMoveOfCurrentLine()
> if (val >= beta)
> return beta;
> if (val > alpha)
> alpha = val;
> }
> return alpha;
> }
Dave.
--
David Richerby Fluorescent Chainsaw (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a lethal weapon but it'll hurt your
eyes!
|
|
