11 Replies - 2677 Views - Last Post: 19 March 2011 - 02:39 PM Rate Topic: -----

#1 absolute1987  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-March 11

looking for ideas on checkmate algorithm

Posted 19 March 2011 - 02:17 AM

I am doing a 2 player chess game in c++.

The most difficult part was doing the checkmate function.


What I did is the following:

All pieces are stored in an 8x8x2 matrix.

the first layer contains the type of piece and the second layer contains the
side to which the piece belongs.

-Loop trough the entire matrix and see if any enemy pieces can attack the king
Store in a list the locations of every enemy piece that can attack the king

-for each stored location, see if the defending player can occupy it, thus
implying that the enemy piece causing a check can be removed
If the piece is removable delete its stored location from the list

-Now for those pieces which cannot be removed check if they can be blocked.
This is done by looping trough all the empty tiles between the king and the enemy
piece causing a check. For each empty tile loop trough the matrix and see if the defending
player can put a piece there thus blocking a check.

-If there are still checks which cannot be resolved, do all of the above but this time do it on
the empty tiles adjacent to the king. If the king has no were to go and each empty tile is a location
that can be checked then its checkmate.


This works but I think that there is a smarter way of doing this which requires less
strain on computer resources. What I need
is not code but ideas. Coding ideas is easy for me, sometimes coming up with
ideas is the must daunting task for me.

Can anyone tell me if he/she has a better idea than mine?

Is This A Good Question/Topic? 0
  • +

Replies To: looking for ideas on checkmate algorithm

#2 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5940
  • View blog
  • Posts: 12,868
  • Joined: 16-October 07

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 03:33 AM

View Postabsolute1987, on 19 March 2011 - 04:17 AM, said:

All pieces are stored in an 8x8x2 matrix.


You don't use array dimension to store extra values. Make a struct and have an 8x8 of that.

It is simpler than you make it out to be, but probably just as much strain.

View Postabsolute1987, on 19 March 2011 - 04:17 AM, said:

Loop trough the entire matrix and see if any enemy pieces can attack the king


Yep.

View Postabsolute1987, on 19 March 2011 - 04:17 AM, said:

Store in a list the locations of every enemy piece that can attack the king


Who cares? We know the king is in check, all we need to know is if he can get out of it.

You now proceed to make every legal move the player in check is allowed to make. If any of those moves result in him not being in check, then it's not mate.

Your board represents state. The easiest way to analyze moves is to be able to maintain the current state and then make copies of it, alter the copies, and check the results.

This post has been edited by baavgai: 19 March 2011 - 03:33 AM

Was This Post Helpful? 3
  • +
  • -

#3 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 1
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 08:46 AM

View Postbaavgai, on 19 March 2011 - 10:33 AM, said:

View Postabsolute1987, on 19 March 2011 - 04:17 AM, said:

Loop trough the entire matrix and see if any enemy pieces can attack the king

Yep.

No!

You use the king as reference and work out all valid paths/moves to him and see if any pieces lay in any of those paths and if that path is a valid move for that piece. :)
Was This Post Helpful? 2
  • +
  • -

#4 absolute1987  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-March 11

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 08:49 AM

Hmm so I see, so in terms of storing data I can simplify it but I would still need to make every legal move and then
for each legal move see if the king is still in check. I just thought that there are more cunning ways of
doing this.

Thx baavgai I will use the struct storage mechanism.
Was This Post Helpful? 0
  • +
  • -

#5 absolute1987  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-March 11

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 09:07 AM

I think that in a way, that is what my code does.

It uses a generic IsMovePossible() Function.

The IsMovePossible function is given two sets of coordinates:
the destination coordinates and the departure coordinates.

It checks what the piece is and depending on the piece,
a set of rules are checked that they are obeyed. Also
it checks if each tile between the departure and arrival tiles are clear.
In the case of the knight I use a simple formula which makes sure it will
make L movements only.

This IsMovePossible is used on all enemy pieces to see if they can touch the king.
I store any treats in a list in an attempt to make the game more efficient and try to
avoid unnecessary looping.

I don't really care about the game its self. I am just trying to learn to code properly
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5940
  • View blog
  • Posts: 12,868
  • Joined: 16-October 07

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 10:31 AM

Hmm...


View Postabsolute1987, on 19 March 2011 - 04:17 AM, said:

see if any enemy pieces can attack the king



View PostButchDean, on 19 March 2011 - 10:46 AM, said:

No! ... work out all valid paths/moves to him and see if any pieces lay in any of those paths and if that path is a valid move for that piece.


Sorry, you're more pedantically spelling it out, but you didn't really invalidate the original assertion.

There are a number of heuristics that can come into play. Your setup should already be able to isolate capture moves, right? Perhaps not, if it's just two player. You'd still need to validate that a move is viable. By extension, it should be trivial to identify which of the viable moves results in a king's capture.

Sure, you could write something that views the world from a specific piece's perspective. And, yes, that would be optimal for that piece. However, it also stinks of premature optimization, when you presumably have to have other mechanisms in place to play the game at all.

This post has been edited by baavgai: 19 March 2011 - 10:32 AM

Was This Post Helpful? 0
  • +
  • -

#7 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 1
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 10:40 AM

View Postbaavgai, on 19 March 2011 - 05:31 PM, said:

Sorry, you're more pedantically spelling it out, but you didn't really invalidate the original assertion.

There are a number of heuristics that can come into play. Your setup should already be able to isolate capture moves, right? Perhaps not, if it's just two player. You'd still need to validate that a move is viable. By extension, it should be trivial to identify which of the viable moves results in a king's capture.

Sure, you could write something that views the world from a specific piece's perspective. And, yes, that would be optimal for that piece. However, it also stinks of premature optimization, when you presumably have to have other mechanisms in place to play the game at all.

Premature optimization is a good thing is games, you always find the best way to do something with minimal effort - there is nothing wrong with that.

When you are looking at a specific situation, as in checking if a checkmate or even check has occurred, there is no point in calculating the possibilities for pieces that cannot possibly check the king. When the pieces are determined by the rough algorithm I suggested, then you check which one are the threat by using whatever heuristic to determine which pices are on a path for a checkmate.

There is no reason to do anything more. :)
Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5940
  • View blog
  • Posts: 12,868
  • Joined: 16-October 07

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 11:40 AM

View PostButchDean, on 19 March 2011 - 12:40 PM, said:

Premature optimization is a good thing is games


"Premature" optimization is never a good thing. Though, I agree, games tend to optimize certain elements much more than most programming efforts. Yes, I do remember doing an anti-aliased line in ASM...

View PostButchDean, on 19 March 2011 - 12:40 PM, said:

you always find the best way to do something with minimal effort - there is nothing wrong with that.


Absolutely agree. Again, optimization implies that the minimal effort has already been made to create something that works, and it's now being optimized. If the best method is clear, to hand, and doesn't take any extra effort, then it's not optimized, just well done.
Was This Post Helpful? 0
  • +
  • -

#9 absolute1987  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-March 11

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 12:31 PM

Ok thx both of you, I will try out your ideas and take my time in trying to fully understand what you said. English is not my first language so it will take a while.
Was This Post Helpful? 0
  • +
  • -

#10 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 1
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 01:43 PM

View Postbaavgai, on 19 March 2011 - 06:40 PM, said:

View PostButchDean, on 19 March 2011 - 12:40 PM, said:

Premature optimization is a good thing is games


"Premature" optimization is never a good thing. Though, I agree, games tend to optimize certain elements much more than most programming efforts. Yes, I do remember doing an anti-aliased line in ASM...

View PostButchDean, on 19 March 2011 - 12:40 PM, said:

you always find the best way to do something with minimal effort - there is nothing wrong with that.


Absolutely agree. Again, optimization implies that the minimal effort has already been made to create something that works, and it's now being optimized. If the best method is clear, to hand, and doesn't take any extra effort, then it's not optimized, just well done.

Sorry baavgai, have to disagree with your opinion on optimization here. Game algorithm optimization is always a good thing. It helps game devs get the game out the door on time. I have even had my wrists slapped once or twice for choosing to optimize later. It just is the done thing to optimize as soon as possible as you see fit. :)
Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5940
  • View blog
  • Posts: 12,868
  • Joined: 16-October 07

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 02:14 PM

I don't think we're on the some page here.

I'm talking about premature optimization in this context:

Quote

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. - Knuth


You may choose to disagree with the Father of the analysis of algorithms as you like. I find his insight is still relevant.

More here.
Was This Post Helpful? 0
  • +
  • -

#12 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 1
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: looking for ideas on checkmate algorithm

Posted 19 March 2011 - 02:39 PM

View Postbaavgai, on 19 March 2011 - 09:14 PM, said:

I don't think we're on the some page here.

I'm talking about premature optimization in this context:

Quote

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. - Knuth


You may choose to disagree with the Father of the analysis of algorithms as you like. I find his insight is still relevant.

More here.

I meant 'premature', yes.

Donald Knuth is not a game developer, and you should be aware that his writing are for general programming practice that may or may not be relevant to a certain task at hand. His works offer may solutions and suggestions that may or may not be particularly applicable. He is also very well respected in the games industry, but that still doesn't dissuade premature optimization and the clear benefits of doing so when working with games.

As I've said once or twice here on DIC, game developers are not textbook programmers. Yes, we learn and have learned from them like everyone else, but when I comes to games we do what is most beneficial to the task at hand even if it appears to go against the grain of conventional software engineering.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1