Computer Science/61b/Projects/Network/player/Gameboard.java

This page contains computer code. Unlike all articles on the lensowiki, which are released under the GFDL, this code is released under the GPL.

Copyright 2006, 2007 Paul Borokhov. All rights reserved.

This code is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

The code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

package player;

/* Gameboard class
 * contains the gameboard ADT and methods for handling it
 * in addition, contains methods for generating and evaluating new moves
**/

public class Gameboard {
	
	// Allows for a hypothetical expansion of the board
	public final static int DIMENSION = 8;
	public final static int ADD = 1;
	public final static int STEP = 2;
	// used for signaling a white/black win; needs to be large and prime
	public final static int WHITEWIN = 2047;
	public final static int BLACKWIN = -2047;
	
	private Chip[][] board = new Chip[DIMENSION][DIMENSION];
	private int x = DIMENSION;
	private int y = DIMENSION;
	private int pieces;
	
	// returns the Chip at a given x & y coord
	/* we use a "try" so that if we try to access a location that is off the board,
		i.e. we attempt to get non-existent coords, then just return null */
	public Chip cellContents(int x, int y) {
		try {
		return board[x][y];
		} catch (ArrayIndexOutOfBoundsException e) {
			return null;
		}
	}
	
	/** @return an array of Chip neighbors around a given position (x,y) **/
	public Chip[] neighborarray(int x, int y) {
		Chip[] array = new Chip[8];
		array[0] = cellContents(x-1, y-1); // nw
		array[1] = cellContents(x, y-1); // n
		array[2] = cellContents(x+1, y-1); // ne
		array[3] = cellContents(x+1, y); // e
		array[4] = cellContents(x+1, y+1); // se
		array[5] = cellContents(x, y+1); // s
		array[6] = cellContents(x-1, y+1); // sw
		array[7] = cellContents(x-1, y); // w
		return array;
	}
	
	/** takes in rec = 1 on initial search
		@return the number of the same-color neighbors around a given position (x, y) **/
	public int neighbor(int color, int x, int y, int rec) {
		if (rec < 0) {
			return 0;
		} else {
			Chip[] array = neighborarray(x, y);
			int number = 0;
			for (int i=0; i<array.length; i++) {
				Chip target = array[i];
				if (target != null && target.getColor()==color) {
					number = number + neighbor(color, target.getX(), target.getY(), rec-1);
					number++;
				}
			}
			return number;
		}
	}
	
	/* inserts a chip of the given color at (x, y) if this is acceptable
		returns true if the insertion is legal, false otherwise */
	public boolean insertChip(int color, int x, int y) {
		if (validMove(color, new Move(x, y))) {
			board[x][y] = new Chip(color, x, y);
			pieces++;
			return true;
		} else {
			return false;
		}
	}
	
	/* moves Chip c to a new location at (x, y)
		returns true if the move is legal, false otherwise */
	public boolean moveChip(Chip c, int x, int y) {
		if (validMove(c.getColor(), new Move(x, y))) {
			board[c.getX()][c.getY()] = null;
			board[x][y] = new Chip(c.getColor(), x, y);
			return true;
		} else {
			return false;
		}
	}
	
	/* performs the requested move for a player of the given color
		returns true if the move is legal, false otherwise */
	public boolean performMove(int color, Move m) {
		if (m.moveKind == Move.ADD) {
			return insertChip(color, m.x1, m.y1);
		} else if (m.moveKind == Move.STEP) {
			return moveChip(retrieveChip(m.x2, m.y2), m.x1, m.y1);
		} else {
			return true;
		}
	}
	
	// legacy method for returning a chip at (x, y)
	public Chip retrieveChip(int x, int y) {
		return cellContents(x, y);
	}
	
	/**	Verifies that a given move is valid for a plyer of the given color.
		* the following conditions must be met:
		* No chip may be placed in any of the four corners
		* No chip may be placed in a goal of the opposite color
		* No chip may be placed in a square that is already occupied
		* A player may not have more than two chips in a connected group, whether connected orthogonally or diagonally
		takes a move and the player's color performing the move
		@return true if move is valid
	*/
	public boolean validMove(int color, Move m) {
		if (m.moveKind == Move.QUIT) {
			return true;
		} else {
			if ((m.x1==0 && (m.y1==0 || m.y1==DIMENSION-1)) || (m.y1==DIMENSION-1 && (m.x1==0 || m.x1==DIMENSION-1))) {
				return false; // in the corners
			} else if (board[m.x1][m.y1] != null) {
				return false; // target cell isn't empty
			} else if (((color == Chip.BLACK) && (m.x1==0 || m.x1==DIMENSION-1)) || ((color == Chip.WHITE) && (m.y1==0 || m.y1==DIMENSION-1))) {
				return false; // target cell is in opponent's goal
			} else if (!checkClusterSize(color, m.x1, m.y1)) {
				return false; // resulting cluster too big
			} else {
				return true; // looks like this move is good
			}
		}
	}
	
	// helper method for validMove()
	// @return true if an insertion at the given position is possible w/respect to cluster size; false otherwise
	public boolean checkClusterSize(int color, int x, int y) {
		if (neighbor(color, x, y, 1) > 1) {
			return false;
		} else {
			return true;
		}
	}
	
	// generates a 2-d array of moves and resulting gameboards for a given color
	// @return[0] is an array of Gameboards (Gameboard[x])
	// @return[1] is an array of Moves corresponding to each board in return[0] (Move[x])
	// thus the board after performing g.performMove(color, return[1][i]) is return[0][i]
	public Object[][] generateMoves(int color) {
	

The author of this code fragment is Chanh Vo; consequently, I cannot make it freely available.

	}
	
	// @return an exact clone of "this" gameboard
	public Gameboard clone() {
	

The author of this code fragment is Chanh Vo; consequently, I cannot make it freely available.

	}
	 	
	// return the current Move kind for this gameboard, depending on number of pieces
	// @return either STEP or ADD
	public int moveKind() {
		if (pieces < 20) {
			return ADD;
		} else {
			return STEP;
		}
	}
	
	/* chooses a move to a given depth for a given color using alpha-beta pruning (hopefully)
	/ first two moves involve the random placement of a chip in each of the goals without any analysis
	/ @param color - current player's color
		depth - number of levels remaining to search (i.e. depth = 1 means no look-ahead)
		alpha, beta - best-case and worst-case scores
		side - true for white, false for black
		factor - multiplier used to score a win many levels down lower than a win in the first level
	/ @return an Alphamove with the best move and its corresponding score */
	public Alphamove chooseMove(int color, int depth, int alpha, int beta, boolean side, int factor) {
		Alphamove bestme = new Alphamove();
		Alphamove bestopp;
		if (side) {
			bestme.score = alpha;
		} else {
			bestme.score = beta;
		}
		if (pieces < 2) { // first move for each color
						  // place a random piece in the top (black) or left (white) goal
			int target = (((int) (Math.random() * 10.0)) % (DIMENSION - 2)) + 1;
			if (color == Chip.BLACK) {
				bestme.move = new Move(target, 0);
			} else {
				bestme.move = new Move(0, target);
			}
			return bestme;
		} else if (pieces < 4) { // second move for each color
								 // place a random piece in the bottom (black) or right (white) goal
			int target = (((int) (Math.random() * 10.0)) % (DIMENSION - 2)) + 1;
			if (color == Chip.BLACK) {
				bestme.move = new Move(target, DIMENSION-1);
			} else {
				bestme.move = new Move(DIMENSION-1, target);
			}
			return bestme;
		} else {
			// at least 4 pieces are on the board now, so this is the 3rd+ move
			// go ahead and generate the possible moves from the current board
			Object[][] arr = generateMoves(color);
			if (depth == 1) {
				// this is our last level, so end the recursion
				for (int i=0; i<arr[0].length; i++) {
					if (arr[0][i] != null) {
						Move targetmove = (Move) arr[1][i];
						int score = ((Gameboard) arr[0][i]).winner()*factor;
						System.out.println("Got score " + score + " for board " + ((Gameboard) arr[0][i]) + ", factor " + factor);
						if ((((score/factor)==WHITEWIN) && (color==Chip.WHITE)) || (((score/factor)==BLACKWIN) && (color==Chip.BLACK))) {
							// we've reached a winner, so stop here and return it
							bestme.score = score;
							bestme.move = targetmove;
							return bestme;
						} else if ((score > bestme.score && side) || (score < bestme.score && !side)) {
							bestme.score = score;
							bestme.move = targetmove;
						}
					} else { // we've run out of moves to evalute; stop
						break;
					}
				}
				return bestme;
			} else {
				for (int ii=0; ii<arr[0].length; ii++) {
					if (arr[0][ii] != null) {
						// eventually, this is where we will check to make sure we still have enough time
						System.out.println("side: " + side);
						Move targetmove = (Move) arr[1][ii];
						int score = ((Gameboard) arr[0][ii]).winner()*factor;
						if (depth ==2) { System.out.println("Got score " + score + " for board " + ((Gameboard) arr[0][ii]) + ", factor " + factor); }
						if ((((score/factor)==WHITEWIN) && (color==Chip.WHITE)) || (((score/factor)==BLACKWIN) && (color==Chip.BLACK))) {
							// we've reached a winner, so stop here and return it
							bestme.score = score;
							bestme.move = targetmove;
							return bestme;
						} else {
							bestopp = ((Gameboard) arr[0][ii]).chooseMove(generateOpponent(color), depth-1, alpha, beta, !side, factor-1); //hopefully we never search for more than 9 levels...
							System.out.println("Opponent's best response is " + bestopp.score + ", current best score is " + bestme.score + " (side && (bestopp.score > bestme.score)) returns " + (side && (bestopp.score > bestme.score)) + " for side = " + side);
							targetmove = (Move) arr[1][ii];
							if (side && (bestopp.score > bestme.score)) {
								bestme.move = targetmove;
								bestme.score = bestopp.score;
								alpha = bestopp.score;
								System.out.println("Found better move for white, score is " + bestopp.score + " move is " + bestme.move);
							} else if (!side && (bestopp.score < bestme.score)) {
								bestme.move = targetmove;
								bestme.score = bestopp.score;
								beta = bestopp.score;
								// System.out.println("Found better move for black, score is " + bestopp.score);
							} if (alpha >= beta) {
								return bestme;
							}
						}
					} else { // we've run out of moves to evalute; stop
						break;
					}
				}
				return bestme;
			}
		}
	}
	
	// returns the best possible move that can be made by the given color to a search depth of "depth" using the "this" board
	// @return the best current Move
	public Move evalTree(int color, int depth) {
		int alpha = (BLACKWIN*10)-1;
		int beta = (WHITEWIN*10)+1;
		boolean side;
		if (color == Chip.BLACK) {
			side = false;
		} else { 
			side = true;
		}
		Alphamove winningmove = this.chooseMove(color, depth, alpha, beta, side, 10);
		return winningmove.move;
	}
	
	// simple method to generate the opponent's color
	// given a color, @return the color of the opponent
	public static int generateOpponent(int color) {
		if (color == Chip.WHITE) {
			return Chip.BLACK;
		} else {
			return Chip.WHITE;
		}
	}
	
	// evaluates the given network for a winning color
	// returns a probability of winning if there is no win (positive for white advantage, negative for black advantage)
	// returns WHITEWIN if WHITE wins, BLACKWIN if BLACK wins
	// @return an int with this board's score
	public int winner() {
	

The author of this code fragment is Jordan Berk; consequently, I cannot make it freely available.

	}
	
	// helper function for winner - recursively finds networks and assigns 1 point per connection and 10000 for a win
	// @return an int with the score of the network
	int findNetwork(Gameboard g, int x, int y, int color, int num, String currentDirection, String lastDirection) {
	

The author of this code fragment is Jordan Berk; consequently, I cannot make it freely available.

	}
	
	// debugging method to print a gameboard
	// @return a string represeting the board
	public String toString() {
		String output = "\n|";
		for (y=0; y<DIMENSION; y++) {
			for (x=0; x<DIMENSION; x++) {
				if (board[x][y] == null) {
					output = output + " .";
				} else {
					output = output + " " + ((Chip) board[x][y]).getColor();
				}
			}
			output = output + "|\n|";
		}
		return output;
	}
}