title: Computing Checkmate Correctly
body: <p>When computing checkmate for a king in chess, do you determine the other players possible moves against your king? Or do you consider merely their unit's reach? If you say it's the former, then there is a contradiction like "this statement is false" Consider this image with two kings a square apart and their knights protecting from above rooks. If we assume that the definition of possible moves must prevent check based on enemy possible moves, then the logic recursively alternates. </p>
  
  <blockquote>
    <ol>
    <li>First, we say that our king is in check from the enemy knight so we are limited from moving our own knight because we must escape. </li>
    <li>Then we realize that the knight does not have an available move into our king's square because he will be placing his king in check with our rook. He does not have our king in check after all.</li>
    <li>Then we realize, free from check, that we are now able to move our own knight to the enemy king forcing him to move from check and preventing further his choices.</li>
    <li>However, we notice that we cannot do this because it will place us in check with the enemy rook.</li>
    <li>We realize that since we cannot actually move our knight, the enemy king is not actually in check, therefore he is freely able to use his knight to attack our king.</li>
    <li>Go to step 2 (no matter how many times you have already).</li>
    </ol>
  </blockquote>
  
  <p>Okay, so maybe we assume that reach always counts regardless of the enemy's check status. If our king is in reach of the enemy knight's usual attack range, we consider it a check and must resolve it. Is this how the actual game is ruled though? It seems an easy solution to the problem faced when programming the game logic, but I'm not sure if it is correct or not.</p>
  
  <p><img src="https://i.stack.imgur.com/1OcXq.png" alt="Both in check, or neither?"></p>
  
  <p>I did some thinking and came up with this analysis:
  I think you have proven that the scenario of both kings being in check (not necessarily the scenario of the board I showed) cannot exist by contradiction.
  Only one player can make a move at a time.
  Therefore, one player makes the initial move which transitions from the state of no kings being in check to some king(s) being in check.
  According to the rules, this move is not allowed if that player's king results is in a check. (I will point out the significance of 'results' soon)
  This means that no matter how check is defined, he cannot make any move if his king meets that condition.
  Therefore, the only transition to checks from no checks is to the enemy being in check.
  The enemy must escape check, still following the rule of not entering check in one move.
  The remaining state would be game over or that king escaping check.</p>
  
  <p>So I understand that both kings being in check is not possible. 
  Now the board I showed is either reachable or not reachable. 
  Let's assume the board is reachable and see if there is a contradiction.
  Let's ambiguously assume it's white's turn since the scenario is symmetric. 
  This means black just moved.
  Therefore, black's king is not in check.
  The black king is only reachable by the white knight.
  Therefore, the white knight must be restricted by some rule to not attack the black king.
  The only two possible rules that can enforce that conclusion are:</p>
  
  <blockquote>
    <ol>
    <li>The white knight is currently protecting his king from check.</li>
    <li>The white king is in check already and that move will not solve the check.</li>
    </ol>
  </blockquote>
  
  <p>First, assume 2 is true regardless of 1.
  The white king is in check and the only piece in attack range is black knight.
  The black knight cannot attack the square containing king, however, because it would place his own king in check.
  Therefore 1 must be true and the white king is not in check.
  So both kings are not in check.
  We reverse the game board to see if this is reachable.
  Assume the scenario with the following alterations:
  White has a bishop 2 up and 1 right from the black rook.
  The black king is one square to the left.
  The white king is one square to the right.
  No kings are in range of any other pieces, so it may be reasonable to assume this initial state is reachable.
  The black knight is protecting his king from the bishop, so it cannot move to under the white knight.
  The white king moves left.
  Now the white knight is protecting the white king and cannot move to under the black knight.
  The black king moves right one square.
  Thus, the scenario is reachable.
  The only questioned assumption standing is that when any moves are considered, it is safe to assume that the check rules are computed. Thus, a king may come in range of a unit which may not attack it due to prevention of his own king being in check. If this assumption is not made, then the pieces simply could follow the rules of not allowing kings to enter the unrestricted attack range of an enemy unit.
  Now, it is interesting to see if this scenario is computable without infinite loops.
  For dependencies, I will use arrows.
  For the initial white king moving left,
  white king -> black knight stopped -> white bishop attack black king
  Those are single step computations, no loops in dependencies so far.
  For the black king to move right, 
  black king -> white knight stopped -> black rook attack white king
  Still no dependencies.
  What about when we now try to check white knight's available moves including attacking the black king?
  white knight stopped -> black rook attack white king
  What about if the white rook attacks the black rook?
  white rook stopped -> black knight attack white king
  White's remaining options are to move the king to the right or down.</p>
  
  <p>Our conclusion,</p>
  
  <blockquote>
    <ol>
    <li>Moving to this board state is possible without breaking the 'don't move into check' rule.</li>
    <li>This board state obviously assumes that computing check depends on possible enemy moves, not their simple native attack ranges.</li>
    <li>When this state is reached, both kings are not in check.</li>
    <li>It is at least possible that this is not a stalemate. (Unknown if always)</li>
    </ol>
  </blockquote>
  
  <p>So I finally found rules on wikipedia about placing another king in check even if it compromises one's own king. So, we cannot make our assumption in part 2, thus the board state is not reachable.
  "A piece unable to move because it would place its own king in check (it is pinned against its own king) may still deliver check to the opposing player."
  Thus our final conclusion for the apparent actual rules of chess, the board state is not reachable as it follows the check rules.</p>
  
  <p>I am going to choose icedtrees answer because of the valuable logic which follows the game rules:</p>
  
  <pre><code>if for every move for player X (ignoring rules about king threats), 
  player Y can capture player X's king next turn, 
  then player X is in checkmate.
  </code></pre>
  
  <p>However, I would fix them to be the following:</p>
  
  <pre><code>{X is checkmate}
  if and only if {
      For all legal moves:(move according to rule definition) X {
         There exists a generic move:(legal move A ignoring rules of protecting king A) Y such that {
            X king is captured
         }
      }
  }
  </code></pre>