Working out legal moves - expensive?

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

Hi all,

In my spare time I am picking away at the code to do a correspondence
chess website, and have been writing the move generator functions.

It would be *nice* to have javascript in the client to tell the user
*in real time* if the move they are making is allowed - but of course
this requires that I work out all the *legal* moves for all the pieces
in advance (working out the legal moves is far more expensive than just
"the moves", because you need to look for the king being checked -
which means testing each candidate position for threatened squares).

I guess what I'm saying is, if I pre-compute all the legal moves, its
going to be quite expensive - because I have to do the "check" test for
every possible move in order to whittle the moves down; whereas if the
"check" test happens after the fact, you only need to check the move
they are trying to make.

I've been talking to a colleague who's working on a chinese chess
interface, and he has similar issues but is looking at caching the
threatened square patterns in a database to ease the expense of working
them out - all in the pursuit of having real time move validation...

Has anybody else got any views on this?

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

I realise it's much more efficient to do the full check after the move
has been attempted, but wouldn't it be lovely to have the client
restrict it without having to talk to the server.

There is the possibility of using the XML trick to talk to the server
without leaving the page to check candidate position legality, but I've
never tried it. (the same trick Google Mail uses to auto-fill email
addresses)

I guess I should just complete the programming and see how much of a
hit it takes to work out where everything can go in advance - it lets
you have some nice features for the chess board display, like
displaying "threatened squares", and "where this piece can move" as the
user clicks on it...

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

Yes - but what I'm thinking about doing here is all the legwork
up-front - so (in this case) PHP does all the hard work of figuring out
which pieces can go where, and outputs some javascript arrays to the
published page (programatically created Javascript), which is then used
in the page to check what you are trying to do on the board.

The problem (about which my concerns may be unwarranted) is that the
PHP code has to work out every move possible, and then go through every
move making sure the king is not in check following the move - and the
only way to do this is compute the treatened squares for every piece on
the board... during the opening and middlegame this is *expensive* in
terms of processing time.

I have seen no other chess sites do it, but then that may be because
they didn't know how to

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

jonathan.beckett <jonathan.beckett@gmail.com> wrote:
> It would be *nice* to have javascript in the client to tell the user
> *in real time* if the move they are making is allowed - but of course
> this requires that I work out all the *legal* moves for all the pieces
> in advance

Does it? The obvious way is to test that the move submitted is legal and
then submit it to the server -- can JavaScript not do that? Call a move
pseudo-legal if it would be legal ignoring check, i.e., that bishops move
diagonally without jumping, etc. A move is legal exactly when it is
pseudo-legal and it would not be pseudo-legal for any of the opponent's
pieces to capture the king as the next move. That should be pretty
trivial to do -- note that you don't have to consider en passant, castling
or promotion in the check test.


Dave.

--
David Richerby Lead Chicken (TM): it's like a farm
www.chiark.greenend.org.uk/~davidr/ animal that weighs a ton!

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

jonathan.beckett <jonathan.beckett@gmail.com> wrote:
> I realise it's much more efficient to do the full check after the move
> has been attempted, but wouldn't it be lovely to have the client
> restrict it without having to talk to the server.

Sure. What I had in mind is that, when the user clicks to say where they
want the piece to move to, some JavaScript executes to check that the move
is legal and, if it is, sends the request off to the server. Isn't that
how the bits of JavaScript on self-validating web forms work?


Dave.

--
David Richerby Homicidal Crystal Drink (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a refreshing juice beverage but
it's completely transparent and it
wants to kill you!

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

>several thousand times a second

Yes, you would think so, but then when you get several thousand players
online continually making those requests, people start to have to wait
for a second - which is perhaps unacceptable.

One of my friends is hitting a similar problem by recording the common
board positions in a table and looking them up... which takes a lot of
the heat out of the problem.

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

jonathan.beckett <jonathan.beckett@gmail.com> wrote:
> Yes - but what I'm thinking about doing here is all the legwork
> up-front - so (in this case) PHP does all the hard work of figuring out
> which pieces can go where, and outputs some javascript arrays to the
> published page (programatically created Javascript), which is then used
> in the page to check what you are trying to do on the board.

Ah, I see what you mean. Since a well-written C/assembler program can
work out all the legal moves in a position several hundred times a second,
I imagine that you should be able to do it at least a few thousand times a
second in PHP, which should be more than fast enough.


Dave.

--
David Richerby Erotic Salted Tool (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ screwdriver but it's covered in salt
and genuinely erotic!

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

* jonathan.beckett <jonathan.beckett@gmail.com> (23:12) schrieb:

>> several thousand times a second
>
> Yes, you would think so, but then when you get several thousand players
> online continually making those requests, people start to have to wait
> for a second - which is perhaps unacceptable.

That would be a reason to do that client-side. Only test the move to
legal on the server. That's easy, test the move to be pseudo legal, do
it and check if the position is still legal.

> One of my friends is hitting a similar problem by recording the common
> board positions in a table and looking them up... which takes a lot of
> the heat out of the problem.

Sounds like an opening book.

mfg, simon .... l

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

David Richerby <davidr@chiark.greenend.org.uk> wrote:
> Since a well-written C/assembler program can work out all the legal
> moves in a position several hundred times a second

*cough* That should, of course, read `several hundred _thousand_ times a
second'.


Dave.

--
David Richerby Simple Dangerous Drink (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a refreshing juice beverage but
it could explode at any minute and it
has no moving parts!

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

jonathan.beckett <jonathan.beckett@gmail.com> wrote:
> David Richerby wrote:
>> several thousand times a second
>
> Yes, you would think so, but then when you get several thousand players
> online continually making those requests, people start to have to wait
> for a second - which is perhaps unacceptable.

It seems very unlikely to me that you will need to handle several thousand
moves per second. Even ten thousand people online at once playing five-
minute blitz games at an average of 40 moves per game only generates 1300
moves per second. Correspondence chess isn't usually played at such a
frenetic pace.

For comparison, FICS hasn't had more than 1052 players online simultan-
eously since the server was last rebooted a month ago; there are currently
1134 players logged in to the ICC. I'd be surprised if you had to deal
with even tens of moves per second (remember that's a million a day).


Dave.

--
David Richerby Incredible Sword (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a razor-sharp blade but it'll blow
your mind!