forked from mark-watson/Java-AI-Book-Code
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGameSearch.java
More file actions
executable file
·128 lines (117 loc) · 4.73 KB
/
GameSearch.java
File metadata and controls
executable file
·128 lines (117 loc) · 4.73 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package search.game;
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 createMove();
/*
* 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 enum2 = v2.elements();
enum2.nextElement(); // skip previous value
while (enum2.hasMoreElements()) {
Object o = enum2.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 enum2 = best.elements();
while (enum2.hasMoreElements()) {
v3.addElement(enum2.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 = createMove();
startingPosition = makeMove(startingPosition, HUMAN, move);
printPosition(startingPosition);
Vector v = alphaBeta(0, startingPosition, PROGRAM);
Enumeration enum2 = v.elements();
while (enum2.hasMoreElements()) {
System.out.println(" next element: " + enum2.nextElement());
}
startingPosition = (Position)v.elementAt(1);
}
}
}