title: What is the best data-structure to represent a checkers board when speed is the primary concern?
body: <p>I am currently implementing something quite similar to checkers. So, I have this table game and there are both white and black pieces. Where there are neither white or black pieces, you dno't have pieces.</p>
  
  <p>I'm currently doing the <code>GetValidMoves()</code> method that'll return all the current moves one can do with the current board.</p>
  
  <p>I am thus wondering what might be the best way to represent the board. The naive approach would be to have a matrix with 0's 1's and 2's (for no piece, white piece and black piece).</p>
  
  <p>Other idea would be to instead of a matrix representation of the board, have 2 lists(or any other data-structure): one for black pieces, other for white.</p>
  
  <p>I am implementing this game to test some AI algorithms, so my main concern is speed. I will basically put 2 AI players playing each other, for each turn each player should have a list of all his valid moves and then he'll choose what move to do, this always happening until the game ends(some player wins or there's a tie).</p>
  
  <p>PS: I am not asking about the AI algorithm, I just want to know what would be the best data-structure to handle the board, so that it makes it easy to</p>
  
  <ol>
  <li>Look for all the valid moves for the current player</li>
  <li>Do a move</li>
  <li>Verify the game is not over (it is over when one player lost all his pieces or one player reached the other side of the board).</li>
  </ol>