Mancala Source

(Last Update 09:21 on Wednesday, 10 January 2001)

// Mancala applet
// Neil Rashbrook
// Last modified March 24 2000
import java.awt.*;
final class intlist {
public final int bowl;
public final intlist list;
public intlist(int bowl) {
this.bowl = bowl;
this.list = null;
}
public intlist(final int bowl, final intlist list) {
this.bowl = bowl;
this.list = list;
}
public intlist reverse() {
if (list == null) return this;
intlist src, dest = null;
for (src = this; src != null; src = src.list) dest = new intlist(src.bowl, dest);
return dest;
}
public String toString() {
return addTo(new StringBuffer(getClass().getName()).append('[')).toString();
}
public StringBuffer addTo(final StringBuffer s) {
if (list == null) return s.append(bowl).append(']');
else return list.addTo(s.append(bowl).append(','));
}
}
final class bowl extends Canvas {
private static Image offImage;
private static Graphics offGraphics;
private static int offWidth = -1, offHeight = -1;
private final Object arg;
private int beads;
private double phi;
private boolean clickable;
private boolean highlight;
private Rectangle bounds;
private static final int used[][] = new int[15][15];
private static final int score[][] = new int[15][15];
private static int posX[] = new int[2];
private static int posY[] = new int[2];
private static int cX[] = new int[2];
private static int cY[] = new int[2];
private static final float s3 = (float)Math.sqrt(3);
static {
used[0][0] = 1;
for (int j = 0; j < 15; j++) for (int k = 0; k < 15; k++) score[j][k] += j * j - j * k + k * k;
}
private static int[] extend(final int[] src, final int beads) {
final int iarray[] = new int[beads + 1];
System.arraycopy(src, 0, iarray, 0, src.length);
return iarray;
}
private synchronized static void calc(final int beads) {
final int next = cX.length;
int cx = cX[next - 1], cy = cY[next - 1];
posX = extend(posX, beads);
posY = extend(posY, beads);
cX = extend(cX, beads);
cY = extend(cY, beads);
for (int i = next; i <= beads; i++) {
int l = score[0][7], m = 0, n = 7;
for (int j = 0; j < 15; j++) for (int k = 0; k < 15; k++) if (used[j][k] == 0 && score[j][k] <= l) {
l = score[j][k];
m = j;
n = k;
}
used[m][n] = i;
cX[i] = cx += posX[i] = m + m - n;
cY[i] = cy += posY[i] = n;
for (int j = 0; j < 15; j++) for (int k = 0; k < 15; k++) score[j][k] += (j - m) * (j - m) - (j - m) * (k - n) + (k - n) * (k - n);
}
}
public bowl(final int arg) {
this.arg = new intlist(arg);
}
public boolean isempty() {
return this.beads == 0;
}
public boolean issingle() {
return this.beads == 1;
}
public int empty() {
int beads = this.beads;
this.beads = 0;
this.clickable = false;
if (beads != 0) super.repaint();
return beads;
}
public void add() {
this.beads++;
this.phi = (Math.random() * 4 - 2) * Math.PI;
super.repaint();
}
public void add(final int beads) {
this.beads += beads;
this.phi = (Math.random() * 4 - 2) * Math.PI;
super.repaint();
}
public void remove() {
this.beads--;
this.phi = (Math.random() * 4 - 2) * Math.PI;
if (beads == 0) this.clickable = false;
super.repaint();
}
public void setclickable(boolean clickable) {
if (beads == 0) clickable = false;
if (clickable != this.clickable) {
this.clickable = clickable;
if (this.highlight) super.repaint();
}
}
public int getbeads() {
return beads;
}
public boolean mouseExit(final Event evt, final int mx, final int my) {
if (highlight) {
highlight = false;
if (clickable) super.repaint();
}
return false;
}
public boolean mouseMove(final Event evt, final int mx, final int my) {
if (bounds != null) {
float x = mx * 2F / bounds.width -1, y = my * 2F / bounds.height - 1;
boolean highlight = x * x + y * y < 1;
if (highlight != this.highlight) {
this.highlight = highlight;
if (this.clickable) super.repaint();
}
}
return false;
}
public boolean mouseDown(final Event evt, final int mx, final int my) {
if (clickable && highlight) postEvent(new Event(this, Event.ACTION_EVENT, arg));
return false;
}
public void bead(final float x, final float y, final float r) {
offGraphics.setColor(Color.gray);
offGraphics.fillOval(Math.round(x - r), Math.round(y - r), Math.round(x + r) - Math.round(x - r), Math.round(y + r) - Math.round(y - r));
offGraphics.setColor(Color.white);
offGraphics.drawOval(Math.round(x - r), Math.round(y - r), Math.round(x + r) - Math.round(x - r), Math.round(y + r) - Math.round(y - r));
}
public void paint(final Graphics g) {
bounds = bounds();
if (bounds.width > offWidth || bounds.height > offHeight) {
offWidth = Math.max(offWidth, bounds.width);
offHeight = Math.max(offHeight, bounds.height);
offImage = createImage(offWidth, offHeight);
offGraphics = offImage.getGraphics();
}
offGraphics.setColor(super.getBackground());
offGraphics.fillRect(0, 0, bounds.width, bounds.height);
offGraphics.setColor(Color.gray);
offGraphics.fillOval(0, 0, bounds.width, bounds.height);
if (clickable && highlight) {
offGraphics.setColor(Color.white);
offGraphics.fillOval(1, 1, bounds.width - 3, bounds.height - 3);
offGraphics.setColor(Color.black);
} else {
offGraphics.setColor(Color.black);
offGraphics.fillOval(1, 1, bounds.width - 3, bounds.height - 3);
offGraphics.setColor(Color.white);
}
offGraphics.fillOval(2, 2, bounds.width - 3, bounds.height - 3);
offGraphics.setColor(Color.lightGray);
offGraphics.fillOval(2, 2, bounds.width - 4, bounds.height - 4);
bounds.width--;
bounds.height--;
if (beads > 0) {
float x = bounds.width / 2F, y = bounds.height / 2F;
float r = Math.min(x, y) / (float)Math.sqrt(16. + beads);
if (beads == 1) bead(x, y, r);
else {
if (beads >= posX.length) calc(beads);
float rx = r * (float)Math.cos(phi);
float ry = r * (float)Math.sin(phi);
float s3 = phi < 0 ? -this.s3 : this.s3;
float cx = cX[beads] / (float)beads;
float cy = cY[beads] / (float)beads;
for (int i = 1; i <= beads; i++) {
float bx = posX[i] - cx;
float by = (posY[i] - cy) * s3;
bead(x + bx * rx + by * ry, y + by * rx - bx * ry, r);
}
}
}
g.drawImage(offImage, 0, 0, this);
}
public void update(final Graphics g) {
paint(g);
}
public Dimension minimumSize() {
return new Dimension();
}
public Dimension getMinimumSize() {
return new Dimension();
}
public Dimension preferredSize() {
return new Dimension();
}
public Dimension getPreferredSize() {
return new Dimension();
}
}
final class choice extends java.awt.Choice {
private static Dimension zeroWidth(Dimension d) {
d.width = 0;
return d;
}
public Dimension minimumSize() {
return zeroWidth(super.minimumSize());
}
public Dimension getMinimumSize() {
return zeroWidth(super.getMinimumSize());
}
public Dimension preferredSize() {
return zeroWidth(super.preferredSize());
}
public Dimension getPreferredSize() {
return zeroWidth(super.getPreferredSize());
}
}
final class board {
private int score, player, num;
private int bowls[] = new int[14];
private board next = null;
private boolean top = false, capture = false, playall = false, finish = false;
public boolean gameover = false, nomove = true;
public void copy(final bowl bowls[], final int player) {
for (int i = 0; i < 14; i++) this.bowls[i] = bowls[i].getbeads();
this.player = player;
}
public board() {
this.top = true;
}
private board(final boolean capture, final boolean playall, final boolean finish) {
this.capture = capture;
this.playall = playall;
this.finish = finish;
}
private boolean isgameover(int player) {
for (int bowl = player + 6; bowl > player; bowl--) if (bowls[bowl] > 0) return false;
int scorer = player;
player = 7 - player;
if (!finish) scorer = player;
for (int bowl = player + 6; bowl > player; bowl--) {
bowls[scorer] += bowls[bowl];
bowls[bowl] = 0;
}
return true;
}
private boolean domove(int bowl) {
if (next == null) next = new board(capture, playall, finish);
for (int i = 0; i < 14; i++) next.bowls[i] = bowls[i];
next.player = 7 - player;
int beads = bowls[bowl];
next.bowls[bowl] = 0;
while (beads > 0) {
do bowl = bowl == 0 ? 13 : bowl - 1;
while (!playall && bowl == next.player);
next.bowls[bowl]++;
beads--;
}
if (bowl > player && bowl < player + 7 && next.bowls[bowl] == 1) {
next.bowls[player] += next.bowls[14 - bowl];
next.bowls[14 - bowl] = 0;
if (capture) {
next.bowls[bowl] = 0;
next.bowls[player]++;
}
}
if (next.isgameover(player) || next.isgameover(7 - player) || bowl != player) {
next.player = 7 - player;
return false;
} else {
next.player = player;
return true;
}
}
private intlist[] listmoves(final intlist list) {
int count = 0;
for (int bowl = player + 6; bowl > player; bowl--) if (bowls[bowl] > 0) count++;
if (count == 0) return null;
intlist movelist[] = new intlist[count];
count = 0;
for (int bowl = player + 6; bowl > player; bowl--) if (bowls[bowl] > 0) {
intlist move = new intlist(bowl, list);
intlist nextlist[];
if ((bowl - player - bowls[bowl]) % 13 == 0 && domove(bowl) && (nextlist = next.listmoves(move)) != null) {
intlist newlist[] = new intlist[movelist.length + nextlist.length - 1];
System.arraycopy(nextlist, 0, newlist, 0, nextlist.length);
System.arraycopy(movelist, 0, newlist, nextlist.length, count);
movelist = newlist;
count += nextlist.length;
} else movelist[count++] = move;
}
return movelist;
}
private static int value(final int bowl, int beads) {
int value = beads / 13;
beads %= 13;
if (beads - bowl <= 0) return (value + beads);
else if (beads - bowl <= 6) return (value - beads + bowl + bowl);
else return (value - 12 + beads);
}
private board domoves(final intlist moves) {
if (moves == null) return this;
domove(moves.bowl);
return next.domoves(moves.list);
}
public void reset(final boolean capture, final boolean playall, final boolean finish) {
this.capture = capture;
this.playall = playall;
this.finish = finish;
if (next != null) next.reset(capture, playall, finish);
}
public intlist findmove(final Label l, final int depth, int best, final int cut, int thermo, int tstep) {
intlist movelist[] = listmoves(null);
gameover = movelist == null;
if (gameover || depth == 0) {
score = bowls[player] - bowls[7 - player];
for (int bowl = 1; bowl < 7; bowl++) score += value(bowl, bowls[player + bowl]) - value(bowl, bowls[7 - player + bowl]);
} else {
tstep /= movelist.length;
if (tstep > 0) l.setText(thermo / 100 + "%");
score = -Integer.MAX_VALUE;
num = 0;
for (int count = 0; count < movelist.length; count++) {
intlist move = movelist[count].reverse();
board result = domoves(move);
result.findmove(l, depth - 1, -cut, -best, thermo, tstep);
result.score = -result.score;
if (result.score > score) {
score = result.score;
if (score > cut) break;
if (score > best) best = score;
num = 0;
}
if (top) {
System.err.println(move + ":" + result.score);
if (result.score == score) movelist[num++] = move;
}
thermo += tstep;
}
if (top) {
l.setText("");
intlist move = movelist[(int)(Math.random() * num)];
System.err.println(move + ":" + score);
return move;
}
}
return null;
}
public int winner() {
if (score > 0) return player;
else if (score < 0) return 7 - player;
else return -7;
}
}
public final class mancala extends java.applet.Applet implements Runnable {
int bowl = 0, player = 0;
bowl bowls[];
board position;
intlist moves;
Thread thread;
Choice p1, p2;
Label l1, l2;
Button b;
Frame f;
boolean capture, playall, finish;
public synchronized void init() {
Container comp = this;
while (comp != null && !(comp instanceof Frame)) comp = comp.getParent();
f = (Frame)comp;
position = new board();
bowls = new bowl[14];
p1 = new choice();
p2 = new choice();
p1.addItem("Human");
p2.addItem("Human");
for (int i = 1; i <= 9; i++) {
String s = "Level " + i;
p1.addItem(s);
p2.addItem(s);
}
GridBagConstraints c = new GridBagConstraints();
GridBagLayout l = new GridBagLayout();
super.setLayout(l);
c.insets = new Insets(2, 2, 2, 2);
c.fill = c.HORIZONTAL;
c.gridheight = 1;
c.gridwidth = 1;
c.weighty = 0;
c.weightx = 1;
c.gridx = 0;
c.gridy = 0;
l.setConstraints(super.add(p1), c);
c.gridy = 6;
l.setConstraints(super.add(l1 = new Label("", Label.CENTER)), c);
c.gridx = 7;
l.setConstraints(super.add(p2), c);
c.gridy = 0;
l.setConstraints(super.add(l2 = new Label("", Label.CENTER)), c);
c.fill = c.NONE;
c.gridwidth = 6;
c.gridx = 1;
c.gridy = 3;
l.setConstraints(super.add(b = new Button("New Game")), c);
c.fill = c.BOTH;
c.gridwidth = 1;
c.gridheight = 3;
c.weighty = 1;
c.gridx = 0;
c.gridy = 2;
l.setConstraints(super.add(bowls[0] = new bowl(0)), c);
c.gridx = 7;
l.setConstraints(super.add(bowls[7] = new bowl(7)), c);
c.gridy = 0;
for (c.gridx = 1; c.gridx <= 6; c.gridx++)
l.setConstraints(super.add(bowls[c.gridx] = new bowl(c.gridx)), c);
c.gridy = 4;
for (c.gridx = 1; c.gridx <= 6; c.gridx++)
l.setConstraints(super.add(bowls[14 - c.gridx] = new bowl(14 - c.gridx)), c);
reset(true);
threadstart();
}
public synchronized void destroy() {
threadstop();
}
public void threadstart() {
thread = new Thread(this, "Mancala");
thread.start();
try { // for appletviewer 1.1
b.requestFocus();
} catch (Exception e) {
}
}
private int getParameter(final String name, final int value) {
try {
return Integer.parseInt(super.getParameter(name));
} catch (Exception e) {
return value;
}
}
private boolean getParameter(final String name, final boolean value) {
return value != String.valueOf(!value).equalsIgnoreCase(super.getParameter(name));
}
public void reset(final boolean b) {
if (b) {
capture = getParameter("capture", false);
playall = getParameter("playall", false);
finish = getParameter("finish", false);
p1.select(getParameter("upper", 0));
p2.select(getParameter("lower", 0));
}
final int beads = getParameter("beads", 4);
position.reset(capture, playall, finish);
moves = null;
player = 0;
bowl = 0;
l1.setText("");
l2.setText("");
bowls[0].empty();
bowls[7].empty();
for (int i = 1; i < 7; i++) {
bowls[i].empty();
bowls[i].add(beads);
bowls[i + 7].empty();
bowls[i + 7].add(beads);
}
position.copy(bowls, player);
}
public void threadstop() {
if (thread != null) {
thread.stop();
thread = null;
}
}
public synchronized boolean action(final Event evt, final Object what) {
if (evt.target == b) {
threadstop();
reset(false);
threadstart();
} else if (what != null && what instanceof intlist) {
threadstop();
moves = (intlist)what;
threadstart();
}
return false;
}
public boolean mouseMove(final Event evt, final int mx, final int my) {
return true;
}
public boolean mouseEnter(final Event evt, final int mx, final int my) {
return true;
}
public boolean mouseExit(final Event evt, final int mx, final int my) {
return true;
}
private synchronized void play() throws InterruptedException {
int beads;
StringBuffer status = new StringBuffer();
String sep = player == 0 ? "Upper player is playing " : "Lower player is playing ";
while (moves != null) {
int bowl = moves.bowl;
status.append(sep).append(bowl);
showStatus(status.toString());
sep = ", ";
bowl src = bowls[bowl];
for (beads = src.getbeads(); beads > 0; beads--) {
do bowl = bowl == 0 ? 13 : bowl - 1;
while (!playall && bowl == 7 - player);
src.remove();
bowls[bowl].add();
Thread.sleep(250);
}
if (bowl != player) {
if (player == (bowl < 7 ? 0 : 7) && bowls[bowl].issingle() && (capture || !bowls[14 - bowl].isempty())) {
bowls[player].add(bowls[14 - bowl].empty());
if (capture) bowls[player].add(bowls[bowl].empty());
Thread.sleep(250);
}
player = 7 - player;
}
for (bowl = 1; bowl < 7; bowl++) if (!bowls[bowl].isempty()) break;
if (bowl == 7) {
player = finish ? 0 : 7;
for (bowl = 8; bowl < 14; bowl++) bowls[player].add(bowls[bowl].empty());
Thread.sleep(250);
} else {
for (bowl = 8; bowl < 14; bowl++) if (!bowls[bowl].isempty()) break;
if (bowl == 14) {
player = finish ? 7 : 0;
for (bowl = 1; bowl < 7; bowl++) bowls[player].add(bowls[bowl].empty());
Thread.sleep(250);
}
}
moves = moves.list;
}
}
public void run() {
try {
if (f != null) f.setCursor(f.WAIT_CURSOR);
for (int i = 0; i < 14; i++) bowls[i].setclickable(false);
do {
play();
position.copy(bowls, player);
if (player == 0) {
showStatus("Upper player is thinking...");
moves = position.findmove(l1, p1.getSelectedIndex(), -Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 10000);
} else {
showStatus("Lower player is thinking...");
moves = position.findmove(l2, p2.getSelectedIndex(), -Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 10000);
}
} while (moves != null);
if (position.gameover) {
switch (position.winner()) {
case 0:
showStatus("Upper player has won.");
break;
case 7:
showStatus("Lower player has won.");
break;
default:
showStatus("Game has finished drawn.");
break;
}
} else {
for (int i = player + 1; i <= player + 6; i++) bowls[i].setclickable(true);
showStatus(player == 0 ? "Upper player to move." : "Lower player to move.");
}
} finally {
thread = null;
if (f != null) f.setCursor(f.DEFAULT_CURSOR);
return;
}
}
public String getAppletInfo() { // for appletviewer 1.1
return "Mancala Applet © 1997-2000 Neil Rashbrook";
}
public String[][] getParameterInfo() { // for appletviewer 1.1
return new String[][] {
{"beads", "int", "Beads per bowl"},
{"capture", "boolean", "Score capturing bead"},
{"playall", "boolean", "Play in all bowls"},
{"finish", "boolean", "Finisher wins remaining beads"},
{"upper", "int", "Level of upper player"},
{"lower", "int", "Level of lower player"}};
}
}

Frames Version
Customization Page
Back to Mancala Page

619614
38.107.191.95