• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
patishi

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

4 posts in this topic

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.

0

Share this post


Link to post
Share on other sites

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 [url="https://chessprogramming.wikispaces.com/Move+Ordering#Typical%20move%20ordering"]typical move ordering[/url] 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 [url="https://chessprogramming.wikispaces.com/MVV-LVA"]MVV-LVA[/url] 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. :)

0

Share this post


Link to post
Share on other sites

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).

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0