Alpha-beta pruning

  1. Find some pseudo-code for alpha-beta pruning that you like. Study it. Understand it. (No, it is not acceptable to implement it without understanding it.)


  2. Write a Chess-playing artificial intelligence that implements minimax with alpha-beta pruning. To help you get started, here is some code to represent the state of the game: {C++ version, Java version}. (If you use another language, you are on your own. If you want to translate it into your favorite language and release it under the CC0 license, I will be happy to add it for the benefit of future generations.) Here is some example usage for the Java version. 
    ChessState s = new ChessState();             // Make a new state
s.resetBoard();                              // Initialize to starting setup
ChessMoveIterator it = s.iterator(true);     // Iterate over all valid moves
ChessState.ChessMove m;                      //  for the light player
while(it.hasNext()) {                        // Find the last valid move.
    m = it.next();                           // (Obviously, this is not
}                                            //  a great strategy.)
s.move(m.xSource, m.ySource, m.xDest, m.yDest); // Move the piece
int h = s.heuristic();                       // evaluate the state
s.printBoard(System.out);                    // print the board
    The C++ usage is similar: 
    GChessBoard board;                           // Make a new state
board.resetBoard();                          // Initialize to starting setup
GChessMoveIterator it;                       // Make an iterator
it.reset(&board, true);                      // Iterate over all valid moves
int xSrc, ySrc, xDest, yDest;                //  for the light player
int validMoves = 0;            
while(it.nextMove(&xSrc, &ySrc, &xDest, &yDest)) {
    validMoves++;                            // Count the valid moves
}
board.move(xSrc, ySrc, xDest, yDest);        // Move a piece
int h = board.heuristic();                   // Evaluate the state
board.printBoard(std::cout);                 // print the board


  3. Make a simple console interface. I know you really want to make an elegant GUI for this. You are welcome to do that too, but it will make the grader's job easier time if we all use a consistent interface. So, let's all use a simple console interface based on the "printBoard" method that I provided. Please:
    • Make your program accept two command-line arguments: 1- The look-ahead depth for the light player, and 2- The look-ahead depth for the dark player. As a special case, if the depth is 0, a human will play that side. For example:
      "java Chess 0 0" will be a game played by two humans,
      "java Chess 5 0" will be a game where light is played by the AI, and dark is played by a human,
      "java Chess 3 5" will be a game with two AI agents, but dark is smarter.
    • The light side always goes first.
    • Print the board before each move, whether the player is human or machine.
    • If the player is human, prompt with "Your move?". The human player should then enter a 4 character string and press Enter. For example, the string "b1c3" would move the piece at grid position B1 to grid position C3. (Internally, the positions are zero-indexed, so this would be 1,0 to 2,2.) If the move is invalid for any reason, say so, then prompt again. As a special case, if the user enters "q", just quit the game.
    • When the game ends, print "Light wins!" or "Dark wins!".
    (Please try to make it such that the grader can pipe a text file as input into your program to see if it behaves as expected. In other words, don't try to make your interface unique.)


  4. Make sure your build script contains a comment that tells the grader how to execute your program. Lines that begin with a '#' are comments. Use look-ahead depths of 3 and 5. Example build script: 
    javac *.java
#java Chess 3 5


  5. Zip or tarball your source code in the usual manner. Don't include any generated binary files in your archive. Click on the "Project submission" link on the main class page to submit your archive file. If you have any difficulties with the submission server, please e-mail your submission directly to the grader.






FAQ:

  1. Q: In its long history, Chess has accumulated many obscure rules. Do I have to support them?
    A: No.
    • You do not need to make the computer announce "check" when it is possible to capture your king in one move. (If you don't see that coming, you need more practice anyway.)
    • You do not need to detect the condition of "checkmate"--you may simply end the game when the king is captured. (So the game lasts one move longer--not a big deal.)
    • You do not have to handle any of the many rules pertaining to stale-mate.
    • You do not need to support castling. It follows that you certainly do not need to support vertical castling.
    • You do not need to support en passant.
    • You do not need to worry about repeating states. The pursuer does not have to relent.
    • You do not have to move the first piece you accidentally touch. (Calling that rule just reveals that you would rather win on a technicality than face intellectual competition.)
    • You do not need to support the possibility of promoting a pawn to a non-queen piece.
    • You do not need to do anything special if the kings ever face each other. (That's more of a Chinese Chess rule, anyway.)
    • etc.
    One may argue that without all these rules, the game is not really Chess. That's fine with me. You may call it "Schmess" if it makes you feel better.


  2. Q: All my pieces suddenly disappeared! What happened?
    A: When the king is captured, all the pieces on its team are automatically captured as well. This ensures that the AI views immediately taking the king to be as good as systematically capturing all the pieces before taking the king. Otherwise, the AI becomes a cruel opponent who systematically assassinates your pieces for points, while keeping your king trapped for a future regicide.


  3. Q: In Java, where do I get a PrintStream to pass to the ChessState.printBoard method?
    A: You probably want to pass "System.out" as this parameter.


  4. Q: The computer keeps moving pieces back and forth in an endless manner.
    A: The small random component added to the heuristic is supposed to fix that. Are you instantiating a new random number generator each time you need a random number? The Java random number generator picks a seed based on the product of the current time (in seconds) and the process ID. Since it is unlikely that an entire second has passed since the previous time you needed a random number, and since the process ID does not change, this effectively creates the same sequence of "random numbers" over and over ...which is not at all random. Your program should only instantiate ONE random number generator.