carfield.com.hk
Chess$aMove.class
2000-06-01T16:00:00Z
2000-06-01T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-06-01T16:00:00Z
Chess.class
2000-06-01T16:00:00Z
2000-06-01T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-06-01T16:00:00Z
Chess.java
2000-06-01T16:00:00Z
2000-06-01T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">import java.util.*;
import java.io.*;
public class Chess extends GameSearch {
/**
* Notes: PROGRAM false -1, HUMAN true 1
*/
/**
* PUBLIC API (mostly fromGameSearch)
*/
public boolean drawnPosition(Position p) {
/**
* We want to keep searching:
*/
return false;
}
public boolean wonPosition(Position p, boolean player) {
// evetually, we should check for checkmates here...
return false;
}
public float positionEvaluation(Position p, boolean player) {
ChessPosition pos = (ChessPosition)p;
int [] b = pos.board;
float ret = 0.0f;
// adjust for material:
for (int i=22; i<100; i++) {
if (b[i] != 0 && b[i] != 7) ret += b[i];
}
// adjust for positional advantages:
setControlData(pos);
int control = 0;
for (int i=22; i<100; i++) {
control += humanControl[i];
control -= computerControl[i];
}
// Count center squares extra:
control += humanControl[55] - computerControl[55];
control += humanControl[56] - computerControl[56];
control += humanControl[65] - computerControl[65];
control += humanControl[66] - computerControl[66];
control /= 10.0f;
ret += control;
// credit for attacked pieces:
for (int i=22; i<100; i++) {
if (b[i] == 0 || b[i] == 7) continue;
if (b[i] < 0) {
if (humanControl[i] > computerControl[i]) {
ret += 0.9f * value[-b[i]];
}
}
if (b[i] > 0) {
if (humanControl[i] < computerControl[i]) {
ret -= 0.9f * value[b[i]];
}
}
}
// adjust if computer side to move:
if (!player) ret = -ret;
return ret;
}
public void printPosition(Position p) {
System.out.println("Board position:");
ChessPosition pos = (ChessPosition)p;
int [] b = pos.board;
for (int col=92; col>=22; col-=10) {
System.out.println();
for (int ii=0; ii<8; ii++) {
int i = ii + col;
if (b[i] != 0) {
System.out.print(pp(b[i], i));
} else {
boolean white_sq = true;
for (int k=0; k<blackSquares.length; k++) {
if (i == blackSquares[k]) {
white_sq = false;
break;
}
}
if (white_sq) System.out.print(" ");
else System.out.print(" . ");
}
}
}
System.out.println();
}
private String pp(int piece, int square_index) {
if (piece == 0) return " ";
String color;
if (piece < 0) color = "B"; else color = "W";
int p = piece; if (p < 0) p = -p;
switch (p) {
case 1: return " " + color + "P";
case 2: return " " + color + "N";
case 3: return " " + color + "B";
case 4: return " " + color + "R";
case 5: return " " + color + "Q";
case 9: return " " + color + "K";
}
return "error";
}
public Position [] possibleMoves(Position p, boolean player) {
if (GameSearch.DEBUG) System.out.println("posibleMoves("+p+","+player+")");
ChessPosition pos = (ChessPosition)p;
//System.out.println("Chess.possibleMoves(): pos=" + pos);
//for (int i=22; i<40; i++) System.out.println(pos.board[i]);
int num = calcPossibleMoves(pos, player);
if (num == 0) {
System.out.println("Stalemate");
System.exit(0);
}
ChessPosition [] chessPos = new ChessPosition[num];
for (int i=0; i<num; i++) {
chessPos[i] = new ChessPosition();
for (int j=22; j<100; j++) chessPos[i].board[j] = pos.board[j];
chessPos[i].board[possibleMoveList[i].to] = chessPos[i].board[possibleMoveList[i].from];
chessPos[i].board[possibleMoveList[i].from] = 0;
}
return chessPos;
}
public Position makeMove(Position p, boolean player, Move move) {
if (GameSearch.DEBUG) System.out.println("Entered Chess.makeMove");
ChessMove m = (ChessMove)move;
ChessPosition pos = (ChessPosition)p;
ChessPosition pos2 = new ChessPosition();
for (int i=0; i<120; i++) pos2.board[i] = pos.board[i];
int pp;
if (player) pp = 1;
else pp = -1;
if (GameSearch.DEBUG) System.out.println("makeMove: m.from = " + m.from +
", m.to = " + m.to);
pos2.board[m.to] = pos2.board[m.from];
pos2.board[m.from] = 0;
return pos2;
}
public boolean reachedMaxDepth(Position p, int depth) {
if (depth < 5) return false;
return true;
}
private BufferedReader in = null;
public Move getMove() {
if (GameSearch.DEBUG) System.out.println("Enter blank square index [0,8]:");
ChessMove mm = new ChessMove();
System.out.println("enter a move like 'd2d4' or 'oo'");
try {
if (in == null) {
in = new BufferedReader(new InputStreamReader(System.in));
}
String s = in.readLine().toLowerCase();
System.out.println("s="+s);
char c0 = (char)(s.charAt(0) - 'a' + 2);
char r0 = (char)(s.charAt(1) - '1' + 2);
char c1 = (char)(s.charAt(2) - 'a' + 2);
char r1 = (char)(s.charAt(3) - '1' + 2);
mm.from = r0*10+c0;
mm.to = r1*10+c1;
System.out.println("From " + mm.from + ", to " + mm.to);
} catch (Exception e) { System.out.println(e); }
return mm;
}
static public void main(String [] args) {
ChessPosition p = new ChessPosition();
for (int i=0; i<120; i++) p.board[i] = initialBoard[i];
Chess ttt = new Chess();
/* DEBUG*/ // ttt.setControlData(p);
ttt.playGame(p, true);
}
/**
* PRIVATE API, mostly chess move and evaluation utilities
*/
// static data that can be re-used (assume single threading!)
static private float [] computerControl = new float[120];
static private float [] humanControl = new float[120];
private void setControlData(ChessPosition pos) {
for (int i=0; i<120; i++) {
computerControl[i] = 0;
humanControl[i] = 0;
}
int [] b = pos.board;
float [] control; // set to computerControl or humanControl, as appropriate
for (int square_index=22; square_index<100; square_index++) {
int piece = b[square_index];
if (piece == 7 || piece == 0) continue;
int piece_type = piece;
if (piece_type < 0) {
piece_type = -piece_type;
control = computerControl;
} else {
control = humanControl;
}
int count = 0, side_index, move_offset, temp, next_square;
int piece_index = index[piece_type];
int move_index = pieceMovementTable[piece_index];
if (piece < 0) side_index = -1;
else side_index = 1;
switch (piece_type) {
case ChessPosition.PAWN:
{
// first check for possible pawn captures:
for (int delta=-1; delta<= 1; delta += 2) {
move_offset = square_index + side_index * 10 + delta;
int target = b[move_offset];
if ((target <= -1 && target != 7 && piece > 0) ||
(target >= 1 && target != 7 && piece < 0)) {
// kluge: count pawn control more:
control[square_index + side_index * delta] += 1.25f;
}
}
}
// Note: no break here: we want pawns to use move table also:
case ChessPosition.KNIGHT:
case ChessPosition.BISHOP:
case ChessPosition.ROOK:
case ChessPosition.KING:
case ChessPosition.QUEEN:
{
move_index = piece; if (move_index < 0) move_index = -move_index;
move_index = index[move_index];
//System.out.println("move_index="+move_index);
next_square = square_index + pieceMovementTable[move_index];
outer:
while (true) {
inner:
while (true) {
if (next_square > 99) break inner;
if (next_square < 22) break inner;
if (b[next_square] == 7) break inner;
control[next_square] += 1;
// the next statement should be augmented for x-ray analysis:
if (side_index < 0 && b[next_square] < 0) break inner;
if (side_index > 0 && b[next_square] > 0 && b[next_square] != 7) break inner;
// NOTE: prevents calculating guarding:
//if (b[next_square] != 0) break inner;
if (piece_type == ChessPosition.PAWN &&
(square_index / 10 == 3)) break inner;
if (piece_type == ChessPosition.KNIGHT) break inner;
if (piece_type == ChessPosition.KING) break inner;
next_square += pieceMovementTable[move_index];
}
move_index += 1;
if (pieceMovementTable[move_index] == 0) break outer;
next_square = square_index + pieceMovementTable[move_index];
}
}
}
}
// System.out.println("Human control:");
// for (int i=99; i>=22; i--) {
// if (b[i] == 7 && b[i+1]==7) System.out.println();
// if (b[i] != 7) System.out.print(humanControl[i]);
// }
// System.out.println();
// System.out.println("Computer control:");
// for (int i=99; i>=22; i--) {
// if (b[i] == 7 && b[i+1]==7) System.out.println();
// if (b[i] != 7) System.out.print(computerControl[i]);
// }
// System.out.println();
// System.exit(1);
}
static class aMove {
int from;
int to;
}
private static aMove [] possibleMoveList = new aMove[255];
static {
for (int i=0; i<255; i++) possibleMoveList[i] = new aMove();
}
private int calcPossibleMoves(ChessPosition pos, boolean player) {
//System.out.println("calcPossibleMoves()");
int [] b = pos.board;
int count = 0;
for (int i=22; i<100; i++) {
int board_val = b[i];
//System.out.println(board_val);
if (board_val == 7) continue;
// computer pieces will be negative:
if ((board_val < 0 && !player) || (board_val > 0 && player)) {
int num = calcPieceMoves(pos, i);
for (int j=0; j<num; j++) {
if (b[piece_moves[j]] != 7) {
//System.out.println("count="+count+", i="+i);
possibleMoveList[count].from = i;
possibleMoveList[count].to = piece_moves[j];
// System.out.println("possible move: player="+player+
// ", from="+i+", to="+piece_moves[j]);
count++;
}
}
// TBD: castle logic, etc. (page 159)
}
}
return count;
}
private int calcPieceMoves(ChessPosition pos, int square_index) {
int [] b = pos.board;
int piece = b[square_index];
int piece_type = piece;
if (piece_type < 0) piece_type = -piece_type;
int count = 0, side_index, move_offset, temp, next_square;
int piece_index = index[piece_type];
int move_index = pieceMovementTable[piece_index];
if (piece < 0) side_index = -1;
else side_index = 1;
switch (piece_type) {
case ChessPosition.PAWN:
{
// first check for possible pawn captures:
for (int delta=-1; delta<= 1; delta += 2) {
move_offset = square_index + side_index * 10 + delta;
int target = b[move_offset];
if ((target <= -1 && target != 7 && piece > 0) ||
(target >= 1 && target != 7 && piece < 0)) {
piece_moves[count++] = square_index + side_index * delta;
}
}
// check for initial pawn move of 2 squares forward:
move_offset = square_index + side_index * 20;
if (piece > 0) temp = 3; else temp = 8;
if (b[move_offset] == 0 &&
(square_index / 10) == temp &&
((piece < 0 && b[square_index - 10]==0) ||
(piece > 0 && b[square_index + 10]==0))) {
piece_moves[count++] = square_index + side_index * 20;
}
// try to move forward 1 square:
move_offset = square_index + side_index * 10;
if (b[move_offset] == 0) {
piece_moves[count++] = move_offset;
}
}
break;
case ChessPosition.KNIGHT:
case ChessPosition.BISHOP:
case ChessPosition.ROOK:
case ChessPosition.KING:
case ChessPosition.QUEEN:
{
move_index = piece; if (move_index < 0) move_index = -move_index;
move_index = index[move_index];
//System.out.println("move_index="+move_index);
next_square = square_index + pieceMovementTable[move_index];
outer:
while (true) {
inner:
while (true) {
if (next_square > 99) break inner;
if (next_square < 22) break inner;
if (b[next_square] == 7) break inner;
// check for piece on the same side:
if (side_index < 0 && b[next_square] < 0) break inner;
if (side_index >0 && b[next_square] > 0) break inner;
piece_moves[count++] = next_square;
if (b[next_square] != 0) break inner;
if (piece_type == ChessPosition.KNIGHT) break inner;
if (piece_type == ChessPosition.KING) break inner;
next_square += pieceMovementTable[move_index];
}
move_index += 1;
if (pieceMovementTable[move_index] == 0) break outer;
next_square = square_index + pieceMovementTable[move_index];
}
}
}
return count;
}
private static int [] piece_moves = new int[255];
private static int [] initialBoard = {
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
4, 2, 3, 5, 9, 3, 2, 4, 7, 7, // white pieces
1, 1, 1, 1, 1, 1, 1, 1, 7, 7, // white pawns
0, 0, 0, 0, 0, 0, 0, 0, 7, 7, // 8 blank squares, 2 off board
0, 0, 0, 0, 0, 0, 0, 0, 7, 7, // 8 blank squares, 2 off board
0, 0, 0, 0, 0, 0, 0, 0, 7, 7, // 8 blank squares, 2 off board
0, 0, 0, 0, 0, 0, 0, 0, 7, 7, // 8 blank squares, 2 off board
-1,-1,-1,-1,-1,-1,-1,-1, 7, 7, // black pawns
-4,-2,-3,-5,-9,-3,-2,-4, 7, 7, // black pieces
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};
private static int [] index = {
0, 12, 15, 10, 1, 6, 0, 0, 0, 6
};
private static int [] pieceMovementTable = {
0, -1, 1, 10, -10, 0, -1, 1, 10, -10, -9, -11, 9,
11, 0, 8, -8, 12, -12, 19, -19, 21, -21, 0, 10, 20,
0, 0, 0, 0, 0, 0, 0, 0
};
private static int [] value = {
0, 1, 3, 3, 5, 9, 0, 0, 0, 12
};
private static int [] blackSquares = {
22, 24, 26, 28, 33, 35, 37, 39,
42, 44, 46, 48, 53, 55, 57, 59,
62, 64, 66, 68, 73, 75, 77, 79,
82, 84, 86, 88, 93, 95, 97, 99
};
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-06-01T16:00:00Z
jprobe.jpl
2000-06-01T16:00:00Z
2000-06-01T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-06-01T16:00:00Z
out.txt
2000-06-01T16:00:00Z
2000-06-01T16:00:00Z
<br/>Board position:<br/><br/> BR BN BB BQ BK BB BN BR<br/> BP BP BP BP BP BP BP BP<br/> . . . . <br/> . . . . <br/> . . . . <br/> . . . . <br/> WP WP WP WP WP WP WP WP<br/> WR WN WB WQ WK WB WN WR<br/>Your move:<br/>enter a move like 'd2d4' or 'oo'<br/>s=d2d4<br/>From 35, to 55<br/>Board position:<br/><br/> BR BN BB BQ BK BB BN BR<br/> BP BP BP BP BP BP BP BP<br/> . . . . <br/> . . . . <br/> . WP . . <br/> . . . . <br/> WP WP WP . WP WP WP WP<br/> WR WN WB WQ WK WB WN WR<br/> next element: 5.4<br/> next element: [4,2,3,5,9,3,2,4,7,7,1,1,1,0,1,1,1,1,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,0,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,-5,-9,-3,-2,-4,]<br/> next element: [4,2,3,0,9,3,2,4,7,7,1,1,1,5,1,1,1,1,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,0,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,-5,-9,-3,-2,-4,]<br/> next element: [4,2,3,0,9,3,2,4,7,7,1,1,1,5,1,1,1,1,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,-5,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,-3,-2,-4,]<br/> next element: [4,2,3,0,9,3,0,4,7,7,1,1,1,5,1,1,1,1,7,7,0,0,0,0,0,2,0,0,7,7,0,0,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,-5,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,-3,-2,-4,]<br/> next element: [4,2,3,0,9,3,0,4,7,7,1,1,1,5,1,1,1,1,7,7,0,0,0,0,0,2,0,0,7,7,0,0,0,1,0,0,0,0,7,7,-1,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,-5,0,0,7,7,0,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,-3,-2,-4,]<br/>Board position:<br/><br/> BR BN BB BQ BK BB BN BR<br/> BP BP BP BP . BP BP BP<br/> . . BP . . <br/> . . . . <br/> . WP . . <br/> . . . . <br/> WP WP WP . WP WP WP WP<br/> WR WN WB WQ WK WB WN WR<br/>Your move:<br/>enter a move like 'd2d4' or 'oo'<br/>s=g1f3<br/>From 28, to 47<br/>Board position:<br/><br/> BR BN BB BQ BK BB BN BR<br/> BP BP BP BP . BP BP BP<br/> . . BP . . <br/> . . . . <br/> . WP . . <br/> . . . WN . <br/> WP WP WP . WP WP WP WP<br/> WR WN WB WQ WK WB . WR<br/> next element: 6.1999993<br/> next element: [4,2,3,5,9,3,0,4,7,7,1,1,1,0,1,1,1,1,7,7,0,0,0,0,0,2,0,0,7,7,0,0,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,-5,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,-3,-2,-4,]<br/> next element: [4,2,3,0,9,3,0,4,7,7,1,1,1,0,1,1,1,1,7,7,0,0,0,5,0,2,0,0,7,7,0,0,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,-5,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,-3,-2,-4,]<br/> next element: [4,2,3,0,9,3,0,4,7,7,1,1,1,0,1,1,1,1,7,7,0,0,0,5,0,2,0,0,7,7,0,-3,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,-5,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,0,-2,-4,]<br/> next element: [4,2,3,0,9,3,0,4,7,7,1,1,0,0,1,1,1,1,7,7,0,0,1,5,0,2,0,0,7,7,0,-3,0,1,0,0,0,0,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,-5,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,0,-2,-4,]<br/> next element: [4,2,3,0,9,3,0,4,7,7,1,1,0,0,1,1,1,1,7,7,0,0,1,5,0,2,0,0,7,7,0,-3,0,1,0,0,0,-5,7,7,0,0,0,0,0,0,0,0,7,7,0,0,0,0,-1,0,0,0,7,7,-1,-1,-1,-1,0,-1,-1,-1,7,7,-4,-2,-3,0,-9,0,-2,-4,]<br/>Board position:<br/><br/> BR BN BB . BK BB BN BR<br/> BP BP BP BP . BP BP BP<br/> . . BP BQ . <br/> . . . . <br/> . WP . . <br/> . . . WN . <br/> WP WP WP . WP WP WP WP<br/> WR WN WB WQ WK WB . WR<br/>Your move:<br/>enter a move like 'd2d4' or 'oo'<br/>java.lang.NullPointerException<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-06-01T16:00:00Z
ChessMove.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
ChessMove.java
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">public class ChessMove extends Move {
public int from;
public int to;
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
ChessPosition.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
ChessPosition.java
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">public class ChessPosition extends Position {
final static public int BLANK = 0;
final static public int HUMAN = 1;
final static public int PROGRAM = -1;
final static public int PAWN = 1;
final static public int KNIGHT = 2;
final static public int BISHOP = 3;
final static public int ROOK = 4;
final static public int QUEEN = 5;
final static public int KING = 6;
int [] board = new int[120];
public String toString() {
StringBuffer sb = new StringBuffer("[");
for (int i=22; i<100; i++) {
sb.append(""+board[i]+",");
}
sb.append("]");
return sb.toString();
}
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
GameSearch.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
GameSearch.java
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">import java.util.*;
public abstract class GameSearch {
public static final boolean DEBUG = false;
/*
* Note: the abstract Position also needs to be
* subclassed to write a new game program.
*/
/*
* Note: the abstract class Move also needs to be subclassed.
*
*/
public static boolean PROGRAM = false;
public static boolean HUMAN = true;
/**
* Notes: PROGRAM false -1, HUMAN true 1
*/
/*
* Abstract methods:
*/
public abstract boolean drawnPosition(Position p);
public abstract boolean wonPosition(Position p, boolean player);
public abstract float positionEvaluation(Position p, boolean player);
public abstract void printPosition(Position p);
public abstract Position [] possibleMoves(Position p, boolean player);
public abstract Position makeMove(Position p, boolean player, Move move);
public abstract boolean reachedMaxDepth(Position p, int depth);
public abstract Move getMove();
/*
* Search utility methods:
*/
protected Vector alphaBeta(int depth, Position p, boolean player) {
Vector v = alphaBetaHelper(depth, p, player, 1000000.0f, -1000000.0f);
//System.out.println("^^ v(0): " + v.elementAt(0) + ", v(1): " + v.elementAt(1));
return v;
}
protected Vector alphaBetaHelper(int depth, Position p,
boolean player, float alpha, float beta) {
if (GameSearch.DEBUG) System.out.println("alphaBetaHelper("+depth+","+p+","+alpha+","+beta+")");
if (reachedMaxDepth(p, depth)) {
Vector v = new Vector(2);
float value = positionEvaluation(p, player);
v.addElement(new Float(value));
v.addElement(null);
if(GameSearch.DEBUG) {
System.out.println(" alphaBetaHelper: mx depth at " + depth+
", value="+value);
}
return v;
}
Vector best = new Vector();
Position [] moves = possibleMoves(p, player);
for (int i=0; i<moves.length; i++) {
Vector v2 = alphaBetaHelper(depth + 1, moves[i], !player, -beta, -alpha);
// if (v2 == null || v2.size() < 1) continue;
float value = -((Float)v2.elementAt(0)).floatValue();
if (value > beta) {
if(GameSearch.DEBUG) System.out.println(" ! ! ! value="+value+", beta="+beta);
beta = value;
best = new Vector();
best.addElement(moves[i]);
Enumeration enum = v2.elements();
enum.nextElement(); // skip previous value
while (enum.hasMoreElements()) {
Object o = enum.nextElement();
if (o != null) best.addElement(o);
}
}
/**
* Use the alpha-beta cutoff test to abort search if we
* found a move that proves that the previous move in the
* move chain was dubious
*/
if (beta >= alpha) {
break;
}
}
Vector v3 = new Vector();
v3.addElement(new Float(beta));
Enumeration enum = best.elements();
while (enum.hasMoreElements()) {
v3.addElement(enum.nextElement());
}
return v3;
}
public void playGame(Position startingPosition, boolean humanPlayFirst) {
if (humanPlayFirst == false) {
Vector v = alphaBeta(0, startingPosition, PROGRAM);
startingPosition = (Position)v.elementAt(1);
}
while (true) {
printPosition(startingPosition);
if (wonPosition(startingPosition, PROGRAM)) {
System.out.println("Program won");
break;
}
if (wonPosition(startingPosition, HUMAN)) {
System.out.println("Human won");
break;
}
if (drawnPosition(startingPosition)) {
System.out.println("Drawn game");
break;
}
System.out.println("Your move:");
Move move = getMove();
startingPosition = makeMove(startingPosition, HUMAN, move);
printPosition(startingPosition);
Vector v = alphaBeta(0, startingPosition, PROGRAM);
Enumeration enum = v.elements();
while (enum.hasMoreElements()) {
System.out.println(" next element: " + enum.nextElement());
}
startingPosition = (Position)v.elementAt(1);
}
}
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
Move.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
Move.java
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">abstract public class Move {
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
Position.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
Position.java
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">abstract public class Position {
}</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
TicTacToe.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
TicTacToe.java
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">import java.util.*;
public class TicTacToe extends GameSearch {
public boolean drawnPosition(Position p) {
if (GameSearch.DEBUG) System.out.println("drawnPosition("+p+")");
boolean ret = true;
TicTacToePosition pos = (TicTacToePosition)p;
for (int i=0; i<9; i++) {
if (pos.board[i] == TicTacToePosition.BLANK){
ret = false;
break;
}
}
if (GameSearch.DEBUG) System.out.println(" ret="+ret);
return ret;
}
public boolean wonPosition(Position p, boolean player) {
if (GameSearch.DEBUG) System.out.println("wonPosition("+p+","+player+")");
boolean ret = false;
TicTacToePosition pos = (TicTacToePosition)p;
if (winCheck(0,1,2, player, pos)) ret = true;
else if (winCheck(3,4,5, player, pos)) ret = true;
else if (winCheck(6,7,8, player, pos)) ret = true;
else if (winCheck(2,5,8, player, pos)) ret = true;
else if (winCheck(0,4,8, player, pos)) ret = true;
else if (winCheck(2,4,6, player, pos)) ret = true;
else if (winCheck(0,3,6, player, pos)) ret = true;
else if (winCheck(1,4,7, player, pos)) ret = true;
if (GameSearch.DEBUG) System.out.println(" ret="+ret);
return ret;
}
private boolean winCheck(int i1, int i2, int i3,
boolean player, TicTacToePosition pos) {
int b = 0;
if (player) b = TicTacToePosition.HUMAN;
else b = TicTacToePosition.PROGRAM;
if (pos.board[i1] == b &&
pos.board[i2] == b &&
pos.board[i3] == b) return true;
return false;
}
public float positionEvaluation(Position p, boolean player) {
int count = 0;
TicTacToePosition pos = (TicTacToePosition)p;
for (int i=0; i<9; i++) {
if (pos.board[i] == 0) count++;
}
count = 10 - count;
// prefer the center square:
float base = 1.0f;
if (pos.board[4] == TicTacToePosition.HUMAN &&
player) {
base += 0.4f;
}
if (pos.board[4] == TicTacToePosition.PROGRAM &&
!player) {
base -= 0.4f;
}
float ret = (base - 1.0f);
if (wonPosition(p, player)) {
return base + (1.0f / count);
}
if (wonPosition(p, !player)) {
return -(base + (1.0f / count));
}
return ret;
}
public void printPosition(Position p) {
System.out.println("Board position:");
TicTacToePosition pos = (TicTacToePosition)p;
int count = 0;
for (int row=0; row<3; row++) {
System.out.println();
for (int col=0; col<3; col++) {
if (pos.board[count] == TicTacToePosition.HUMAN) {
System.out.print("H");
} else if (pos.board[count] == TicTacToePosition.PROGRAM) {
System.out.print("P");
} else {
System.out.print(" ");
}
count++;
}
}
System.out.println();
}
public Position [] possibleMoves(Position p, boolean player) {
if (GameSearch.DEBUG) System.out.println("posibleMoves("+p+","+player+")");
TicTacToePosition pos = (TicTacToePosition)p;
int count = 0;
for (int i=0; i<9; i++) if (pos.board[i] == 0) count++;
if (count == 0) return null;
Position [] ret = new Position[count];
count = 0;
for (int i=0; i<9; i++) {
if (pos.board[i] == 0) {
TicTacToePosition pos2 = new TicTacToePosition();
for (int j=0; j<9; j++) pos2.board[j] = pos.board[j];
if (player) pos2.board[i] = 1; else pos2.board[i] = -1;
ret[count++] = pos2;
if (GameSearch.DEBUG) System.out.println(" "+pos2);
}
}
return ret;
}
public Position makeMove(Position p, boolean player, Move move) {
if (GameSearch.DEBUG) System.out.println("Entered TicTacToe.makeMove");
TicTacToeMove m = (TicTacToeMove)move;
TicTacToePosition pos = (TicTacToePosition)p;
TicTacToePosition pos2 = new TicTacToePosition();
for (int i=0; i<9; i++) pos2.board[i] = pos.board[i];
int pp;
if (player) pp = 1;
else pp = -1;
if (GameSearch.DEBUG) System.out.println("makeMove: m.moveIndex = " + m.moveIndex);
pos2.board[m.moveIndex] = pp;
return pos2;
}
public boolean reachedMaxDepth(Position p, int depth) {
boolean ret = false;
if (wonPosition(p, false)) ret = true;
else if (wonPosition(p, true)) ret = true;
else if (drawnPosition(p)) ret = true;
if (GameSearch.DEBUG) {
System.out.println("reachedMaxDepth: pos=" + p.toString() + ", depth="+depth
+", ret=" + ret);
}
return ret;
}
public Move getMove() {
if (GameSearch.DEBUG) System.out.println("Enter blank square index [0,8]:");
int i = 0;
try {
int ch = System.in.read();
i = ch - 48;
System.in.read();
System.in.read();
System.out.println("ch="+ch+", i=" + i);
} catch (Exception e) { }
TicTacToeMove mm = new TicTacToeMove();
mm.moveIndex = i;
return mm;
}
static public void main(String [] args) {
TicTacToePosition p = new TicTacToePosition();
TicTacToe ttt = new TicTacToe();
ttt.playGame(p, false);
}
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
TicTacToeMove.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
TicTacToePosition.class
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
TicTacToePosition.java
2000-05-30T16:00:00Z
2000-05-30T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">public class TicTacToePosition extends Position {
final static public int BLANK = 0;
final static public int HUMAN = 1;
final static public int PROGRAM = -1;
int [] board = new int[9];
public String toString() {
StringBuffer sb = new StringBuffer("[");
for (int i=0; i<9; i++) {
sb.append(""+board[i]+",");
}
sb.append("]");
return sb.toString();
}
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-30T16:00:00Z
TicTacToeMove.java
2000-05-19T16:00:00Z
2000-05-19T16:00:00Z
<br/><TEXTAREA name="code" class="java" rows="16" cols="100">public class TicTacToeMove extends Move {
public int moveIndex;
}
</TEXTAREA><br><br/><script type="text/javascript"><!--google_ad_client = "pub-9426659565807829";google_ad_slot = "9359905831";google_ad_width = 728;google_ad_height = 15;//--></script><script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>
2000-05-19T16:00:00Z