carfield.com.hk

AbstractGraphSearch.java

2002-01-20T16:00:00Z

import java.util.Vector;

abstract public class AbstractGraphSearch {

public void addNode(String name, int x, int y) {
	System.out.println("Adding node: " + name + ", " + x + ", " + y);
	nodeNames[numNodes] = name;
	node_x[numNodes] = x;
	node_y[numNodes] = y;
	numNodes++;
    }

public int getNumNodes() { return numNodes; }
    public int getNumLinks() { return numLinks; }

public String getNodeName(int index) {
	try {
	    return nodeNames[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodeName: " + e);
	}
	return "no name"; // error condition
    }

public int getNodeX(int index) {
	try {
	    return node_x[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodePosition: " + e);
	}
	return 0;  // error condition
    }

public int getNodeY(int index) {
	try {
	    return node_y[index];
	} catch (Exception e) {
	    System.out.println("Error in getNodePosition: " + e);
	}
	return 0;  // error condition
    }

public int getLink1(int index) {
      return link_1[index];
    }

public int getLink2(int index) {
      return link_2[index];
    }

public void addLink(int node1, int node2) {
	link_1[numLinks] = node1;
	link_2[numLinks] = node2;
	int dist_squared =
	    (node_x[node1] - node_x[node2]) * (node_x[node1] - node_x[node2]) +
	    (node_y[node1] - node_y[node2]) * (node_y[node1] - node_y[node2]);
	lengths[numLinks] = (int)Math.sqrt(dist_squared);
	numLinks++;
    }

public void addLink(String name1, String name2) {
	int index1 = -1, index2 = -1;
	for (int i=0; i<numNodes; i++) {
	 if (name1.equals(nodeNames[i])) index1 = i;
	 if (name2.equals(nodeNames[i])) index2 = i;
	}
	if (index1 != -1 && index2 != -1) addLink(index1, index2);
 }

/** findPath - abstract method that is defined in subclasses */
    abstract public int [] findPath(int start_node, int goal_node); // return an array of node indices

protected int getNodeIndex(String name) {
	for (int i=0; i<numNodes; i++) {
	 if (name.equals(nodeNames[i])) return i;
	}
	return -1; // error condition
 }

final public static int MAX = 50; // max number of nodes and max number of links

protected int [] path = new int[AbstractGraphSearch.MAX];
    protected int num_path = 0;

// for nodes:
    protected String [] nodeNames = new String[MAX];
    protected int [] node_x = new int[MAX];
    protected int [] node_y = new int[MAX];
    // for links between nodes:
    protected int [] link_1 = new int[MAX];
    protected int [] link_2 = new int[MAX];
    protected int [] lengths = new int[MAX];

protected int numNodes = 0;
    protected int numLinks = 0;

protected int goalNodeIndex = -1, startNodeIndex = -1;

}

BreadthFirstSearch.java

2002-01-20T16:00:00Z

public class BreadthFirstSearch extends AbstractGraphSearch {

/** findPath - abstract method in super class */
    public int [] findPath(int start_node, int goal_node) { // return an array of node indices
	System.out.println("Entered BreadthFirstSearch.findPath(" +
			   start_node + ", " + goal_node + ")");
	// data structures for depth first search:
	boolean [] alreadyVisitedFlag = new boolean[numNodes];
	int [] predecessor = new int[numNodes];
	IntQueue queue = new IntQueue(numNodes + 2);

for (int i=0; i<numNodes; i++) {
	 alreadyVisitedFlag[i] = false;
	 predecessor[i] = -1;
	}

alreadyVisitedFlag[start_node] = true;
	queue.addToBackOfQueue(start_node);
outer:	while (queue.isEmpty() == false) {
	 int head = queue.peekAtFrontOfQueue();
	 int [] connected = connected_nodes(head);
	 if (connected != null) {
		for (int i=0; i<connected.length; i++) {
		 if (alreadyVisitedFlag[connected[i]] == false) {
			predecessor[connected[i]] = head;
			queue.addToBackOfQueue(connected[i]);
			if (connected[i] == goal_node) break outer; // we are done
		 }
		}
		alreadyVisitedFlag[head] = true;
		queue.removeFromQueue(); // ignore return value
	 }
	}
	// now calculate the shortest path from the predecessor array:
	int [] ret = new int[numNodes + 1];
	int count = 0;
	ret[count++] = goal_node;
	for (int i=0; i<numNodes; i++) {
	 ret[count] = predecessor[ret[count - 1]];
	 count++;
	 if (ret[count - 1] == start_node) break; // back to starting node
	}
	int [] ret2 = new int[count];
	for (int i=0; i<count; i++) {
	 ret2[i] = ret[count - 1 - i];
	}
	return ret2;
 }

protected class IntQueue {
	public IntQueue(int num) {
	    queue = new int[num];
	    head = tail = 0;
	    len = num;
	}
	public IntQueue() {
	    this(400);
	}
	private int [] queue;
	int tail, head, len;
	public void addToBackOfQueue(int n) {
	    queue[tail] = n;
	    if (tail >= (len - 1)) {
		tail = 0;
	    } else {
		tail++;
	    }
	}
	public int removeFromQueue() {
	    int ret = queue[head];
	    if (head >= (len - 1)) {
		head = 0;
	    } else {
		head++;
	    }
	    return ret;
	}
	public boolean isEmpty() {
	    return head == (tail + 1);
	}
	public int peekAtFrontOfQueue() {
	    return queue[head];
	}
    }

protected int [] connected_nodes(int node) {
	int [] ret = new int[AbstractGraphSearch.MAX];
	int num = 0;

for (int n=0; n<numNodes; n++) {
	 boolean connected = false;
	 // See if there is a link between node 'node' and 'n':
	 for (int i=0; i<numLinks; i++) {
		if (link_1[i] == node) {
		 if (link_2[i] == n) {
			connected = true;
			break;
		 }
		}
		if (link_2[i] == node) {
		 if (link_1[i] == n) {
			connected = true;
			break;
		 }
		}
	 }
	 if (connected) {
		ret[num++] = n;
	 }
	}
	if (num == 0) return null;
	int [] ret2 = new int[num];
	for (int i=0; i<num; i++) {
	 ret2[i] = ret[i];
	}
	return ret2;
 }

}

DepthFirstSearch.java

2002-01-20T16:00:00Z

public class DepthFirstSearch extends AbstractGraphSearch {

/** findPath - abstract method in super class */
    public int [] findPath(int start_node, int goal_node) { // return an array of node indices
        System.out.println("Entered DepthFirstSearch.findPath(" +
                           start_node + ", " + goal_node + ")");
        path[0] = start_node;
        return findPathHelper(path, 1, goal_node);
    }

public int [] findPathHelper(int [] path, int num_path, int goal_node) {
 System.out.println("Entered DepthFirstSearch.findPathHelper(...," +
 num_path + ", " + goal_node + ")");
 if (goal_node == path[num_path - 1]) {
 int [] ret = new int[num_path];
 for (int i=0; i<num_path; i++) ret[i] = path[i];
 return ret; // we are done!
 }
 int [] new_nodes = connected_nodes(path, num_path);
 if (new_nodes != null) {
 for (int j=0; j<new_nodes.length; j++) {
 path[num_path] = new_nodes[j];
 int [] test = findPathHelper(path, num_path + 1, goal_node);
 if (test != null) {
 if (test[test.length - 1] == goal_node) {
 return test;
 }
 }
 }
 }
 return null;
 }

protected int [] connected_nodes(int [] path, int num_path) {
 // find all nodes connected to the last node on 'path'
 // that are not already on 'path'
 int [] ret = new int[AbstractGraphSearch.MAX];
 int num = 0;
 int last_node = path[num_path - 1];
 for (int n=0; n<numNodes; n++) {
 // see if node 'n' is already on 'path':
 boolean keep = true;
 for (int i=0; i<num_path; i++) {
 if (n == path[i]) {
 keep = false;
 break;
 }
 }
 boolean connected = false;
 if (keep) {
 // now see if there is a link between node 'last_node' and 'n':
 for (int i=0; i<numLinks; i++) {
 if (link_1[i] == last_node) {
 if (link_2[i] == n) {
 connected = true;
 break;
 }
 }
 if (link_2[i] == last_node) {
 if (link_1[i] == n) {
 connected = true;
 break;
 }
 }
 }
 if (connected) {
 ret[num++] = n;
 }
 }
 }
 if (num == 0) return null;
 int [] ret2 = new int[num];
 for (int i=0; i<num; i++) {
 ret2[i] = ret[i];
 }
 return ret2;
 }

}

GraphBreadthFirstSearch.java

2002-01-20T16:00:00Z

import javax.swing.*;
import java.awt.*;

public class GraphBreadthFirstSearch extends JFrame {
  JPanel jPanel1 = new JPanel();

public GraphBreadthFirstSearch() {
    BreadthFirstSearch engine = new BreadthFirstSearch();
	  // Define a test network before calling the super class 'init':
	  engine.addNode("0", 20, 40);
	  engine.addNode("1", 60, 60);
	  engine.addNode("2", 100, 40);
	  engine.addNode("3", 50, 110);
	  engine.addNode("4", 140, 80);
	  engine.addNode("5", 160, 150);
	  engine.addNode("6", 200, 80);
	  engine.addNode("7", 160, 40);
	  engine.addNode("8", 240, 120);
	  engine.addNode("9", 260, 90);

engine.addLink(0,1);
	 engine.addLink(1,2);
	 engine.addLink(2,3);
	 engine.addLink(2,4);
	 engine.addLink(4,5);
	 engine.addLink(4,6);
	 engine.addLink(6,8);
	 engine.addLink(8,9);
	 engine.addLink(2,7);
	 engine.addLink(7,9);
 System.out.println("Before calculating path");
 path = engine.findPath(0, 9);
 System.out.println("After calculating path:");
 for (int i=0; i<path.length; i++) {
 System.out.println(" node # " + path[i]);
 }
 this.engine = engine;
 try {
 jbInit();
 }
 catch(Exception e) {
 e.printStackTrace();
 }
 }
 private int [] path = null;
 private BreadthFirstSearch engine = null;

public static void main(String[] args) {
    GraphBreadthFirstSearch graphBreadthFirstSearch1 = new GraphBreadthFirstSearch();
  }

private void jbInit() throws Exception {
    this.setDefaultCloseOperation(3);
    jPanel1.setBackground(Color.white);
    this.getContentPane().add(jPanel1, BorderLayout.CENTER);
    this.setSize(290, 180);
    this.setVisible(true);
  }
    protected void paintNode(Graphics g, String name, int x, int y) {
	int len = name.length() * 10 + 6;
	int x1 = x - (len / 2);
	int x2 = x + (len / 2);
	int y1 = y - 10;
	int y2 = y + 10;
	g.setColor(Color.cyan);
	g.fill3DRect(x1, y1, len, 20, true);
	g.setColor(Color.black);
	g.drawString(name, x1 + 4, y2 - 6);
    }

public void paint(Graphics g) {
	super.paint(g);
	if (engine != null && path != null) {
 int numNodes = engine.getNumNodes();
 int numLinks = engine.getNumLinks();
 for (int i=0; i<numLinks; i++) {
 int l1 = engine.getLink1(i);
 int l2 = engine.getLink2(i);
 int x1 = engine.getNodeX(l1);
 int y1 = engine.getNodeY(l1);
 int x2 = engine.getNodeX(l2);
 int y2 = engine.getNodeY(l2);
 g.setColor(Color.lightGray);
 g.drawLine(x1, y1, x2, y2);
 }
 for (int i=1; i<path.length; i++) {
 int x1 = engine.getNodeX(path[i-1]);
 int y1 = engine.getNodeY(path[i-1]);
 int x2 = engine.getNodeX(path[i]);
 int y2 = engine.getNodeY(path[i]);
 g.setColor(Color.black);
 g.drawLine(x1, y1, x2, y2);
 }
 for (int i=0; i<numNodes; i++) {
 int x1 = engine.getNodeX(i);
 int y1 = engine.getNodeY(i);
 paintNode(g, engine.getNodeName(i), x1, y1);
 }
 }
 }

}

GraphDepthFirstSearch.java

2002-01-20T16:00:00Z

import javax.swing.*;
import java.awt.*;

public class GraphDepthFirstSearch extends JFrame {
  JPanel jPanel1 = new JPanel();

public GraphDepthFirstSearch() {
    DepthFirstSearch engine = new DepthFirstSearch();
	  // Define a test network before calling the super class 'init':
	  engine.addNode("0", 20, 40);
	  engine.addNode("1", 60, 60);
	  engine.addNode("2", 100, 40);
	  engine.addNode("3", 50, 110);
	  engine.addNode("4", 140, 80);
	  engine.addNode("5", 160, 150);
	  engine.addNode("6", 200, 80);
	  engine.addNode("7", 160, 40);
	  engine.addNode("8", 240, 120);
	  engine.addNode("9", 260, 90);

public static void main(String[] args) {
    GraphDepthFirstSearch graphDepthFirstSearch1 = new GraphDepthFirstSearch();
  }

}

Maze.java

2002-01-19T16:00:00Z

import java.awt.Dimension;

/**
 * Class Maze - private class for representing search space as a two-dimensional maze
 */
public class Maze {
 public static short OBSTICLE = -1;
 public static short START_LOC_VALUE = -2;
 public static short GOAL_LOC_VALUE = -3;
 private int width = 0;
 private int height = 0;
 public Dimension startLoc = new Dimension();
 public Dimension goalLoc = new Dimension();
 /**
 * The maze (or search space) data is stored as a short integer rather than
 * as a boolean so that bread-first style searches can use the array to store
 * search depth. A value of -1 indicates a barrier in the maze.
 */
 private short [][]maze;
 public Maze(int width, int height) {
 System.out.println("New maze of size " + width + " by " + height);
 this.width = width;
 this.height = height;
 maze = new short[width+2][height+2];
 for (int i=0; i<width+2; i++) {
 for (int j=0; j<height+2; j++) {
 maze[i][j] = 0;
 }
 }
 for (int i=0; i<height+2; i++) {
 maze[0][i] = maze[width+1][i] = OBSTICLE;
 }
 for (int i=0; i<width+2; i++) {
 maze[i][0] = maze[i][height+1] = OBSTICLE;
 }
 /**
 * Randomize the maze by putting up arbitray obsticals
 */
 int max_obsticles = (width * height) / 3;
 for (int i=0; i<max_obsticles; i++) {
 int x = (int)(Math.random()*width);
 int y = (int)(Math.random()*height);
 setValue(x, y, OBSTICLE);
 }
 /**
 * Specify the starting location
 */
 startLoc.width = 0;
 startLoc.height = 0;
 setValue(0, 0, (short)0);
 /**
 * Specify the goal location
 */
 goalLoc.width = width - 1;
 goalLoc.height = height - 1;
 setValue(width - 1, height - 1, GOAL_LOC_VALUE);
 }
 synchronized public short getValue(int x, int y) { return maze[x+1][y+1]; }
 synchronized public void setValue(int x, int y, short value) { maze[x+1][y+1] = value; }
 public int getWidth() { return width; }
 public int getHeight() { return height; }
}

MazeBreadthFirstSearch.java

2002-01-19T16:00:00Z

import javax.swing.*;
import java.awt.*;
import java.awt.image.*;
import java.awt.event.*;
/**
 * Title: MazeBreadthFirstSearch
 * Description: Demo program for Java AI Programming
 * Copyright: Copyright (c) Mark Watson, Released under Open Source Artistic License
 * Company: Mark Watson Associates
 * @author Mark Watson
 * @version 1.0
 */

public class MazeBreadthFirstSearch extends javax.swing.JFrame {
    JPanel jPanel1 = new JPanel();
    BreadthFirstSearchEngine currentSearchEngine = null;

public MazeBreadthFirstSearch() {
        try {
          jbInit();
        } catch (Exception e) {
          System.out.println("GUI initilization error: " + e);
        }
        currentSearchEngine = new BreadthFirstSearchEngine(10, 10);
        repaint();
    }

public void paint(Graphics g_unused) {
 if (currentSearchEngine == null) return;
 Maze maze = currentSearchEngine.getMaze();
 int width = maze.getWidth();
 int height = maze.getHeight();
 System.out.println("Size of current maze: " + width + " by " + height);
 Graphics g = jPanel1.getGraphics();
 BufferedImage image = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
 Graphics g2 = image.getGraphics();
 g2.setColor(Color.white);
 g2.fillRect(0, 0, 320, 320);
 g2.setColor(Color.black);
 for (int x=0; x<width; x++) {
 for (int y=0; y<height; y++) {
 short val = maze.getValue(x,y);
 if ( val == Maze.OBSTICLE) {
 g2.setColor(Color.lightGray);
 g2.fillRect(6 + x * 28, 3 + y * 29, 29, 30);
 } else if (val == Maze.START_LOC_VALUE || (x==0 && y==0)) {
 g2.setColor(Color.blue);
 g2.drawString("S", 16 + x * 28, 19 + y * 29);
 } else if (val == Maze.GOAL_LOC_VALUE) {
 g2.setColor(Color.red);
 g2.drawString("G", 16 + x * 28, 19 + y * 29);
 }
 }
 }
 // redraw the path in black:
 g2.setColor(Color.black);
 Dimension [] path = currentSearchEngine.getPath();
 for (int i=1; i< (path.length-1); i++) {
 int x = path[i].width;
 int y = path[i].height;
 short val = maze.getValue(x,y);
 g2.drawString("" + (path.length - i), 16 + x * 28, 19 + y * 29);
 }
 g.drawImage(image, 30, 40, 320, 320, null);

}

public static void main(String[] args) {
        MazeBreadthFirstSearch mazeSearch1 = new MazeBreadthFirstSearch();
    }

private void jbInit() throws Exception {

this.setContentPane(jPanel1);
        this.setCursor(null);
        this.setDefaultCloseOperation(3);
        this.setTitle("MazeBreadthFirstSearch");
        this.getContentPane().setLayout(null);
        jPanel1.setBackground(Color.white);
        jPanel1.setDebugGraphicsOptions(DebugGraphics.NONE_OPTION);
        jPanel1.setDoubleBuffered(false);
        jPanel1.setRequestFocusEnabled(false);
        jPanel1.setLayout(null);
        this.setSize(370, 420);
        this.setVisible(true);
    }
}

MazeDepthFirstSearch.java

2002-01-19T16:00:00Z

import javax.swing.*;
import java.awt.*;
import java.awt.image.*;
import java.awt.event.*;
/**
 * Title: MazeDepthFirstSearch
 * Description: Demo program for Java AI Programming
 * Copyright: Copyright (c) Mark Watson, Released under Open Source Artistic License
 * Company: Mark Watson Associates
 * @author Mark Watson
 * @version 1.0
 */

public class MazeDepthFirstSearch extends javax.swing.JFrame {
    JPanel jPanel1 = new JPanel();
    DepthFirstSearchEngine currentSearchEngine = null;

public MazeDepthFirstSearch() {
        try {
          jbInit();
        } catch (Exception e) {
          System.out.println("GUI initilization error: " + e);
        }
        currentSearchEngine = new DepthFirstSearchEngine(10, 10);
        repaint();
    }

public void paint(Graphics g_unused) {
 if (currentSearchEngine == null) return;
 Maze maze = currentSearchEngine.getMaze();
 int width = maze.getWidth();
 int height = maze.getHeight();
 System.out.println("Size of current maze: " + width + " by " + height);
 Graphics g = jPanel1.getGraphics();
 BufferedImage image = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
 Graphics g2 = image.getGraphics();
 g2.setColor(Color.white);
 g2.fillRect(0, 0, 320, 320);
 g2.setColor(Color.black);
 for (int x=0; x<width; x++) {
 for (int y=0; y<height; y++) {
 short val = maze.getValue(x,y);
 if ( val == Maze.OBSTICLE) {
 g2.setColor(Color.lightGray);
 g2.fillRect(6 + x * 28, 3 + y * 29, 29, 30);
 } else if (val == Maze.START_LOC_VALUE || val == 1) {
 g2.setColor(Color.blue);
 g2.drawString("S", 16 + x * 28, 19 + y * 29);
 } else if (val == Maze.GOAL_LOC_VALUE) {
 g2.setColor(Color.red);
 g2.drawString("G", 16 + x * 28, 19 + y * 29);
 } else if (val > 0) {
 //g2.setColor(Color.green);
 //g2.drawString("" + val, 16 + x * 28, 19 + y * 29);
 }
 }
 }
 // redraw the path in black:
 g2.setColor(Color.black);
 Dimension [] path = currentSearchEngine.getPath();
 for (int i=1; i< path.length; i++) {
 int x = path[i].width;
 int y = path[i].height;
 short val = maze.getValue(x,y);
 g2.drawString("" + val, 16 + x * 28, 19 + y * 29);
 }
 g.drawImage(image, 30, 40, 320, 320, null);

}

public static void main(String[] args) {
        MazeDepthFirstSearch mazeSearch1 = new MazeDepthFirstSearch();
    }

private void jbInit() throws Exception {

this.setContentPane(jPanel1);
        this.setCursor(null);
        this.setDefaultCloseOperation(3);
        this.setTitle("MazeDepthFirstSearch");
        this.getContentPane().setLayout(null);
        jPanel1.setBackground(Color.white);
        jPanel1.setDebugGraphicsOptions(DebugGraphics.NONE_OPTION);
        jPanel1.setDoubleBuffered(false);
        jPanel1.setRequestFocusEnabled(false);
        jPanel1.setLayout(null);
        this.setSize(370, 420);
        this.setVisible(true);
    }
}

Chess$aMove.class

2000-06-01T16:00:00Z

Chess.class

2000-06-01T16:00:00Z

Chess.java

2000-06-01T16:00:00Z

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
 };
}

jprobe.jpl

2000-06-01T16:00:00Z

out.txt

2000-06-01T16:00:00Z

Board position:

BR BN BB BQ BK BB BN BR
BP BP BP BP BP BP BP BP
. . . .
. . . .
. . . .
. . . .
WP WP WP WP WP WP WP WP
WR WN WB WQ WK WB WN WR
Your move:
enter a move like 'd2d4' or 'oo'
s=d2d4
From 35, to 55
Board position:

BR BN BB BQ BK BB BN BR
BP BP BP BP BP BP BP BP
. . . .
. . . .
. WP . .
. . . .
WP WP WP . WP WP WP WP
WR WN WB WQ WK WB WN WR
next element: 5.4
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,]
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,]
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,]
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,]
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,]
Board position:

BR BN BB BQ BK BB BN BR
BP BP BP BP . BP BP BP
. . BP . .
. . . .
. WP . .
. . . .
WP WP WP . WP WP WP WP
WR WN WB WQ WK WB WN WR
Your move:
enter a move like 'd2d4' or 'oo'
s=g1f3
From 28, to 47
Board position:

BR BN BB BQ BK BB BN BR
BP BP BP BP . BP BP BP
. . BP . .
. . . .
. WP . .
. . . WN .
WP WP WP . WP WP WP WP
WR WN WB WQ WK WB . WR
next element: 6.1999993
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,]
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,]
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,]
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,]
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,]
Board position:

BR BN BB . BK BB BN BR
BP BP BP BP . BP BP BP
. . BP BQ .
. . . .
. WP . .
. . . WN .
WP WP WP . WP WP WP WP
WR WN WB WQ WK WB . WR
Your move:
enter a move like 'd2d4' or 'oo'
java.lang.NullPointerException

ChessPosition.java

2000-05-30T16:00:00Z

GameSearch.class

2000-05-30T16:00:00Z

GameSearch.java

2000-05-30T16:00:00Z

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); 
 }
 }
}

Move.class

2000-05-30T16:00:00Z

Move.java

2000-05-30T16:00:00Z

Position.class

2000-05-30T16:00:00Z

Position.java

2000-05-30T16:00:00Z

TicTacToe.class

2000-05-30T16:00:00Z

TicTacToe.java

2000-05-30T16:00:00Z

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);
 }
}

TicTacToeMove.class

2000-05-30T16:00:00Z

TicTacToePosition.class

2000-05-30T16:00:00Z

TicTacToePosition.java

2000-05-30T16:00:00Z