backgammonboard.java

人工智能_bachgammonagent

    }

    // Get moves when using doubles, reduce repetitions of moves.
    // s_pos is position to start trying moves from.
    // Start at 0/NUM_POINTS and increase/decrease from there.
    // Does not guarrantee maximum number of dice is used.
    private MoveSet getValidMovesDoublesRec(Move current_move, int player, int dice_left, int[] dice, int s_pos) {
	// Do not make a move that is "before" the move of one at a previous recursive level.
	MoveSet rtn_mset = new MoveSet();
	int p_type = pType(player);
	if (dice_left==0) {
	    // Stop if we're out of dice, return the current move.
	    rtn_mset.add(current_move);
	} else {
	    // Find all atomic moves with first die in list.
	    int the_die = dice[dice_left-1];
	    boolean moved=false;
	    // For player 0, run from s_pos down to 0, for player 1, run from s_pos up to NUM_POINTS-1.
	    for (int b_loc=s_pos; b_loc<NUM_POINTS && b_loc>=0; b_loc+=p_type) {
		// Check that the player has a checker here, and that
		// it can move it the_die spaces.
		if (board[b_loc]*p_type>0 && isValidMove(b_loc,the_die,player)) {
		    moved = true;
		    Move rec_move = (Move) current_move.clone();

		    // For each such move, make a recursive call with
		    // that atomic move added to the move, with an
		    // updated board.
		    int to_loc = b_loc+p_type*the_die;
		    if (to_loc>NUM_POINTS) {
			to_loc = NUM_POINTS;
		    } else if (to_loc<-1) {
			to_loc = -1;
		    }
		    AtomicMove a_move = new AtomicMove(b_loc, to_loc);
		    rec_move.addMove(a_move);
		    BackgammonBoard rec_board = (BackgammonBoard) this.clone();
		    rec_board.applyAtomicMove(player,a_move);
		    MoveSet rec_mset = rec_board.getValidMovesDoublesRec(rec_move,player,dice_left-1,dice,b_loc);

		    // Add rec_mset to rtn_mset.
		    rtn_mset.addSet(rec_mset);
		}
	    }
	    // Check the bar.
	    int bar_loc = player==0 ? BAR_LOC0 : BAR_LOC1;
	    if (on_bar[player] > 0 && isValidMove(bar_loc,the_die,player)) {
		// Same as above, with bar location.
		moved = true;
		Move rec_move = (Move) current_move.clone();

		AtomicMove a_move = new AtomicMove(bar_loc, bar_loc+p_type*the_die);
		rec_move.addMove(a_move);
		BackgammonBoard rec_board = (BackgammonBoard) this.clone();
		rec_board.applyAtomicMove(player,a_move);
		// TO DO:: Could do the bar moves non-duplicate using s_pos too.
		MoveSet rec_mset = rec_board.getValidMovesDoublesRec(rec_move,player,dice_left-1,dice,s_pos);
		rtn_mset.addSet(rec_mset);
	    }
	    if (!moved && current_move.getNumAtomicMoves()>0) {
		rtn_mset.add(current_move);
	    }
	}
	return rtn_mset;
    }


    // Find all moves possible on current board, append to current_move.
    // Assumes dice are sorted in non-decreasing order, we will find
    // moves starting with largest die first.
    // TO DO:: Slow because of clone calls?  Just modify board??
    // Note: could use the "not before", but it gets tricky with the "use some dice" rule.
    private MoveSet getValidMovesRec(Move current_move, int player, int dice_left, int[] dice) {
	MoveSet rtn_mset = new MoveSet();
	int p_type = pType(player);
	if (dice_left==0) {
	    // Stop if we're out of dice, return the current move.
	    rtn_mset.add(current_move);
	} else {
	    // Find all atomic moves with first die in list.
	    int the_die = dice[dice_left-1];
	    boolean moved=false;
	    for (int b_loc=0; b_loc<NUM_POINTS; b_loc++) {
		// Check that the player has a checker here, and that
		// it can move it the_die spaces.
		if (board[b_loc]*p_type>0 && isValidMove(b_loc,the_die,player)) {
		    moved = true;
		    Move rec_move = (Move) current_move.clone();

		    // For each such move, make a recursive call with
		    // that atomic move added to the move, with an
		    // updated board.
		    int to_loc = b_loc+p_type*the_die;
		    if (to_loc>NUM_POINTS) {
			to_loc = NUM_POINTS;
		    } else if (to_loc<-1) {
			to_loc = -1;
		    }
		    AtomicMove a_move = new AtomicMove(b_loc, to_loc);
		    rec_move.addMove(a_move);
		    BackgammonBoard rec_board = (BackgammonBoard) this.clone();
		    rec_board.applyAtomicMove(player,a_move);
		    MoveSet rec_mset = rec_board.getValidMovesRec(rec_move,player,dice_left-1,dice);

		    // Add rec_mset to rtn_mset.
		    rtn_mset.addSet(rec_mset);
		}
	    }
	    // Check the bar.
	    int bar_loc = player==0 ? BAR_LOC0 : BAR_LOC1;
	    if (on_bar[player] > 0 && isValidMove(bar_loc,the_die,player)) {
		// Same as above, with bar location.
		moved = true;
		Move rec_move = (Move) current_move.clone();

		AtomicMove a_move = new AtomicMove(bar_loc, bar_loc+p_type*the_die);
		rec_move.addMove(a_move);
		BackgammonBoard rec_board = (BackgammonBoard) this.clone();
		rec_board.applyAtomicMove(player,a_move);
		MoveSet rec_mset = rec_board.getValidMovesRec(rec_move,player,dice_left-1,dice);
		rtn_mset.addSet(rec_mset);
	    }

	    // If we didn't find any atomic moves, just add the current move.
	    if (!moved) {
		if (current_move.getNumAtomicMoves()!=0) {
		    rtn_mset.add(current_move);
		}
	    }
	}
	return rtn_mset;
    }


    /* Returns true iff player has won. */
    public boolean hasWon(int player) {
	return in_home[player] == CHECKERS_PER_PLAYER;
    }

    /* Print a visualization of the board to out_stream */
    public void showBoard() {
        int absx;
        int [][] dummy;

        dummy = new int [20][24];

        for (int i = 0; i < 20; i++)
            for (int j = 0; j < 24; j++)
                dummy[i][j] = 0;

        for (int j = 0; j < 12; j++) {
            absx = board[j] >= 0 ? board[j] : -board[j];
            for (int i = 0; i < absx; i++)
                if (board[j] > 0)
                    dummy[19 - i][22 - 2 * j] = 1;
                else
                    dummy[19 - i][22 - 2 * j] = -1;
        }

        for (int j = 0; j < 12; j++) {
            absx = board[j + 12] >= 0 ? board[j+12] : -board[j+12];
            for (int i = 0; i < absx; i++)
                if (board[j+12] > 0)
                    dummy[i][2*j] = 1;
                else
                    dummy[i][2*j] = -1;
        }

        out_stream.println();

        // Print point numbers.
        out_stream.println("12 13 14 15 16 17 18 19 20 21 22 23");
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < 24; j++) {
                if (dummy[i][j] == 1) {
                    out_stream.print("O");
                } else if (dummy[i][j] == -1) {
                    out_stream.print("X");
                } else {
                    out_stream.print("_");
                }
                if (j % 2==1) {
                    out_stream.print(" ");
                }


            }
            out_stream.println();
        }

        // Print point numbers.
        out_stream.println("11 10 09 08 07 06 05 04 03 02 01 00");

        out_stream.println("Player X on bar: " + on_bar[0] + "  in home: " + in_home[0]);
        out_stream.println("Player O on bar: " + on_bar[1] + "  in home: " + in_home[1]);

        out_stream.println();
        System.out.flush();
    }

    // Checks if player can start "bearing off" (moving checkers into home).
    private boolean canBearOff(int player) {
        boolean can_off = true;

        if (player==0) {
            for (int loc=6; loc < NUM_POINTS; loc++) {
                can_off = can_off & board[loc]>=0;
            }
        } else {
            for (int loc=0; loc < NUM_POINTS-6; loc++) {
                can_off = can_off & board[loc]<=0;
            }
        }

        return can_off;
    }

    // Assumes there is one of player's tiles at space.
    private boolean isValidMove(int space, int steps, int player) {
        boolean is_valid = true;
        int p_type = pType(player);

	// Can't move other tiles unless bar is clear.
	if (on_bar[player]>0 && ((space != BAR_LOC0 && player==0) || (space != BAR_LOC1 && player==1))) {
	    return false;
	}

        // Check not a move into home without proper positioning of tiles.
        // Bounds check for next step happens here.
        int move_to = space+steps*p_type;
        if (move_to < 0 | move_to > NUM_POINTS-1) {
            // Assumes moves are positive.
            is_valid = is_valid & canBearOff(player);
        } else {
            // Check no opponent's block there.
            if (board[move_to]*(-p_type) >= 2) {
                is_valid = false;
            }
        }

        return is_valid;
    }
}