Index: src/lib/ai.py
===================================================================
--- src/lib/ai.py	(revision 8388)
+++ src/lib/ai.py	(working copy)
@@ -359,6 +359,10 @@
         isSelf = player is self and self.moving
         self.moving = False
         self.connection.reportMove(move.canMove, isSelf)
+        
+    def onUndoMove(self):
+        """Called by game.ChessPlayer"""
+        self.connection.undoMove()
 
     def readyToMove(self):
         """Called by game.ChessPlayer"""
Index: src/lib/game.py
===================================================================
--- src/lib/game.py	(revision 8388)
+++ src/lib/game.py	(working copy)
@@ -104,6 +104,9 @@
         """
         pass
     
+    def onUndoMove(self):
+        pass
+    
     def onPlayerStartTurn(self, player):
         pass
 
@@ -169,6 +172,10 @@
         """
         self.__game.move(self, move)
         
+    def undo(self):
+        """Undo moves until it is this players turn"""
+        self.__game.undo(self)
+        
     def endMove(self):
         """Complete this players turn"""
         self.__game.endMove(self)
@@ -496,6 +503,35 @@
 
         self.endLock()
         
+    def undo(self, player):
+        if self.__inCallback:
+            self.__queuedCalls.append((self.undo, (player,)))
+            return
+        
+        self.startLock()
+        
+        # If current player undo oponents move and our move
+        if player is self.__currentPlayer:
+            count = 2
+        else:
+            count = 1
+            self.__currentPlayer = player
+            
+        for i in xrange(count):
+            self.__moves = self.__moves[:-1]
+            for player in self.__players:
+                player.onUndo()
+
+        # Inform other players of the result
+        for player in self.__players:
+            player.onPlayerStartTurn(self.__currentPlayer)
+
+        # Notify the next player they can move
+        if self.__started is True and self.result == RESULT_IN_PROGRESS:
+            self.__currentPlayer._setReadyToMove(True)               
+        
+        self.endLock()
+        
     def startLock(self):
         assert(self.__inCallback is False)
         self.__inCallback = True
Index: src/lib/cecp.py
===================================================================
--- src/lib/cecp.py	(revision 8388)
+++ src/lib/cecp.py	(working copy)
@@ -96,6 +96,10 @@
         """Stop the AI from automatically moving"""
         self.onOutgoingData('force\n')
         
+    def sendUndo(self):
+        """Undo the last move"""
+        self.onOutgoingData('undo\n')
+        
     def sendMovePrompt(self):
         """Get the AI to move for the current player"""
         self.onOutgoingData('go\n')
@@ -206,6 +210,11 @@
         # Prompt the AI to move
         self.sendMovePrompt()
         
+    def undoMove(self):
+        """Undo the last move made by this AI"""
+        self.sendWait()
+        self.sendUndo()
+
     def reportMove(self, move, isSelf):
         """Report the move the current player has made.
         
Index: src/lib/chess/board.py
===================================================================
--- src/lib/chess/board.py	(revision 8388)
+++ src/lib/chess/board.py	(working copy)
@@ -201,6 +201,9 @@
     
     # The move that got us to this state
     lastMove        = None
+    
+    # Pieces moved that got us to this state
+    moves           = None
 
     # If the last move was a pawn march the location where it can be taken by en-passant
     enPassantSquare = None
@@ -215,10 +218,11 @@
     
     # Flag to show if the previous move has caused a three fold repition
     threeFoldRepetition = False
-    
+
+    # Bitboards
     whiteBitBoard = 0
     blackBitBoard = 0
-    allBitBoard = 0
+    allBitBoard   = 0
 
     def __init__(self, lastState = None):
         """Constuctor for storing the state of a chess board.
@@ -243,6 +247,7 @@
             self.moveNumber = 0
             self.squares = {}
             self.casualties = []
+            self.moves = []
             self.whiteState = ChessPlayerState()
             self.blackState = ChessPlayerState()
             
@@ -251,6 +256,7 @@
             self.moveNumber = 0
             self.squares = {}
             self.casualties = []
+            self.moves = []            
             self.whiteBitBoard = 0
             self.blackBitBoard = 0
             self.allBitBoard = 0
@@ -275,6 +281,7 @@
             self.squares = lastState.squares.copy()
             self.casualties = lastState.casualties[:]
             self.lastMove = lastState.lastMove
+            self.moves = lastState.moves[:]
             self.enPassantSquare = lastState.enPassantSquare
             self.whiteState = ChessPlayerState(lastState.whiteState)
             self.blackState = ChessPlayerState(lastState.blackState)
@@ -352,8 +359,7 @@
 
             # See if this piece can take
             board = ChessBoardState(self)
-            move = board.movePiece(enemyPiece.getColour(), enemyCoord, location, testCheck = False, applyMove = False)
-            if move is not None:
+            if board.movePiece(enemyPiece.getColour(), enemyCoord, location, testCheck = False, applyMove = False):
                 return True
             
         return False
@@ -375,8 +381,7 @@
             for rank in 'abcdefgh':
                 for file in '12345678':
                     board = ChessBoardState(self)
-                    move = board.movePiece(colour, coord, rank + file, applyMove = False)
-                    if move is not None:
+                    if board.movePiece(colour, coord, rank + file, applyMove = False):
                         return True
 
         return False
@@ -693,6 +698,8 @@
             self.allBitBoard = allBitBoard
             
         else:
+            self.moves = result
+            
             # Remember the casualties
             if victim is not None:
                 self.casualties.append(victim)
@@ -867,12 +874,11 @@
         assert(self.__inCallback is False)
         
         state = ChessBoardState(self.__boardStates[moveNumber])
-        moves = state.movePiece(colour, start, end, promotionType = promotionType, allowSuicide = False)
-        if moves is None:
+        if not state.movePiece(colour, start, end, promotionType = promotionType, allowSuicide = False):
             return None
 
         victim = None
-        for (piece, start, end, delete) in moves:
+        for (piece, start, end, delete) in state.moves:
             # The victim is the enemy piece that has been deleted
             if delete and piece.getColour() != colour:
                 victim = piece
@@ -899,14 +905,23 @@
         if not test:
             self.__boardStates.append(state)
         move = Move()
-        move.moves = moves
+        move.moves = state.moves
         move.victim = victim
         move.opponentInCheck = state.inCheck(opponentColour)
         move.opponentCanMove = state.canMove(opponentColour)
         move.threeFoldRepetition = state.threeFoldRepetition
         move.fiftyMoveRule = state.fiftyMoveCount >= 50
         return move
+    
+    def undo(self):
+        """Undo the last move"""
+        undoState = self.__boardStates[-1]
+        self.__boardStates = self.__boardStates[:-1]
 
+        # Undo the moves
+        for (piece, start, end, delete) in undoState.moves:
+            self.__onPieceMoved(piece, end, start, False)
+
     def __str__(self):
         """Returns a representation of the current board state"""
         return str(self.__boardStates[-1])
Index: src/lib/uci.py
===================================================================
--- src/lib/uci.py	(revision 8388)
+++ src/lib/uci.py	(working copy)
@@ -116,6 +116,13 @@
             blackTime = 30000
             
         self.__sendCommand('go wtime %d btime %d' % (whiteTime, blackTime))
+        
+    def undoMove(self):
+        """
+        """
+        self.__sendCommand('stop');
+        (self.__positionCommand, _) = self.__positionCommand.rsplit(" ", 1)
+        self.__sendCommand(self.__positionCommand)        
 
     def reportMove(self, move, isSelf):
         """
@@ -125,7 +132,7 @@
         self.__haveMoves = True
         self.__positionCommand += ' ' + move
         self.__sendCommand(self.__positionCommand)
-        
+
     def parseLine(self, line):
         """
         """
