Checking for Legal Moves in Checkers

[np_123]

What is it you are trying to achieve?
Be able to identify (in a game of checkers) when there are no legal moves possible, and there are pieces from both sides still remaining on the board


What is the problem you are having?
I've just about created a working 2-player checkers game (no AI), in Turing, with the exception that I currently do not account for the situation that both sides have pieces, but one player doesn't have any legal moves.
I'm asking: what is the most efficient way to check if there are any remaining legal moves for each side?

Would it be iterating through each and every piece, checking for at least one possible move?


Describe what you have tried to solve this problem
I haven't put anything into code yet to do this 'move-checking' but am looking for the most efficient way to do it
I think I will be capable of applying (putting into code) suggested methods to solve the problem


PS. Two functions that I have used extensively in the attached code are X_to_sqx and Y_to_sqy -> these convert the coordinates of the mouse to squares on the grid of a checkerboard

[Raknarg]

There's not really a more elegant solution, nor do you need one. Remember that computers can do many things very quickly. You should only be worrying about efficiency once you have to calculate a huge amount of data. With this problem, you only have to check 24 pieces. In fact you could probably check 10000 pieces and notice hardly any difference in speed if you check every possible move.

Anyways, like I said, there's not really any way you can get around move checking without checking every piece. Also like I said, even if you do, it's still very fast, you only really have to check 2 or 4 spots per piece. You they can move forward diagonally, jump diagonally, and in the case of kings, jump backwards. Thats not that many things to check.

Keep this in mind for the future: Try to balance simplicity and efficiency. Sometimes it's better just to use something simple rather than something efficient because it saves you the headache of trying to implement something more complex for hardly any return.

[np_123]

Okay, that makes sense

I'll get to work on implementing that solution...shouldn't take too long to work that into my program, seeing as I've already separated the procedures involving the jumps and regular moves.

So essentially, I'm checking like half the moves then, seeing as I have the jumps covered beforehand

[np_123]

Thanks

[np_123]

In case you're interested in seeing how I got my game working
It's 2-player, but as of yet I haven't the time to try to create a working AI, so it'd have to be 2 players, on the same computer playing against each other

I've tested gameplay, and haven't noticed any bugs - if any are found, please let me know

To my knowledge, it enforces the rules of checkers - NO illegal moves are allowed!
It will only allow you to click on pieces that can legally be moved, and will not move on to the next player's turn unless a turn has been made and completed fully

[Raknarg]

One thing I can see right now is that you can't seem to change the piece you're using once you select it.

It would also be nice if you had something saying the current turn, and if you wanted to go further light up the pieces that can be played

[np_123]

Those are some great ideas - thanks for the feedback.
I'll work on adding those features into the game.

I actually thought a lot about the changing pieces, but I wasn't too sure how to work that in.

I think I might make selecting the pieces a completely separate procedure then, cuz that'll make it easier then to reset if the person wants to change the piece.

Do you think it'd be okay to set it so that to deselect you click the same piece again?
That would be an easy catch with if statements then

[Raknarg]

Select the same piece, or maybe if they click out of the play area

[np_123]

That 'catch' could potentially also solve the problem that if you click a certain distance outside of the grid it crashes since it would exceed the array boundaries for the piece locations.

Again, many thanks.

[Raknarg]

Protip: If the user can make the game crash, you should probably find a way to make sure they can't crash the game

[np_123]

yeah, up to now I've been mostly putting all my effort into making sure the game works per the rules of checkers
I'll only need to add a couple of if statements (I think) but you're 100% right, I should make sure the user can't crash the game

To be honest, this is one of the first programs I've made that isn't 'foolproof'
Even back when I had ICS3U, I made sure my programs wouldn't crash, even though my teacher's solutions crashed or didn't work quite often

[Raknarg]

Haha that doesn't sound like the best teacher.

In any case, good work

[np_123]

Haha, he was a pretty useless teacher for the course.

He gave us booklets that summarized a concept, and had a bunch of practice programs for us to make, then he would just sit at his desk and mark work from one of his other classes.

By the time we were mid-way through the course, the teacher was compiling code from either myself or a couple of my friends and using it as his 'solutions' that he used as a standard to mark by.

Pretty much, everything I know about Turing I taught myself

[evildaddy911]

i hate those teacher :/ this year in the gr11 ICS course, he decided that he would switch from visual basic to Python.. he started learning python the 2 days before school started.. hes refusing to change any of the projects from the VB course so some of them are nearly impossible. fortuneately, those teachers are easy to bullcrap, all i have to do is say "thats a recursive method" and he says ok and gives me 100%, no questions asked

[Raknarg]

unfortunately, it's also a wasted opportunity to learn.