/*
Connect 4
By Tantrum
The board:
8!16 24 32 40 48 56 64!
7!15 23 31 39 47 55 63!71
---+--------------------+---
6!14 22 30 38 46 54 62!70
5!13 21 29 37 45 53 61!69
4!12 20 28 36 44 52 60!68
3!11 19 27 35 43 51 59!67
2!10 18 26 34 42 50 58!66
1! 9 17 25 33 41 49 57!65
---+--------------------+---
0! 8 16 24 32 40 48 56!64
a b c d e f g
*/
import java.awt.*;
import java.applet.*;
import java.io.*;
public class Connect4 extends Applet {
Thread cThread = null;
int board[] = new int[72]; // playing board
int rootBoard[] = new int[72]; // copy of playing board
int next[] = new int[7]; // next free sq in column
int game[] = new int[42]; // list of moves in the game
int scores[] = new int[43]; // score at each move in the game
int moveno; // move number
int rootMoveno;
int brdScore; // current positional score
int rootBrdScore;
int side; // side to move
int rootSide;
boolean win = false; // end of game, winner
boolean auto = true;
int bestval;
int nodecnt;
final static int win_score = -14000;
final static int peakdepth = 11;
int pv[][] = new int[peakdepth][peakdepth]; // principle variation
int depth, maxdepth;
int curCol = 0; // Current position of the next disk
public void stop() {
if (cThread != null) {
cThread.stop();
cThread = null;
}
}
void NewGame() {
int i, j;
for (i = 0; i < 72; ++i)
board[i] = 3;
for (i = 0; i < 7; ++i) {
next[i] = i * 8 + 9;
for (j = 0; j < 6; ++j)
board[i * 8 + j + 9] = 0;
}
moveno = 0;
brdScore = 0;
side = 1;
nodecnt = 0;
bestval = 0;
Copy();
}
void Copy() {
rootMoveno = moveno;
rootSide = side;
rootBrdScore = brdScore;
for (int i = 0; i < 72; i++)
rootBoard[i] = board[i];
}
void Update(int i) {
int v;
scores[moveno] = brdScore;
game[moveno] = i;
board[next[i]] = side;
v = UpdateScore(next[i]);
brdScore = (v >= (-win_score)) ? -v : -(brdScore + v);
++moveno;
++next[i];
side = 3 - side;
++nodecnt;
}
void Dndate() {
int col;
--moveno;
col = game[moveno];
--next[col];
board[next[col]] = 0;
brdScore = scores[moveno];
side = 3 - side;
}
boolean yourMove(int m) {
if ((m < 0) || (m > 6) || (board[next[m]] != 0)) {
return false;
}
Update(m);
Copy();
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
win = true;
repaint();
play(getCodeBase(), "gameover.au");
} else {
repaint(curCol * xoff, 0, xoff, yoff * 7); // column
play(getCodeBase(), "ding.au");
}
return true;
}
Image notImage; // The image for white.
Image crossImage; // The image for black.
Image brdImage; // The board
Image rdiskImage; // Players disk
Image gdiskImage; // Players disk
FileOutputStream fos;
PrintStream ps;
public void init() {
notImage = getImage(getCodeBase(), "pieces/yellow.gif");
crossImage = getImage(getCodeBase(), "pieces/red.gif");
brdImage = getImage(getCodeBase(), "pieces/empty.gif");
rdiskImage = getImage(getCodeBase(), "pieces/ydisk.gif");
gdiskImage = getImage(getCodeBase(), "pieces/rdisk.gif");
setBackground(Color.lightGray);
NewGame();
}
final int xoff = 50;
final int yoff = 50;
public void update(Graphics g) {
paint(g);
}
public void paint(Graphics g) {
int i, j;
Font font = new Font("Arial", Font.BOLD, 25);
g.setFont(font);
g.clearRect(0, 0, xoff * 7, yoff);
if (rootBrdScore <= win_score || rootBrdScore >= (-win_score)) {
if (win)
g.drawString("You won this game.", 20, 20);
else
g.drawString("You lost this game.", 20, 20);
} else if (rootMoveno >= 42)
g.drawString("The game is a draw.", 20, 20);
else if (rootSide == 1)
g.drawImage(rdiskImage, curCol * xoff, 0, this);
else
g.drawImage(gdiskImage, curCol * xoff, 0, this);
for (int r = 1; r < 7; r++) {
for (int c = 0; c < 7; c++) {
switch (rootBoard[c * 8 + (6 - r) + 9]) {
case 0:
g.drawImage(brdImage, c * xoff, r * yoff, this);
break;
case 1:
g.drawImage(notImage, c * xoff, r * yoff, this);
break;
case 2:
g.drawImage(crossImage, c * xoff, r * yoff, this);
break;
}
} // for c
} // for r
}
// the next disk over the board follows the mouse movement
public boolean mouseMove(Event evt, int x, int y) {
if (cThread != null)
return true;
int col = x / xoff;
if (col <= 0)
col = 0;
if (col >= 6)
col = 6;
if (col != curCol) {
curCol = col;
repaint(0, 0, xoff * 7, yoff);
}
return true;
}
// the click of the mouse makes the move
public boolean mouseDown(Event evt, int x, int y) {
if (cThread != null)
return true;
// Click after game-over to start a new game
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
play(getCodeBase(), "ding.au");
NewGame();
repaint();
return true;
}
mouseMove(evt, x, y);
if (yourMove(curCol)) {
if (auto) {
cThread = new ComputeThread(this);
cThread.start();
}
} else
play(getCodeBase(), "error.au");
return true;
}
public boolean keyDown(Event event, int key) {
if (key == Event.F2) {
auto = !auto;
if (auto)
showStatus("Auto on");
else
showStatus("Auto off");
return true;
}
if (key == Event.F3) {
cThread = new ComputeThread(this);
cThread.start();
return true;
}
return false;
}
public String getAppletInfo() {
return "Connect Four by Mike Johnson";
}
// compute a move
void ComputeMove() {
long starttime = System.currentTimeMillis();
Copy();
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
win = true;
return;
}
// Generate a random start move
curCol = (int) (Math.random() * 7);
if (curCol < 0)
curCol = 0;
if (curCol > 6)
curCol = 6;
pv[0][0] = curCol;
// If its the first move then play the random move
if (moveno >= 2) {
depth = 0;
nodecnt = 0;
int i, j;
for (i = 0; i < peakdepth; ++i)
for (j = 0; j < peakdepth; ++j)
pv[i][j] = 255;
for (maxdepth = 2; maxdepth < peakdepth && moveno + maxdepth <= 44; ++maxdepth) {
bestval = -alphabeta(-15000, 15000);
showStatus("msec=" + (System.currentTimeMillis() - starttime)
+ ", depth=" + maxdepth + ", nodes=" + nodecnt
+ ", move=" + (char) (pv[0][0] + 'a'));
if (System.currentTimeMillis() - starttime >= 1000) {
break;
}
if (bestval <= win_score) {
break;
}
if (bestval >= (-win_score)) {
break;
}
} // for maxdepth
} // if moveno
curCol = pv[0][0];
Update(curCol);
Copy();
win = false;
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
repaint(); // everyting
play(getCodeBase(), "gameover.au");
} else {
repaint(curCol * xoff, 0, xoff, yoff * 7); // column
play(getCodeBase(), "ding.au");
}
}
int order[] = { 3, 2, 4, 1, 5, 0, 6 }; // move order
int alphabeta(int alpha, int beta) {
int i, v, mv, pmv = 0;
if (brdScore <= win_score)
return brdScore;
if (depth >= maxdepth)
return brdScore;
if (moveno == 42)
return 0;
for (i = (-1); i < 7; i++) {
/* select move, priciple variation first, rest after */
if (i == (-1)) {
pmv = mv = pv[depth][depth];
if (mv == 255)
continue;
} else {
mv = order[i];
if (mv == pmv)
continue;
}
/* search move */
if (board[next[mv]] == 0) {
Update(mv);
++depth;
v = -alphabeta(-beta, -alpha);
Dndate();
--depth;
if (v > alpha) {
alpha = v;
pv[depth][depth] = mv;
if ((depth == 0) && (curCol != mv)) {
curCol = mv;
repaint(0, 0, xoff * 7, yoff); // top line
}
for (v = depth + 1; v < maxdepth; ++v)
pv[depth][v] = pv[depth + 1][v];
}
if (alpha >= beta)
return alpha;
}
}
return alpha;
}
// Evaluation function
int direction[] = { 1, 9, 8, 7 };
// would filling this square make a winning line ?
boolean LineOfThree(int emptySq, int side) {
if (board[emptySq] != 0) // only consider empty squares
return false;
for (int dirIndex = 0; dirIndex < 4; ++dirIndex) { // 4 line directions
int sqCount = 0;
int nearSq = emptySq - direction[dirIndex];
while (board[nearSq] == side) {
++sqCount;
nearSq -= direction[dirIndex];
}
nearSq = emptySq + direction[dirIndex];
while (board[nearSq] == side) {
++sqCount;
nearSq += direction[dirIndex];
}
if (sqCount >= 3)
return true;
}
return false;
}
int valueOfCount[] = { 0, 1, 4, 10, 100 }; // points for partial rows
int UpdateScore(int sq) {
int d, k;
int s1, s2;
int i, j;
int gap = 0;
int val = 0;
for (d = 0; d < 4; ++d) { // all 4 directions
i = sq;
for (k = 1; k <= 3; ++k) { // move down at most 3 squares
i -= direction[d];
if (board[i] == 3) { // too far: just off edge
i += direction[d];
break;
}
}
for (;;) { // all rows of 4, in this direction, containing sq
s1 = s2 = 0;
for (k = 0, j = i; k < 4; ++k, j += direction[d]) {
if (board[j] == 0) // empty square
gap = j;
else if (board[j] == side) // side just moved
++s2;
else if (board[j] == (3 - side)) // side to move next
++s1;
else if (board[j] == 3) // edge of board, so not possible to
// be a line of 4
break;
} // end for k, j
if (k < 4 && board[j] == 3) // hit the other edge of board, so
// no more lines of 4
break;
if (s2 == 4) // won by side just moved
return (-win_score) + (50 - moveno);
else if (s1 == 0) {
// row owned by s2, side just played, may be
// an increase in ownership or a first
if (s2 == 3) {
// winning gap in line of 3 ? Depends on parity,
// 1st side to play on odd squares, second on even
if ((gap & 1) == (side & 1))
val += 50;
else
val += (valueOfCount[s2] - valueOfCount[s2 - 1]);
// is it part of a gap pair
if (LineOfThree(gap + 1, side)
|| LineOfThree(gap - 1, side))
val += 300;
} else
val += (valueOfCount[s2] - valueOfCount[s2 - 1]);
} else if (s2 == 1) { // s1!=0
// was owned by s1, now not owned by either
// gap-pairs cannot be destroyed
if (s1 == 3 && (sq & 1) != (side & 1)) // parity block a
// winning line of
// three
val += 50;
else
val += valueOfCount[s1];
}
if (i == sq)
break;
i += direction[d];
} // end for all rows of 4
} // end for d, all 4 directions
if (LineOfThree(sq + 1, 3 - side)) // next move is a win for the
// opponent
return -1000;
return val;
} // end update score
} // end class connect4
class ComputeThread extends Thread {
Connect4 a;
public ComputeThread(Connect4 a) {
this.a = a;
}
public void run() {
a.ComputeMove();
a.cThread = null;
}
}
/*
Connect 4
By Tantrum
The board:
8!16 24 32 40 48 56 64!
7!15 23 31 39 47 55 63!71
---+--------------------+---
6!14 22 30 38 46 54 62!70
5!13 21 29 37 45 53 61!69
4!12 20 28 36 44 52 60!68
3!11 19 27 35 43 51 59!67
2!10 18 26 34 42 50 58!66
1! 9 17 25 33 41 49 57!65
---+--------------------+---
0! 8 16 24 32 40 48 56!64
a b c d e f g
*/
import java.awt.*;
import java.applet.*;
import java.io.*;
public class Connect4 extends Applet {
Thread cThread = null;
int board[] = new int[72]; // playing board
int rootBoard[] = new int[72]; // copy of playing board
int next[] = new int[7]; // next free sq in column
int game[] = new int[42]; // list of moves in the game
int scores[] = new int[43]; // score at each move in the game
int moveno; // move number
int rootMoveno;
int brdScore; // current positional score
int rootBrdScore;
int side; // side to move
int rootSide;
boolean win = false; // end of game, winner
boolean auto = true;
int bestval;
int nodecnt;
final static int win_score = -14000;
final static int peakdepth = 11;
int pv[][] = new int[peakdepth][peakdepth]; // principle variation
int depth, maxdepth;
int curCol = 0; // Current position of the next disk
public void stop() {
if (cThread != null) {
cThread.stop();
cThread = null;
}
}
void NewGame() {
int i, j;
for (i = 0; i < 72; ++i)
board[i] = 3;
for (i = 0; i < 7; ++i) {
next[i] = i * 8 + 9;
for (j = 0; j < 6; ++j)
board[i * 8 + j + 9] = 0;
}
moveno = 0;
brdScore = 0;
side = 1;
nodecnt = 0;
bestval = 0;
Copy();
}
void Copy() {
rootMoveno = moveno;
rootSide = side;
rootBrdScore = brdScore;
for (int i = 0; i < 72; i++)
rootBoard[i] = board[i];
}
void Update(int i) {
int v;
scores[moveno] = brdScore;
game[moveno] = i;
board[next[i]] = side;
v = UpdateScore(next[i]);
brdScore = (v >= (-win_score)) ? -v : -(brdScore + v);
++moveno;
++next[i];
side = 3 - side;
++nodecnt;
}
void Dndate() {
int col;
--moveno;
col = game[moveno];
--next[col];
board[next[col]] = 0;
brdScore = scores[moveno];
side = 3 - side;
}
boolean yourMove(int m) {
if ((m < 0) || (m > 6) || (board[next[m]] != 0)) {
return false;
}
Update(m);
Copy();
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
win = true;
repaint();
play(getCodeBase(), "gameover.au");
} else {
repaint(curCol * xoff, 0, xoff, yoff * 7); // column
play(getCodeBase(), "ding.au");
}
return true;
}
Image notImage; // The image for white.
Image crossImage; // The image for black.
Image brdImage; // The board
Image rdiskImage; // Players disk
Image gdiskImage; // Players disk
FileOutputStream fos;
PrintStream ps;
public void init() {
notImage = getImage(getCodeBase(), "pieces/yellow.gif");
crossImage = getImage(getCodeBase(), "pieces/red.gif");
brdImage = getImage(getCodeBase(), "pieces/empty.gif");
rdiskImage = getImage(getCodeBase(), "pieces/ydisk.gif");
gdiskImage = getImage(getCodeBase(), "pieces/rdisk.gif");
setBackground(Color.lightGray);
NewGame();
}
final int xoff = 50;
final int yoff = 50;
public void update(Graphics g) {
paint(g);
}
public void paint(Graphics g) {
int i, j;
Font font = new Font("Arial", Font.BOLD, 25);
g.setFont(font);
g.clearRect(0, 0, xoff * 7, yoff);
if (rootBrdScore <= win_score || rootBrdScore >= (-win_score)) {
if (win)
g.drawString("You won this game.", 20, 20);
else
g.drawString("You lost this game.", 20, 20);
} else if (rootMoveno >= 42)
g.drawString("The game is a draw.", 20, 20);
else if (rootSide == 1)
g.drawImage(rdiskImage, curCol * xoff, 0, this);
else
g.drawImage(gdiskImage, curCol * xoff, 0, this);
for (int r = 1; r < 7; r++) {
for (int c = 0; c < 7; c++) {
switch (rootBoard[c * 8 + (6 - r) + 9]) {
case 0:
g.drawImage(brdImage, c * xoff, r * yoff, this);
break;
case 1:
g.drawImage(notImage, c * xoff, r * yoff, this);
break;
case 2:
g.drawImage(crossImage, c * xoff, r * yoff, this);
break;
}
} // for c
} // for r
}
// the next disk over the board follows the mouse movement
public boolean mouseMove(Event evt, int x, int y) {
if (cThread != null)
return true;
int col = x / xoff;
if (col <= 0)
col = 0;
if (col >= 6)
col = 6;
if (col != curCol) {
curCol = col;
repaint(0, 0, xoff * 7, yoff);
}
return true;
}
// the click of the mouse makes the move
public boolean mouseDown(Event evt, int x, int y) {
if (cThread != null)
return true;
// Click after game-over to start a new game
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
play(getCodeBase(), "ding.au");
NewGame();
repaint();
return true;
}
mouseMove(evt, x, y);
if (yourMove(curCol)) {
if (auto) {
cThread = new ComputeThread(this);
cThread.start();
}
} else
play(getCodeBase(), "error.au");
return true;
}
public boolean keyDown(Event event, int key) {
if (key == Event.F2) {
auto = !auto;
if (auto)
showStatus("Auto on");
else
showStatus("Auto off");
return true;
}
if (key == Event.F3) {
cThread = new ComputeThread(this);
cThread.start();
return true;
}
return false;
}
public String getAppletInfo() {
return "Connect Four by Mike Johnson";
}
// compute a move
void ComputeMove() {
long starttime = System.currentTimeMillis();
Copy();
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
win = true;
return;
}
// Generate a random start move
curCol = (int) (Math.random() * 7);
if (curCol < 0)
curCol = 0;
if (curCol > 6)
curCol = 6;
pv[0][0] = curCol;
// If its the first move then play the random move
if (moveno >= 2) {
depth = 0;
nodecnt = 0;
int i, j;
for (i = 0; i < peakdepth; ++i)
for (j = 0; j < peakdepth; ++j)
pv[i][j] = 255;
for (maxdepth = 2; maxdepth < peakdepth && moveno + maxdepth <= 44; ++maxdepth) {
bestval = -alphabeta(-15000, 15000);
showStatus("msec=" + (System.currentTimeMillis() - starttime)
+ ", depth=" + maxdepth + ", nodes=" + nodecnt
+ ", move=" + (char) (pv[0][0] + 'a'));
if (System.currentTimeMillis() - starttime >= 1000) {
break;
}
if (bestval <= win_score) {
break;
}
if (bestval >= (-win_score)) {
break;
}
} // for maxdepth
} // if moveno
curCol = pv[0][0];
Update(curCol);
Copy();
win = false;
if (moveno >= 42 || brdScore <= win_score || brdScore >= (-win_score)) {
repaint(); // everyting
play(getCodeBase(), "gameover.au");
} else {
repaint(curCol * xoff, 0, xoff, yoff * 7); // column
play(getCodeBase(), "ding.au");
}
}
int order[] = { 3, 2, 4, 1, 5, 0, 6 }; // move order
int alphabeta(int alpha, int beta) {
int i, v, mv, pmv = 0;
if (brdScore <= win_score)
return brdScore;
if (depth >= maxdepth)
return brdScore;
if (moveno == 42)
return 0;
for (i = (-1); i < 7; i++) {
/* select move, priciple variation first, rest after */
if (i == (-1)) {
pmv = mv = pv[depth][depth];
if (mv == 255)
continue;
} else {
mv = order[i];
if (mv == pmv)
continue;
}
/* search move */
if (board[next[mv]] == 0) {
Update(mv);
++depth;
v = -alphabeta(-beta, -alpha);
Dndate();
--depth;
if (v > alpha) {
alpha = v;
pv[depth][depth] = mv;
if ((depth == 0) && (curCol != mv)) {
curCol = mv;
repaint(0, 0, xoff * 7, yoff); // top line
}
for (v = depth + 1; v < maxdepth; ++v)
pv[depth][v] = pv[depth + 1][v];
}
if (alpha >= beta)
return alpha;
}
}
return alpha;
}
// Evaluation function
int direction[] = { 1, 9, 8, 7 };
// would filling this square make a winning line ?
boolean LineOfThree(int emptySq, int side) {
if (board[emptySq] != 0) // only consider empty squares
return false;
for (int dirIndex = 0; dirIndex < 4; ++dirIndex) { // 4 line directions
int sqCount = 0;
int nearSq = emptySq - direction[dirIndex];
while (board[nearSq] == side) {
++sqCount;
nearSq -= direction[dirIndex];
}
nearSq = emptySq + direction[dirIndex];
while (board[nearSq] == side) {
++sqCount;
nearSq += direction[dirIndex];
}
if (sqCount >= 3)
return true;
}
return false;
}
int valueOfCount[] = { 0, 1, 4, 10, 100 }; // points for partial rows
int UpdateScore(int sq) {
int d, k;
int s1, s2;
int i, j;
int gap = 0;
int val = 0;
for (d = 0; d < 4; ++d) { // all 4 directions
i = sq;
for (k = 1; k <= 3; ++k) { // move down at most 3 squares
i -= direction[d];
if (board[i] == 3) { // too far: just off edge
i += direction[d];
break;
}
}
for (;;) { // all rows of 4, in this direction, containing sq
s1 = s2 = 0;
for (k = 0, j = i; k < 4; ++k, j += direction[d]) {
if (board[j] == 0) // empty square
gap = j;
else if (board[j] == side) // side just moved
++s2;
else if (board[j] == (3 - side)) // side to move next
++s1;
else if (board[j] == 3) // edge of board, so not possible to
// be a line of 4
break;
} // end for k, j
if (k < 4 && board[j] == 3) // hit the other edge of board, so
// no more lines of 4
break;
if (s2 == 4) // won by side just moved
return (-win_score) + (50 - moveno);
else if (s1 == 0) {
// row owned by s2, side just played, may be
// an increase in ownership or a first
if (s2 == 3) {
// winning gap in line of 3 ? Depends on parity,
// 1st side to play on odd squares, second on even
if ((gap & 1) == (side & 1))
val += 50;
else
val += (valueOfCount[s2] - valueOfCount[s2 - 1]);
// is it part of a gap pair
if (LineOfThree(gap + 1, side)
|| LineOfThree(gap - 1, side))
val += 300;
} else
val += (valueOfCount[s2] - valueOfCount[s2 - 1]);
} else if (s2 == 1) { // s1!=0
// was owned by s1, now not owned by either
// gap-pairs cannot be destroyed
if (s1 == 3 && (sq & 1) != (side & 1)) // parity block a
// winning line of
// three
val += 50;
else
val += valueOfCount[s1];
}
if (i == sq)
break;
i += direction[d];
} // end for all rows of 4
} // end for d, all 4 directions
if (LineOfThree(sq + 1, 3 - side)) // next move is a win for the
// opponent
return -1000;
return val;
} // end update score
} // end class connect4
class ComputeThread extends Thread {
Connect4 a;
public ComputeThread(Connect4 a) {
this.a = a;
}
public void run() {
a.ComputeMove();
a.cThread = null;
}
}