Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


Best way to assert the king is not in check when generating moves in chess


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 13 December 2013 - 10:40 AM

I am now working on generating moves in chess.  I am writing move generation function for every piece (pawn,knight,bishop...)and i currently generation all possible moves without any kind of filtering.  

 

 I wonder what is the preffered way to assert that the king is not in check after the move is played (e.g if the move is valid).    The way i see it,  I have to actually play the move on the board and only than can I know that the king is not exposed or attacked.     But should I make this valiadation in the alpha-beta function (in the actual evaluation stage) ?   or maybe "artificialy"  make the move inside the moves generation function and decide if i should add it to the list in the first place.    

 

Also,  can you give me some tips on how to improve the move generation ?  maybe not generate all possible moves? 

 

Thx.



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13628

Like
0Likes
Like

Posted 13 December 2013 - 12:58 PM

For your first question, you have a choice as to whether you filter moves that expose the king at generation time or you do so when you actually try to make the move in the alpha-beta loop. The latter is simpler and it's what I have always done. People refer to this as "pseudo-legal" move generation. It might be worth having a specialized function that generates check evasions, because is you are in check most of the pseudo-legal moves are likely to be illegal, and legal move generation is going to be faster. You should probably not do this at first, and leave it as a possible optimization for later on.

 

As to how to improve move generation, the main idea is to stagger move generation, so you only generate the moves you need. This is closely related to move ordering heuristics, which are critical to be able to reach high depths.

 

The chess programming wiki (which you should bookmark) has a good description of a typical move ordering in a chess program. If you use something like that, you should have a function to verify if a move is valid from the current position, so you can try the hash move before generating any moves. You then generate captures, sort them (probably in MVV-LVA order) and try them out, evaluating the ones with positive SEE and saving for later the ones with negative or zero SEE (you'll have to test lots of choices here to see what works best for your engine). Then again you can use the function that verifies if a move is valid from the current position, to try out the killer moves without generating any other moves. Then you generate non-captures.

 

Organizing the code to do all of this can be messy. I recommend creating a MoveGenerator object that keeps track of where you stand in the process, what lists of moves you still have to go through, etc. The interface to this object consists of a method get_next_move(), so code that uses this can be kept very clean.

 

Also very important is the move generation in the quiescence search, because that's likely to be where your engine spends most of its time. For that, you want to use the capture generator, the check-evasion generator and perhaps a specialized generator for non-capturing checks, if you are going to consider those moves in your quiescence search (again you need to test lots of options to see what works for your engine).

 

I have mentioned a couple of places where you will need to test different options. That is the main mode of development of an engine once you manage to put something together that obeys the rules and can talk UCI. So make sure you find a good mechanism to test one version of your program against another or against some reference opponents.

 

That should keep you busy for a while. :)



#3 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 13 December 2013 - 01:21 PM

Thanks a lot for the very detailed answer.  Boy! do I still have a lot of work to do :)      

 

I remember that i first need to try and play the hash move, capture moves, killer moves etc..   first, before i am going to play the quiet moves.   But I (stupidly) was going to generate all the possible moves fist and only play them in that order.     Thank you for correcting me, now i know that there is no point in generating usless moves if i am not going to actually play them ( or at least not sure about that).



#4 Álvaro   Crossbones+   -  Reputation: 13628

Like
0Likes
Like

Posted 13 December 2013 - 02:36 PM

Well, if you follow my advice about encapsulating the staggered move generation and move ordering in a neat little object, you can start with something that generates all the moves and sorts them, and later on you can come back and do the more sophisticated thing. I gave you the full answer because you asked about how to improve it.

 

Keep me posted on your progress and feel free to ask more questions along the way. I know it can be a bit overwhelming at the beginning.



#5 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 13 December 2013 - 03:54 PM

Thank a lot my friend!    very much appreciated






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS