-
Notifications
You must be signed in to change notification settings - Fork 48
/
NegaScout.java
executable file
·133 lines (120 loc) · 4.46 KB
/
NegaScout.java
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
129
130
131
132
133
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Java Chess *
* Copyright (C) 2005 Arvydas Bancewicz *
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License for more details. *
* *
* You should have received a copy of the GNU General Public License *
* along with Java Chess; if not, write to the Free Software *
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
* * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*
* Created on Mar 16, 2005
*/
package chess.algorithms;
import java.io.Serializable;
import java.util.Vector;
import chess.core.*;
/**
* NegaScout, a subclass of MoveAlgorithm, is a negascout search algorithm.
* It is a variation of the "alfa-beta pruning" technique.
*
* @author Arvydas Bancewicz
*
*/
public class NegaScout extends MoveAlgorithm implements Serializable{
/**
* Create an negaScout algorithm object.
*/
public NegaScout() {
super();
}
/**
* Create an negaScout algorithm object with a game to use.
* @param game - The chess game to work with
*/
public NegaScout(ChessGame game) {
super(game);
}
/**
* Create an negaScout algorithm object with a board to use.
* @param board - The board to work with
*/
public NegaScout(Board board) {
super(board);
}
/**
* Get a reply in the form of a move. NOTE: the move is stored in mm
* @param white - White player ?
* @return the move
*/
public Move getReply(boolean white) {
System.out.println("\n"+(white?"White":"Black") + " replies with "+toString());
negaScout(white, -INFINITY, INFINITY, dd);
return mm;
}
/**
* The search algorithm, using methods found in the super class MoveAlgorithm,
* produces the best move result in mm
* @param white - White player ?
* @param alpha - The best score
* @param beta - The worst-case scenario for the opponent.
* @param depth - The number of levels in the tree to be searched.
* @return the estimated position value
*/
public int negaScout(boolean white, int alpha, int beta, int depth) {
if(isStopped())
return 0;
if(depth==0)
return estimate();
int best = -INFINITY;
int n = beta;
Vector v = successors(white);
if(v!=null) {
int siz = v.size();
if(depth==dd)
super.board.progress.setMaximum(v.size());
v = randomize(board.b, v);
if(v.size()>0 && depth==dd)
mm = (Move)v.elementAt(0);
while(v.size()>0 && best<beta) {
Move m = (Move)v.remove(0);
m.perform(board);
int est = -negaScout(!white, -n, -Math.max(alpha, best), depth-1);
if(est>best) {
if(n==beta || depth<=2) {
best = est;
if(depth==dd)
mm = m;
} else {
best = -negaScout(!white, -beta, -est, depth-1);
if(depth==dd)
mm = m;
}
}
m.undo(board);
n = Math.max(alpha, best)+1;
if (depth==dd) {
super.board.think.setText((mm==null?"":mm+" - ")+v.toString());
super.board.progress.setValue(siz-v.size());
}
}
}
return best;
}
/**
* Get the name of this algorithm
*/
public String toString() {
return "NegaScout";
}
}