1,277
edits
Changes
no edit summary
{{code}}
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) {
{{notmine|Chanh Vo|fragment=yes}}
}
// @return an exact clone of "this" gameboard
public Gameboard clone() {
{{notmine|Chanh Vo|fragment=yes}}
}
// 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() {
{{notmine|Jordan Berk|fragment=yes}}
}
// 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) {
{{notmine|Jordan Berk|fragment=yes}}
}
// 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;
}
}
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) {
{{notmine|Chanh Vo|fragment=yes}}
}
// @return an exact clone of "this" gameboard
public Gameboard clone() {
{{notmine|Chanh Vo|fragment=yes}}
}
// 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() {
{{notmine|Jordan Berk|fragment=yes}}
}
// 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) {
{{notmine|Jordan Berk|fragment=yes}}
}
// 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;
}
}