tictactoemodel.java

TieTaeToe,外國的五子棋。初學者必看

package ticTacToe;

/** Maintains a square board of squares.
 * 
 * <p>Objects of this class encapsulte both the board and
 * the strategy of one player of a game of TicTacToe.
 * <p>
 * The rules of the game are this
 * <ul>
 *    <li>The game is played on a board that is TicTacToeModel.SIZE
 *    by TicTacToeModel.SIZE squares.
 *    <li>There are two players, player X and player O. The role of 
 *    player O is taken by this class.
 *    <li>Each square is coloured with one of three
 *     integer values:  TicTacToeModel.BLANK, TicTacToeModel.O,
 *      of TicTacToeModel.X.
 *    <li>Player X goes first and players alternate until either
 *    there is a winner or no square is blank.
 *    <li>On player X's move, player X places an X on a blank square.
 *    On player O's move, player O places an O on a blank square.
 *    <li>There is a winner as soon as one player has
 *    TicTacToeModel.GOAL contiguous pieces horizontally,
 *    vertically, or diagonally.
 *    <li>If no player can move, the game is tied.
 *    
 * </ul>
 * <p>As an invariant, there is at most one winning sequence. Once the
 * game has one winning sequence, no more moves can be made until the game
 * is reset.
 * 
 * @author Theodore Norvell
 *
 */
public class TicTacToeModel {
    public static final int X = +1 ;
    public static final int O = -1 ;
    public static final int BLANK = 0 ;
    /** The size of one side of the board. */
    public static final int SIZE = 10 ;
    /** The number of squares in a row one needs to win. */
    public static final int GOAL = 5 ;
    
    private int[][] board = new int[SIZE][SIZE] ;
    
    /** Reset the game to its initial state.*/
    public void reset() {
    	for(int i=0 ; i<SIZE ; ++i ) {
    		for( int j=0 ; j<SIZE ; ++j ) {
    			board[i][j] = BLANK ; } }
    }
    
    /** Get the value of a square
     * <p><b>Precondition:</b> 0 &lt;= i &amp;&amp i &lt; SIZE
     * <p><b>Precondition:</b> 0 &lt;= j &amp;&amp j &lt; SIZE
     * @param i
     * @param j
     * @return the value of square (i,j)
     */
    public int get(int i, int j) {
    	assert 0 <= i && i < SIZE && 0 <= j && j < SIZE ;
    	return board[i][j] ; }
    
    /** Place an X on a square
     * <P> If possible, the object also places an O
     * on a previously blank square.
     * <p><b>Precondition:</b> 0 &lt;= i &amp;&amp i &lt; SIZE
     * <p><b>Precondition:</b> 0 &lt;= j &amp;&amp j &lt; SIZE
     * <p>If the square is blank, or there is already a winner, no
     * move is made. If the X move is a winner or takes the last square,
     * then no reply is made.
     * @param i
     * @param j
     */
    public void placeX( int i, int j ) {
    	assert 0 <= i && i < SIZE && 0 <= j && j < SIZE ;
    	if( winner() != BLANK ) return ;
    	else if( board[i][j] != BLANK ) return ;
    	board[i][j] = X ;
    	if( winner() != BLANK ) return ;
    	
    	Pair p = getMoveForO( ) ;
    	if( p != null ) {
    		board[p.i][p.j] = O ; }
    }
    
    /** Report whether there is a winner and who it is.
     * 
     * @return TicTacToeModel.BLANK if there is no winner.
     * Otherwise returns the colour of the winner, either
     * TicTacToeModel.X or TicTacToeModel.O.
     */
    public int winner() {
    	int[] delta_i = {0, +1, +1, +1 } ;
    	int[] delta_j = {+1, 0, +1, -1 } ;
    	// For each position
    	for( int i=0 ; i < SIZE ; ++i ) {
    		for( int j=0 ; j < SIZE ; ++j ) {
    			if( board[i][j]==BLANK ) continue ;
    			// For each direction
    			for( int dir = 0 ; dir < 4 ; ++dir ) {
    				// Check if there are GOAL squares in a row
    				// starting at (i,j) and proceeding in direction dir.
    				boolean found = true ;
    				int i0 = i, j0 = j ;
    				for( int k=1 ; k < GOAL ; ++k ) {
    					i0 += delta_i[ dir ] ;
    					j0 += delta_j[ dir ] ;
    					if( i0 == SIZE || j0 == SIZE || j0 == -1
    				    || board[i0][j0] != board[i][j] ) {
    						found=false ;
    						break ; } }
    				if( found ) {
    					// We have a winner.
    					return board[i][j] ; } } } }
    	return BLANK ;
    }
    
    /** Find a move for O.
     * @return Returns null if there is no blank square.
     * Otherwise returns the coordinates of a blank square.
     */
    private Pair getMoveForO() {
    	// Find the square that gives the lowest value
        // according to the value function.
        Pair bestYet = null ;
        int bestYetValue = 1000000000 ;
    	for( int i=0 ; i < SIZE ; ++i ) {
    		for( int j=0 ; j < SIZE ; ++j ) {
    			if( board[i][j] == BLANK ) {
                    board[i][j] = O ;
                    int value = value() ;
                    if( value < bestYetValue ) {
                        bestYet = new Pair(i,j) ;
                        bestYetValue = value; }
                    board[i][j] = BLANK ; } } }
    	return bestYet ;
    }
    
    /** Estimate the value of each board.
     * <P> The more positive the value, the better the position is
     * judged to be for X. The more negative, the better the position
     * is jusdged to be for 0.
     * <p> By the way, as a software desgin note, I should
     * probably split this class into two parts.  One
     * part for board representation and one for strategy.
     * Perhaps I'll do that when I find some time.
     * @return
     */
    private int value() {
        int winner = winner() ;
        if( winner == O ) return -1000000000 ;
        if( winner == X ) return [phone] ;
        int result = 0 ;
        int[] delta_i = {0, +1, +1, +1 } ;
        int[] delta_j = {+1, 0, +1, -1 } ;
        // For each position
        for( int i=0 ; i < SIZE ; ++i ) {
            for( int j=0 ; j < SIZE ; ++j ) {
                if( board[i][j]==BLANK ) continue ;
                // For each direction
                for( int dir = 0 ; dir < 4 ; ++dir ) {
                    // Check if there are GOAL squares in a row
                    // starting at (i,j) and proceeding in direction dir
                    // Count the Xs Os and BLANKs in the set.
                    int OCount = 0 ;
                    int XCount = 0 ;
                    int BCount = 0 ;
                    int i0 = i, j0 = j ;
                    for( int k=0 ; k < GOAL ; ++k ) {
                        if( i0 == SIZE || j0 == SIZE || j0 == -1 ) break ;
                        switch( board[i0][j0] ) {
                        case O: OCount += 1 ; break ;
                        case X: XCount += 1 ; break ;
                        case BLANK: BCount += 1 ; break ; }
                        i0 += delta_i[ dir ] ;
                        j0 += delta_j[ dir ] ; }
                    // If the sum is less than the goal,
                    // then we hit an edge and can ignore
                    // this sequence of squares.
                    if( OCount+XCount+BCount<GOAL ) continue ;
                    // If there are both Xs and Os, then
                    // no one will ever win in this seqence.
                    if( OCount !=0 && XCount != 0 ) continue ;
                    // This is a potential future win.
                    // The fewer the blanks the better it
                    // is and the more (in absolute) we add to the
                    // result.  I figure we can add 1, 4, 9, 16, etc
                    // for 1, 2, 3, 4 Xs or Os.
                    result += X*XCount*XCount + O*OCount*OCount ;  } } }
        return result ;
    }
    
    /** Represent the coordinates of a square.*/
    private class Pair {
    	final int i, j ;
    	
    	Pair(int i, int j) { this.i = i ; this.j = j ; }
    }
}