how to find out if a move is valid

Main

Date: 30 Aug 2006 14:44:42
From: Folkert van Heusden
Subject: how to find out if a move is valid

Hi,

I'm trying to develop a chess playing program.
Now I also need to verify if the moves I generate are valid: that they won't
put the king in check or even check mate position.
Now I was wondering: how can I accomplish this? Of course I could check if
the opponent in the next move can capture my king but then I would also have
to check if the moves by the opponent are all valid ...ad infinitum...
So I wonder: is there some non-infinite-recursive way of doing this?

Folkert

Date: 02 Sep 2006 20:47:23
From: Alkhimey
Subject: Re: how to find out if a move is valid

With so many preople flaming me, I have to admit that I am wrong.

Alkhimey wrote:
> Sorry,
> I thought he was asking about something else, my english is not so
> good. But now when I read throught the post again I understand what he
> meant.
>
> And about bugs, I still hold my position: chess programs should not
> have bugs. Just to add an agument, when was the last time you heard
> about a bug in a driver? In my opinion chess program is almost the
> same. And what about real time systems? Do they have bugs too? I think
> the fact that we have bugs in our software is becouse developing
> companies want to save money (after all, security breach in windows can
> not kill) and becouse developers are lazy. But no excuse like this can
> allow bugs in chess program.
>
> David Richerby wrote:
> > Alkhimey <[email protected]> wrote:
> > > Here is my suggestion:
> > > while (you still have aviable moves) {
> > > get next aviable move from the board
> > > if this move is valid (you need to have a method in board class that
> > > will get a move and return true if its valid and false if it is not)
> > > than add this move to a list or an array
> > > }
> > > return the list of valid moves.
> > > [...]
> > > Hope this helps somehow.
> >
> > No, it doesn't. The OP was asking how to determine whether a move is
> > valid and you're suggesting that he does this by calling a method that
> > determines whether the move is valid. You know, the method he's just
> > asked how to write.
> >
> > Do you understand why there are bugs in computer programs yet?
> >
> >
> > Dave.
> >
> > --
> > David Richerby Disposable Swiss Sword (TM): it's
> > www.chiark.greenend.org.uk/~davidr/ like a razor-sharp blade but it's made
> > in Switzerland and you never have to
> > clean it!

Date: 01 Sep 2006 04:02:39
From:
Subject: Re: how to find out if a move is valid

David Richerby wrote:
>
> Oh, in that case, it's because they're over-worked, over-stressed and
> under-slept...

That I agree with! And, alright, sometimes programmers are lazy.

Still, if one over-worked / over-stressed / under-slept / lazy
programmer is able to destabilize a codebase, at least one or two
others share the blame. There's been a process breakdown.

An efficient software corporation often follows a process to help
ensure quality. This process may utilizes one or more of the following
tools: mentoring, customer surveys, product requirement specs, design
specs, functional specs, coding standards, code/spec reviews, unit
tests, static analysis, smoke tests, feature tests, integration tests,
beta tests, bug reviews, bug trend analysis, and root cause analysis.

A smaller team will select fewer of these tools than a larger team, of
course. And occasionally some tools are skipped to meet a deadline.

Date: 01 Sep 2006 02:55:44
From:
Subject: Re: how to find out if a move is valid

Alkhimey wrote:

> when was the last time you heard about a bug in a driver?

About two weeks ago, but the details are confidential.

> And what about real time systems?

About two months ago, but the details are confidential.

> the fact that we have bugs in our software is becouse developing
> companies want to save money

I totally disagree. It's consumers who want to save money! Reliability
carries a price tag, because it requires redundancy, a better design,
and better quality control. Consumers have to foot the bill in the end
and often decide they don't want to. When enough people are willing to
pay for it, software companies deliver.

> becouse developers are lazy.

What the?! You have absolutely, positively never worked in software
development. Do you realize some top corporations have beds in their
offices and serve late dinners to entice their employees to work past
7:30pm in the evening? Lazy is the last thing I would call them.

> But no excuse like this can allow bugs in chess program.

No offense, but you are clearly out of your element when discussing
software development. It's like someone passing a basic driving test,
then telling professional stock car racers how they should drive.

Date: 01 Sep 2006 11:40:42
From: David Richerby
Subject: Re: how to find out if a move is valid

<[email protected] > wrote:
> Alkhimey wrote:
>> becouse developers are lazy.
>
> What the?! You have absolutely, positively never worked in software
> development. Do you realize some top corporations have beds in their
> offices and serve late dinners to entice their employees to work
> past 7:30pm in the evening?

Oh, in that case, it's because they're over-worked, over-stressed and
under-slept...

Dave.

--
David Richerby Confusing Adult Atom Bomb (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a weapon of mass destruction
that you won't want the children to
see but you can't understand it!

Date:
From: Martin Brown
Subject: Re: how to find out if a move is valid

Date: 01 Sep 2006 12:11:13
From: David Richerby
Subject: Re: how to find out if a move is valid

tin Brown <

Date: 03 Sep 2006 12:14:34
From: Harald Luessen
Subject: Re: how to find out if a move is valid

On 01 Sep 2006 David Richerby wrote:

>Just to clarify, en-passant is a little awkward but it doesn't make it
>any harder to determine whether a given move is invalid because it
>puts or leaves the king in check.

I disagree. There are a few positions where chess progamming
beginners may have some problems.

....k... (Kk white/black kings, Qq queens, Rr rooks,
b....... Bb bishops, Nn knights, Pp pawns)
........
........
...Pp...
........
........
....K..R en passant on d3, black to move

After exd3ep castling O-O is not allowed for white.

....k.b.
........
........
...pP...
........
.K......
........
........ en passant on d6, white to move

The move exd6ep is illegal. Though this position can not
occur in a game it can be built with a setboard command.

....k...
........
........
.K.pP..r
........
........
........
........ en passant on d6, white to move

The move exd6ep is illegal. This is easy when make_move(ep)
is done right.

>I'm not convinced. That's a lot of special case code. It would seem
>to me to be much quicker to write the move generator so that it bails
>out as soon as it spots a king capture and score the king capture so
>high that alpha-beta will never choose it. Good move-ordering should
>make that pretty quick.

I disagree. You need the generic incheck test anyway.
- After a setboard command to accept a position or not.
- For castling test with the squares between king and rook.
- At leaf nodes where you do not generate any moves
- At inner nodes when you want to know the checking status
to make pruning decisions with this information.
May be not all reasons are true for your implementation.

By the way did you try your suggestion and do you have a
working sample implementation? How is the performance
compared with the standard technique or the optimisation
I described in my other postings?

Harald

Date: 01 Sep 2006 01:14:25
From: Alkhimey
Subject: Re: how to find out if a move is valid

Sorry,
I thought he was asking about something else, my english is not so
good. But now when I read throught the post again I understand what he
meant.

And about bugs, I still hold my position: chess programs should not
have bugs. Just to add an agument, when was the last time you heard
about a bug in a driver? In my opinion chess program is almost the
same. And what about real time systems? Do they have bugs too? I think
the fact that we have bugs in our software is becouse developing
companies want to save money (after all, security breach in windows can
not kill) and becouse developers are lazy. But no excuse like this can
allow bugs in chess program.

David Richerby wrote:
> Alkhimey <[email protected]> wrote:
> > Here is my suggestion:
> > while (you still have aviable moves) {
> > get next aviable move from the board
> > if this move is valid (you need to have a method in board class that
> > will get a move and return true if its valid and false if it is not)
> > than add this move to a list or an array
> > }
> > return the list of valid moves.
> > [...]
> > Hope this helps somehow.
>
> No, it doesn't. The OP was asking how to determine whether a move is
> valid and you're suggesting that he does this by calling a method that
> determines whether the move is valid. You know, the method he's just
> asked how to write.
>
> Do you understand why there are bugs in computer programs yet?
>
>
> Dave.
>
> --
> David Richerby Disposable Swiss Sword (TM): it's
> www.chiark.greenend.org.uk/~davidr/ like a razor-sharp blade but it's made
> in Switzerland and you never have to
> clean it!

Date: 01 Sep 2006 15:54:12
From: Dave (from the UK)
Subject: Re: how to find out if a move is valid

Alkhimey wrote:

> And about bugs, I still hold my position: chess programs should not
> have bugs. Just to add an agument, when was the last time you heard
> about a bug in a driver? In my opinion chess program is almost the
> same. And what about real time systems? Do they have bugs too? I think
> the fact that we have bugs in our software is becouse developing
> companies want to save money (after all, security breach in windows can
> not kill) and becouse developers are lazy. But no excuse like this can
> allow bugs in chess program.

What are your experiences writing software? Large programs, small? How
many lines? C, BASIC, Fortran or whatever? I'm just puzzled how you can
possibly hold your position if you had actually ever written any
significant amount of software. Or is it what you believe, but have
never written it yourself?

IMHO, which is derived from a number of years writing software (mainly
for scientific use), you really are either very gifted and can write
software different to anyone else, or totally misguided.
--
Dave (from the UK)

Please note my email address changes periodically to avoid spam.
It is always of the form: [email protected]
Hitting reply will work for a few months only - later set it manually.

http://witm.sourceforge.net/ (Web based Mathematica front end)

Date: 01 Sep 2006 15:18:39
From: Thomas T. Veldhouse
Subject: Re: how to find out if a move is valid

"Dave (from the UK)" <[email protected] > wrote:
> Alkhimey wrote:
>
>> And about bugs, I still hold my position: chess programs should not
>> have bugs. Just to add an agument, when was the last time you heard
>> about a bug in a driver? In my opinion chess program is almost the
>> same. And what about real time systems? Do they have bugs too? I think
>> the fact that we have bugs in our software is becouse developing
>> companies want to save money (after all, security breach in windows can
>> not kill) and becouse developers are lazy. But no excuse like this can
>> allow bugs in chess program.
>
> What are your experiences writing software? Large programs, small? How
> many lines? C, BASIC, Fortran or whatever? I'm just puzzled how you can
> possibly hold your position if you had actually ever written any
> significant amount of software. Or is it what you believe, but have
> never written it yourself?
>

It is essentially impossible to have software of any significant complexity
without some sort of defect [aka bug]. A Chess engine is certainly no
exception.

--
Thomas T. Veldhouse
Key Fingerprint: 2DB9 813F F510 82C2 E1AE 34D0 D69D 1EDC D5EC AED1

Date: 01 Sep 2006 12:06:49
From: David Richerby
Subject: Re: how to find out if a move is valid

Alkhimey <[email protected] > wrote:
> David Richerby wrote:
>> Alkhimey <[email protected]> wrote:
>>> Hope this helps somehow.
>>
>> No, it doesn't.
>
> Sorry, I thought he was asking about something else, my english is
> not so good.

OK -- no worries.

> And about bugs, I still hold my position: chess programs should not
> have bugs.

Ever written one?

> Just to add an agument, when was the last time you heard
> about a bug in a driver?

Googling for `device driver bug' geneates 16.4 million hits.

To answer the more specific question, Microsoft released a new version
of a driver to fix a variety of bugs on August 11th.

http://support.microsoft.com/?kbid=916048

> In my opinion chess program is almost the same.

They're nothing like the same.

> And what about real time systems? Do they have bugs too?

See

http://en.wikipedia.org/wiki/Software_bugs

for many examples. Rockets have crashed, people have been killed,
power grids and telecommunications networks have gone down.

> I think the fact that we have bugs in our software is becouse
> developing companies want to save money

We have bugs in our software because software is actually very
difficult to write correctly. As I posted somewhere else in this
thread, the guys who built EDSAC were st enough to build something
that can claim to be the world's first stored-program computer, (i.e.,
one that is programmed in software rather than hardware) but not st
enough to write a program to print a table of prime numbers correctly
first time.

Software is very, very hard. I really recommend that you try writing
some yourself before claiming again that it's easy.

Dave.

--
David Richerby Permanent Game (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ family board game but it'll be there
for ever!

Date: 31 Aug 2006 02:47:26
From: Alkhimey
Subject: Re: how to find out if a move is valid

Here is my suggestion:
while (you still have aviable moves) {
get next aviable move from the board
if this move is valid (you need to have a method in board class that
will get a move and return true if its valid and false if it is not)
than add this move to a list or an array
}
return the list of valid moves.
-----
if the list is returned empty and the side to move is in check than
this side was check mated.
if the list is empty but there is no check than it is pate.

Hope this helps somehow.

Folkert van Heusden wrote:
> David Richerby wrote:
> > > I'm trying to develop a chess playing program. Now I also need to
> > > verify if the moves I generate are valid: that they won't put the
> > > king in check or even check mate position. Now I was wondering: how
> > > can I accomplish this? Of course I could check if the opponent in
> > > the next move can capture my king
> >
> > That's the best way, yes.
>
> So if I want to know what moves for white are valid, I calculate for every
> possible move (A) of white if black could do a move (B) with which it can
> catch my king? And I don't have to check if all (B) moves are valid - won't
> but black into check/-mate?
> (I'm repeating myself here a little but I would like to know this for sure,
> as you can understand :-) )
>
> Thank you for your reply by the way!
>
>
> Folkert van Heusden

Date: 31 Aug 2006 11:57:06
From: David Richerby
Subject: Re: how to find out if a move is valid

Alkhimey <[email protected] > wrote:
> Here is my suggestion:
> while (you still have aviable moves) {
> get next aviable move from the board
> if this move is valid (you need to have a method in board class that
> will get a move and return true if its valid and false if it is not)
> than add this move to a list or an array
> }
> return the list of valid moves.
> [...]
> Hope this helps somehow.

No, it doesn't. The OP was asking how to determine whether a move is
valid and you're suggesting that he does this by calling a method that
determines whether the move is valid. You know, the method he's just
asked how to write.

Do you understand why there are bugs in computer programs yet?

Dave.

--
David Richerby Disposable Swiss Sword (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a razor-sharp blade but it's made
in Switzerland and you never have to
clean it!

Date: 30 Aug 2006 19:36:53
From: Harald Luessen
Subject: Re: how to find out if a move is valid

On Wed, 30 Aug 2006 Folkert van Heusden wrote:

>I'm trying to develop a chess playing program.
>Now I also need to verify if the moves I generate are valid: that they won't
>put the king in check or even check mate position.
>Now I was wondering: how can I accomplish this? Of course I could check if
>the opponent in the next move can capture my king but then I would also have
>to check if the moves by the opponent are all valid ...ad infinitum...
>So I wonder: is there some non-infinite-recursive way of doing this?

A test if a king is in check or even if a square is attacked is
essential. Imagine all types of pieces on the square and look in
the direction of their moves. If you find a similar piece of
the opponent that way these pieces will attack you. Perhaps
take away your own king first and temporary. Do not forget
pawns and the en passant situation. This generic test can
always be used.

The test can be optimised after a move. In most situations
the check can only come through the from or to direction of the move.

You can avoid to generate moves that leave your king in check
but this is not easy and may have bad performance.

You could do the test for each generated move, perhaps after
temporary changing the board, and kick the forbidden move
out of the move list. This is not recommended, too.

While walking through the game tree you can test if the own
king is checked after the move is made and before the next
recursive search function is called. That is what many
chess programmers do. Often the first moves are good enough to
give a beta cut. (Google alpha-beta algorithm.) Therefore
the check is not done for the many no longer needed moves.
This is fast.

alphabeta(alpha,beta,depth)
{
if (you can use it) checktest(own {side to move's} king)
if (depth == 0) return evaluation() // or quiescence search
generate_moves()
for each move
{
do_move() // change board and switch side to move
if (checktest(with the king of the side that just moved))
{
undo_move()
next move
}
value = -alphabeta(-beta,-alpha,depth-1)
undo_move()
if (value >= beta) return beta
if (value > alpha) alpha = value
}
return alpha
}

You can even delay the check test and wait until the king
is really captured. Be sure to try king captures first.
Then back up and clean up immediately. I do not like this.

Harald

Date: 30 Aug 2006 14:33:06
From: David Richerby
Subject: Re: how to find out if a move is valid

Folkert van Heusden <[email protected] > wrote:
> I'm trying to develop a chess playing program. Now I also need to
> verify if the moves I generate are valid: that they won't put the
> king in check or even check mate position. Now I was wondering: how
> can I accomplish this? Of course I could check if the opponent in
> the next move can capture my king

That's the best way, yes.

> but then I would also have to check if the moves by the opponent are
> all valid ...ad infinitum...

No! A pinned piece still gives check. Consider the following
position, with Black to move:

White: Ka1, Rb2
Black: Kb8, Bb7, Bg7

Even though the White rook is pinned against the king, Black cannot
move his b7-bishop because of the discovered check. If you like, you
can think that, after Black plays, say, 1... Ba8, White plays 2.Rxb8
and wins the game before Black has chance to respond 2... Bxa1. So it
doesn't matter that White's king capture would leave him in check.

(Actually, this argument is flawed because the stalemate law clearly
demonstrates that the goal of chess is not to capture the opponent's
king. The conclusion is correct, though. (-: )

Dave.

--
David Richerby Mouldy Miniature Wine (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a vintage Beaujolais but you can hold
in it your hand and it's starting to
grow mushrooms!

Date: 30 Aug 2006 18:46:33
From: Simon Krahnke
Subject: Re: how to find out if a move is valid

* David Richerby <[email protected] > (15:33) schrieb:

> White: Ka1, Rb2
> Black: Kb8, Bb7, Bg7
>
> Even though the White rook is pinned against the king, Black cannot
> move his b7-bishop because of the discovered check.

�discovered check�? The b7-bishop is pinned, too.

Do you call the moving of a pinned piece a discovered check?

> If you like, you
> can think that, after Black plays, say, 1... Ba8, White plays 2.Rxb8
> and wins the game before Black has chance to respond 2... Bxa1. So it
> doesn't matter that White's king capture would leave him in check.

That's all true anyway.

mfg, simon .... l

Date: 31 Aug 2006 10:51:45
From: David Richerby
Subject: Re: how to find out if a move is valid

Simon Krahnke <[email protected] > wrote:
> David Richerby <[email protected]> (15:33) schrieb:
>> White: Ka1, Rb2
>> Black: Kb8, Bb7, Bg7
>>
>> Even though the White rook is pinned against the king, Black cannot
>> move his b7-bishop because of the discovered check.
>
> �discovered check�? The b7-bishop is pinned, too.

Moving the bishop discovers (uncovers would be the more natural
English word) a check on the black king. I don't see a problem with
my use of terminology there.

> Do you call the moving of a pinned piece a discovered check?

I think it's reasonable to do so in this case.

Dave.

--
David Richerby Revolting Hat (TM): it's like a hat
www.chiark.greenend.org.uk/~davidr/ but it'll turn your stomach!

Date: 30 Aug 2006 17:04:55
From: Folkert van Heusden
Subject: Re: how to find out if a move is valid

David Richerby wrote:
> > I'm trying to develop a chess playing program. �Now I also need to
> > verify if the moves I generate are valid: that they won't put the
> > king in check or even check mate position. �Now I was wondering: how
> > can I accomplish this? Of course I could check if the opponent in
> > the next move can capture my king
>
> That's the best way, yes.

So if I want to know what moves for white are valid, I calculate for every
possible move (A) of white if black could do a move (B) with which it can
catch my king? And I don't have to check if all (B) moves are valid - won't
but black into check/-mate?
(I'm repeating myself here a little but I would like to know this for sure,
as you can understand :-) )

Thank you for your reply by the way!

Folkert van Heusden