搜索是电脑棋手AI的核心有效的搜索算法很关键本文给出了一些常用的搜索算法代码以及这些算法的改进例如配合置换表历史启发表开局库算法的深入学习可以参考注释里给出的地址 : )
view plaincopy to clipboardprint?
/*
* @(#)SearchEnginejava
* Author: <>
* Created on May :: AM
*
* 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 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 Library General Public License for more details
*
* You should have received a copy of the GNU General Public License
* along with this program; if not write to the Free Software
* Foundation Inc Temple Place Suite Boston MA USA
*/
package cneduynuseichinesechessinfrastructuresearch;
import cneduynuseichinesechesmonMotion;
import cneduynuseichinesechesmonSituation;
import cneduynuseichinesechessinfrastructuresearchTranspositionTableNodeType;
import javautilCollections;
import javautilList;
/**
* This class descripts some search algorithms of game tree
* @author <>
* @version Jun
*/
public class SearchEngine {
/**
* value while win a game
*/
public static final int WIN = ;
/**
* chessboard situation
*/
public Situation situation;
/**
* the best move
*/
public Motion bestMotion;
/**
* situation libaray
*/
private Book book = new Book();
/**
* default search depth
*/
public static int SEARCH_DEPTH = ;
/**
* For Performance Test
* @param args should be <code>null</code>
*/
public static void main(String[] args) {
SearchEngine instance;
instance = new SearchEngine(new Situation());
Systemoutprintln(Getting start search!);
long startTime = SystemnanoTime();
//instancebasicAlphaBetaSearch(SEARCH_DEPTH WIN WIN);
//instancealphaBetaWithHistoryHeuristicSearch(SEARCH_DEPTH WIN WIN);
//instancealphaBetaWithTranspositonSearch(SEARCH_DEPTH WIN WIN);
//instanceprincipalVariationSearch(SEARCH_DEPTH WIN WIN);
//instanceprincipalVariationWithHHSearch(SEARCH_DEPTH WIN WIN);
instancenegaScoutWithHHTTSearch(SEARCH_DEPTH WIN WIN);
long estimatedTime = SystemnanoTime() startTime;
Systemoutprintln(Evaluated node count: + SituationnodeEvaluatedCount);
Systemoutprintln(TT hit count: + TranspositionTablehashHitCount);
Systemoutprintln(Best motion: + instancebestMotiontoString());
Systemoutprintln(Elapsed Time: + estimatedTime / + s);
Systemoutprintln();
}
/**
* Finds the best move on the specified chessboard situation
* @param boardSituation the specified chessboard situation
* @return the evaluate value
*/
public int findTheBestMove(int[][] boardSituation) {
TranspositionTableinitHashCode(boardSituation);
return negaScoutWithHHTTSearch(SEARCH_DEPTH WIN WIN);
}
/**
* Search the FEN book for a good move
* @return if find a move in the book retusns <code>true</code>
* otherwise returns <code>false</code>
*/
public boolean bookSearch() {
List<Motion> motions = situationgeneratePossibleMoves();
for (Motion motion : motions) {
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
if (bookexists(situationchessboard)) {
// this situation exists in book!
bestMotion = motion;
situationunMove();
return true;
}
situationunMove();
}
return false;
}
/**
* Basic AlphaBeta search method
* @param depth depth of search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
final int basicAlphaBetaSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
for (Motion motion : motions) {
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = basicAlphaBetaSearch(depth beta alpha);
situationunMove();
if (score > alpha) {
alpha = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha >= beta) {
return beta;
}
}
}
return alpha;
}
/**
* AlphaBeta with History Heuristic search method
* @param depth depth of search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
@SuppressWarnings(unchecked)
final int alphaBetaWithHistoryHeuristicSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motionvalue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX motiontoY);
}
// XXX do sort algorithm by myself for performance?
Collectionssort(motions);
}
for (Motion motion : motions) {
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = alphaBetaWithHistoryHeuristicSearch(depth beta alpha);
situationunMove();
if (score > alpha) {
alpha = score;
HistoryHeuristicTablesetValue(motionfromX motionfromY
motiontoX motiontoY
(HistoryHeuristicTablegetValue(
motionfromX
motionfromY
motiontoX
motiontoY) +
<< depth));
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha >= beta) {
return beta;
}
}
}
return alpha;
}
/**
* Principal Variation SearchEngine method
* <p>Probably the best of the alphabeta variants this goes by
* several names: <em><b>NegaScout</b></em> <em>Principal Variation SearchEngine</em>
* or <em>PVS</em> for short The idea is that alphabeta search works
* best if the first recursive search is likely to be the one
* with the best score Techniques such as sorting the move list
* or using a best move stored in the hash table make it especially
* likely that the first move is best If it is we can search
* the other moves more quickly by using the assumption that
* they are not likely to be as good So PVS performs that first
* search with a normal window but on subsequent searches uses a
* zerowidth window to test each successive move against the first
* move Only if the zerowidth search fails does it do a normal search
* </p>
* <p>
* More detalis please visits:<br>
* <a >
* ICS Winter : Strategy and board game programming</a><br>
* or Read this paper:<br>
* Alexander Reinefild AN IMPROVEMENT TO THE SCOUT TREE SEARCH ALGORITHM
*
* </p>
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
final int principalVariationSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
situationmakeMove(motionsget()fromX motionsget()fromY
motionsget()toX motionsget()toY);
int best = principalVariationSearch(depth beta alpha);
situationunMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motionsget();
}
for (int i = ; i < motionssize(); i++) {
if (best < beta) {
if (best > alpha) {
alpha = best;
}
Motion motion = motionsget(i);
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = principalVariationSearch(depth alpha alpha);
if (score > alpha && score < beta) {
// fail high research
best = principalVariationSearch(depth beta score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (score > best) {
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situationunMove();
}
}
return best;
}
/**
* Principal Variation with History Heuristic SearchEngine method(failsoft version)
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
@SuppressWarnings(unchecked)
final int principalVariationWithHHSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motionvalue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX motiontoY);
}
Collectionssort(motions);
}
Motion motion = motionsget();
situationmakeMove(motionfromX motionfromY
motiontoX motiontoY);
int best = principalVariationWithHHSearch(depth beta alpha);
situationunMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
int oldValue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX
motiontoY);
HistoryHeuristicTablesetValue(motionsget()fromX
motionsget()fromY
motionsget()toX
motionsget()toY
(oldValue + << depth));
}
for (int i = ; i < motionssize(); i++) {
if (best < beta) {
if (best > alpha) {
alpha = best;
}
motion = motionsget(i);
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = principalVariationWithHHSearch(depth alpha
alpha);
if (score > alpha && score < beta) {
best = principalVariationWithHHSearch(depth beta score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (score > best) {
int oldValue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX
motiontoY);
HistoryHeuristicTablesetValue(motionfromX
motionfromY
motiontoX
motiontoY
(oldValue + << depth));
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situationunMove();
}
}
return best;
}
/**
* AlphaBeta with Transposition Table search method
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
final int alphaBetaWithTranspositonSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
// lookup transposition table
int score = TranspositionTablelookup(depth alpha beta);
if (score != ) {
// hit the target!
return score;
}
if (depth <= ) {
score = situationevaluate();
// save the node
TranspositionTablesave(NodeTypeexact depth score);
return score;
}
NodeType hashItemType = NodeTypeunknown;
List<Motion> motions = situationgeneratePossibleMoves();
for (Motion motion : motions) {
int toId = situationmakeMove(motionfromX motionfromY motiontoX
motiontoY);
score = alphaBetaWithTranspositonSearch(depth beta alpha);
situationunMove();
if (score > alpha) {
alpha = score;
hashItemType = NodeTypeexact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha >= beta) {
TranspositionTablesave(NodeTypelowerBound depth alpha);
return beta;
}
}
}
if (hashItemType != NodeTypeunknown) {
TranspositionTablesave(NodeTypeexact depth alpha);
} else {
TranspositionTablesave(NodeTypeupperBound depth alpha);
}
return alpha;
}
/**
* NegaScout with History Heuristic and Transposition Table search
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
@SuppressWarnings(unchecked)
final int negaScoutWithHHTTSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
// lookup transpositiont table
int score = TranspositionTablelookup(depth alpha beta);
if (score != ) {
// hit the target!
return score;
}
if (depth <= ) {
score = situationevaluate();
TranspositionTablesave(NodeTypeexact depth score);
return score;
}
List<Motion> motions = situationgeneratePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motionvalue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX motiontoY);
}
Collectionssort(motions);
}
int bestmove = ;
int a = alpha;
int b = beta;
int t;
int oldValue;
NodeType hashItemType = NodeTypeunknown;
for (int i = ; i < motionssize(); i++) {
Motion motion = motionsget(i);
int toId = situationmakeMove(motionfromX motionfromY motiontoX
motiontoY);
t = negaScoutWithHHTTSearch(depth b a);
if (t > a && t < beta && i > ) {
a = negaScoutWithHHTTSearch(depth beta t);
hashItemType = NodeTypeexact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
bestmove = i;
}
situationunMove();
if (a < t) {
hashItemType = NodeTypeexact;
a = t;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
if (a >= beta) {
TranspositionTablesave(NodeTypelowerBound depth a);
oldValue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX
motiontoY);
HistoryHeuristicTablesetValue(motionfromX
motionfromY
motiontoX
motiontoY
(oldValue + << depth));
return a;
}
b = a + ; // set a new numm window
}
oldValue = HistoryHeuristicTablegetValue(motionsget(bestmove)fromX
motionsget(bestmove)fromY
motionsget(bestmove)toX
motionsget(bestmove)toY);
HistoryHeuristicTablesetValue(motionsget(bestmove)fromX
motionsget(bestmove)fromY
motionsget(bestmove)toX
motionsget(bestmove)toY
(oldValue + << depth));
if (hashItemType != NodeTypeunknown) {
TranspositionTablesave(NodeTypeexact depth alpha);
} else {
TranspositionTablesave(NodeTypeupperBound depth alpha);
}
return a;
}
/**
* Constructor with parameters
* @param situation the specified situation
*/
public SearchEngine(Situation situation) {
thissituation = situation;
}
}
/*
* @(#)SearchEnginejava
* Author: <>
* Created on May :: AM
*
* 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 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 Library General Public License for more details
*
* You should have received a copy of the GNU General Public License
* along with this program; if not write to the Free Software
* Foundation Inc Temple Place Suite Boston MA USA
*/
package cneduynuseichinesechessinfrastructuresearch;
import cneduynuseichinesechesmonMotion;
import cneduynuseichinesechesmonSituation;
import cneduynuseichinesechessinfrastructuresearchTranspositionTableNodeType;
import javautilCollections;
import javautilList;
/**
* This class descripts some search algorithms of game tree
* @author <>
* @version Jun
*/
public class SearchEngine {
/**
* value while win a game
*/
public static final int WIN = ;
/**
* chessboard situation
*/
public Situation situation;
/**
* the best move
*/
public Motion bestMotion;
/**
* situation libaray
*/
private Book book = new Book();
/**
* default search depth
*/
public static int SEARCH_DEPTH = ;
/**
* For Performance Test
* @param args should be <code>null</code>
*/
public static void main(String[] args) {
SearchEngine instance;
instance = new SearchEngine(new Situation());
Systemoutprintln(Getting start search!);
long startTime = SystemnanoTime();
//instancebasicAlphaBetaSearch(SEARCH_DEPTH WIN WIN);
//instancealphaBetaWithHistoryHeuristicSearch(SEARCH_DEPTH WIN WIN);
//instancealphaBetaWithTranspositonSearch(SEARCH_DEPTH WIN WIN);
//instanceprincipalVariationSearch(SEARCH_DEPTH WIN WIN);
//instanceprincipalVariationWithHHSearch(SEARCH_DEPTH WIN WIN);
instancenegaScoutWithHHTTSearch(SEARCH_DEPTH WIN WIN);
long estimatedTime = SystemnanoTime() startTime;
Systemoutprintln(Evaluated node count: + SituationnodeEvaluatedCount);
Systemoutprintln(TT hit count: + TranspositionTablehashHitCount);
Systemoutprintln(Best motion: + instancebestMotiontoString());
Systemoutprintln(Elapsed Time: + estimatedTime / + s);
Systemoutprintln();
}
/**
* Finds the best move on the specified chessboard situation
* @param boardSituation the specified chessboard situation
* @return the evaluate value
*/
public int findTheBestMove(int[][] boardSituation) {
TranspositionTableinitHashCode(boardSituation);
return negaScoutWithHHTTSearch(SEARCH_DEPTH WIN WIN);
}
/**
* Search the FEN book for a good move
* @return if find a move in the book retusns <code>true</code>
* otherwise returns <code>false</code>
*/
public boolean bookSearch() {
List<Motion> motions = situationgeneratePossibleMoves();
for (Motion motion : motions) {
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
if (bookexists(situationchessboard)) {
// this situation exists in book!
bestMotion = motion;
situationunMove();
return true;
}
situationunMove();
}
return false;
}
/**
* Basic AlphaBeta search method
* @param depth depth of search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
final int basicAlphaBetaSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
for (Motion motion : motions) {
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = basicAlphaBetaSearch(depth beta alpha);
situationunMove();
if (score > alpha) {
alpha = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha >= beta) {
return beta;
}
}
}
return alpha;
}
/**
* AlphaBeta with History Heuristic search method
* @param depth depth of search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
@SuppressWarnings(unchecked)
final int alphaBetaWithHistoryHeuristicSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motionvalue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX motiontoY);
}
// XXX do sort algorithm by myself for performance?
Collectionssort(motions);
}
for (Motion motion : motions) {
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = alphaBetaWithHistoryHeuristicSearch(depth beta alpha);
situationunMove();
if (score > alpha) {
alpha = score;
HistoryHeuristicTablesetValue(motionfromX motionfromY
motiontoX motiontoY
(HistoryHeuristicTablegetValue(
motionfromX
motionfromY
motiontoX
motiontoY) +
<< depth));
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha >= beta) {
return beta;
}
}
}
return alpha;
}
/**
* Principal Variation SearchEngine method
* <p>Probably the best of the alphabeta variants this goes by
* several names: <em><b>NegaScout</b></em> <em>Principal Variation SearchEngine</em>
* or <em>PVS</em> for short The idea is that alphabeta search works
* best if the first recursive search is likely to be the one
* with the best score Techniques such as sorting the move list
* or using a best move stored in the hash table make it especially
* likely that the first move is best If it is we can search
* the other moves more quickly by using the assumption that
* they are not likely to be as good So PVS performs that first
* search with a normal window but on subsequent searches uses a
* zerowidth window to test each successive move against the first
* move Only if the zerowidth search fails does it do a normal search
* </p>
* <p>
* More detalis please visits:<br>
* <a >
* ICS Winter : Strategy and board game programming</a><br>
* or Read this paper:<br>
* Alexander Reinefild AN IMPROVEMENT TO THE SCOUT TREE SEARCH ALGORITHM
*
* </p>
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
final int principalVariationSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
situationmakeMove(motionsget()fromX motionsget()fromY
motionsget()toX motionsget()toY);
int best = principalVariationSearch(depth beta alpha);
situationunMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motionsget();
}
for (int i = ; i < motionssize(); i++) {
if (best < beta) {
if (best > alpha) {
alpha = best;
}
Motion motion = motionsget(i);
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = principalVariationSearch(depth alpha alpha);
if (score > alpha && score < beta) {
// fail high research
best = principalVariationSearch(depth beta score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (score > best) {
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situationunMove();
}
}
return best;
}
/**
* Principal Variation with History Heuristic SearchEngine method(failsoft version)
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
@SuppressWarnings(unchecked)
final int principalVariationWithHHSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
if (depth <= ) {
return situationevaluate();
}
List<Motion> motions = situationgeneratePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motionvalue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX motiontoY);
}
Collectionssort(motions);
}
Motion motion = motionsget();
situationmakeMove(motionfromX motionfromY
motiontoX motiontoY);
int best = principalVariationWithHHSearch(depth beta alpha);
situationunMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
int oldValue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX
motiontoY);
HistoryHeuristicTablesetValue(motionsget()fromX
motionsget()fromY
motionsget()toX
motionsget()toY
(oldValue + << depth));
}
for (int i = ; i < motionssize(); i++) {
if (best < beta) {
if (best > alpha) {
alpha = best;
}
motion = motionsget(i);
situationmakeMove(motionfromX motionfromY motiontoX motiontoY);
int score = principalVariationWithHHSearch(depth alpha
alpha);
if (score > alpha && score < beta) {
best = principalVariationWithHHSearch(depth beta score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (score > best) {
int oldValue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX
motiontoY);
HistoryHeuristicTablesetValue(motionfromX
motionfromY
motiontoX
motiontoY
(oldValue + << depth));
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situationunMove();
}
}
return best;
}
/**
* AlphaBeta with Transposition Table search method
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
final int alphaBetaWithTranspositonSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
// lookup transposition table
int score = TranspositionTablelookup(depth alpha beta);
if (score != ) {
// hit the target!
return score;
}
if (depth <= ) {
score = situationevaluate();
// save the node
TranspositionTablesave(NodeTypeexact depth score);
return score;
}
NodeType hashItemType = NodeTypeunknown;
List<Motion> motions = situationgeneratePossibleMoves();
for (Motion motion : motions) {
int toId = situationmakeMove(motionfromX motionfromY motiontoX
motiontoY);
score = alphaBetaWithTranspositonSearch(depth beta alpha);
situationunMove();
if (score > alpha) {
alpha = score;
hashItemType = NodeTypeexact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha >= beta) {
TranspositionTablesave(NodeTypelowerBound depth alpha);
return beta;
}
}
}
if (hashItemType != NodeTypeunknown) {
TranspositionTablesave(NodeTypeexact depth alpha);
} else {
TranspositionTablesave(NodeTypeupperBound depth alpha);
}
return alpha;
}
/**
* NegaScout with History Heuristic and Transposition Table search
* @param depth depth search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if game is over returns <code>WIN</code> if depth arrived
* returns evaluat value(leaf node value) otherwise returns bound(
* determined by cutoff)
*/
@SuppressWarnings(unchecked)
final int negaScoutWithHHTTSearch(int depth int alpha int beta) {
if (situationgameOver() != ) {
return WIN;
}
// lookup transpositiont table
int score = TranspositionTablelookup(depth alpha beta);
if (score != ) {
// hit the target!
return score;
}
if (depth <= ) {
score = situationevaluate();
TranspositionTablesave(NodeTypeexact depth score);
return score;
}
List<Motion> motions = situationgeneratePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motionvalue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX motiontoY);
}
Collectionssort(motions);
}
int bestmove = ;
int a = alpha;
int b = beta;
int t;
int oldValue;
NodeType hashItemType = NodeTypeunknown;
for (int i = ; i < motionssize(); i++) {
Motion motion = motionsget(i);
int toId = situationmakeMove(motionfromX motionfromY motiontoX
motiontoY);
t = negaScoutWithHHTTSearch(depth b a);
if (t > a && t < beta && i > ) {
a = negaScoutWithHHTTSearch(depth beta t);
hashItemType = NodeTypeexact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
bestmove = i;
}
situationunMove();
if (a < t) {
hashItemType = NodeTypeexact;
a = t;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
if (a >= beta) {
TranspositionTablesave(NodeTypelowerBound depth a);
oldValue = HistoryHeuristicTablegetValue(motionfromX
motionfromY
motiontoX
motiontoY);
HistoryHeuristicTablesetValue(motionfromX
motionfromY
motiontoX
motiontoY
(oldValue + << depth));
return a;
}
b = a + ; // set a new numm window
}
oldValue = HistoryHeuristicTablegetValue(motionsget(bestmove)fromX
motionsget(bestmove)fromY
motionsget(bestmove)toX
motionsget(bestmove)toY);
HistoryHeuristicTablesetValue(motionsget(bestmove)fromX
motionsget(bestmove)fromY
motionsget(bestmove)toX
motionsget(bestmove)toY
(oldValue + << depth));
if (hashItemType != NodeTypeunknown) {
TranspositionTablesave(NodeTypeexact depth alpha);
} else {
TranspositionTablesave(NodeTypeupperBound depth alpha);
}
return a;
}
/**
* Constructor with parameters
* @param situation the specified situation
*/
public SearchEngine(Situation situation) {
thissituation = situation;
}
}
view plaincopy to clipboardprint?
/*
* @(#)Bookjava
* Author: <>
* Created on Jun :: PM
*
* 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 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 Library General Public License for more details
*
* You should have received a copy of the GNU General Public License
* along with this program; if not write to the Free Software
* Foundation Inc Temple Place Suite Boston MA USA
*/
package cneduynuseichinesechessinfrastructuresearch;
import cneduynuseichinesechesmonSituation;
import cneduynuseichinesechessinfrastructurefenFEN;
import cneduynuseichinesechessinfrastructurefenFENAccessor;
import javautilHashMap;
import javautilList;
import javautilMap;
/**
* Opening book endgame book or any chessboard situation book
* Currently this class ONLY can read FEN file
* @author <>
* @version Jun
*/
final public class Book {
/**
* book situation hash map
*/
public Map<Integer FEN> hashMap = new HashMap<Integer FEN>();
/**
* Packaged default constructor
*/
Book() {
List<FEN> fens = FENAccessorreadFile(book_final);
Integer hashCode = ;
for (FEN fen : fens) {
hashCode = TranspositionTablecalcCurHashCode(fenchessboard);
hashMapput(hashCode fen);
}
}
/**
* This book exists the specified chessboard situation?
* @param chessboard the specified chessboard
* @return if exists returns <code>true</code> otherwise
* returns <code>false</code>
*/
final public boolean exists(int[][] chessboard) {
FEN f = hashMapget(TranspositionTablecalcCurHashCode(chessboard));
if (f != null && fisBlackDone == false) {
return true;
}
return false;
}
}
/*
* @(#)Bookjava
* Author: <>
* Created on Jun :: PM
*
* 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 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 Library General Public License for more details
*
* You should have received a copy of the GNU General Public License
* along with this program; if not write to the Free Software
* Foundation Inc Temple Place Suite Boston MA USA
*/
package cneduynuseichinesechessinfrastructuresearch;
import cneduynuseichinesechesmonSituation;
import cneduynuseichinesechessinfrastructurefenFEN;
import cneduynuseichinesechessinfrastructurefenFENAccessor;
import javautilHashMap;
import javautilList;
import javautilMap;
/**
* Opening book endgame book or any chessboard situation book
* Currently this class ONLY can read FEN file
* @author <>
* @version Jun
*/
final public class Book {
/**
* book situation hash map
*/
public Map<Integer FEN> hashMap = new HashMap<Integer FEN>();
/**
* Packaged default constructor
*/
Book() {
List<FEN> fens = FENAccessorreadFile(book_final);
Integer hashCode = ;
for (FEN fen : fens) {
hashCode = TranspositionTablecalcCurHashCode(fenchessboard);
hashMapput(hashCode fen);
}
}
/**
* This book exists the specified chessboard situation?
* @param chessboard the specified chessboard
* @return if exists returns <code>true</code> otherwise
* returns <code>false</code>
*/
final public boolean exists(int[][] chessboard) {
FEN f = hashMapget(TranspositionTablecalcCurHashCode(chessboard));
if (f != null && fisBlackDone == false) {
return true;
}
return false;
}
}
view plaincopy to clipboardprint?
/*
* @(#)HistoryHeuristicTablejava
* Author: <>
* Created on May :: PM
*
* 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 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 Library General Public License for more details
*
* You should have received a copy of the GNU General Public License
* along with this program; if not write to the Free Software
* Foundation Inc Temple Place Suite Boston MA USA
*/
package cneduynuseichinesechessinfrastructuresearch;
/**
* A <em>History Heuristic Table</em> maintains all best motion in
* the past
* ({@link cneduynumonMotion#value})
* @author <>
* @version Jun
*/
final class HistoryHeuristicTable {
/**
* hold all best moves
*/
static int[][][][] holds = new int[][][][];
/**
* singleton
*/
private static HistoryHeuristicTable instance = new HistoryHeuristicTable();
/**
* Gets the single instance of the class
* @return history heuristic instance
*/
final public static HistoryHeuristicTable getInstance() {
if (instance == null) {
instance = new HistoryHeuristicTable();
}
return instance;
}
/**
* Private default constructor
*/
private HistoryHeuristicTable() {
}
/**
* Returns the history motion
* @param fromX x coordinate of which chessman do this move
* @param fromY y coordinate of which chessman do this move
* @param toX x coordinate of which chessmans destination
* @param toY y coordinate of which chessmans destination
* @return this moves value
*/
final static int getValue(int fromX int fromY int toX int toY) {
return holds[fromX][fromY][toX][toY];
}
/**
* Sets the history motion
* @param fromX x coordinate of which chessman do this move
* @param fromY y coordinate of which chessman do this move
* @param toX x coordinate of which chessmans destination
* @param toY y coordinate of which chessmans destination
* @param newValue the new value
*/
final static void setValue(int fromX int fromY int toX int toY int newValue) {
holds[fromX][fromY][toX][toY] = newValue;
}
}
/*
* @(#)TranspositionTablejava
* Author: <>
* Created on Jun :: AM
*
* 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 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 Library General Public License for more details
*
* You should have received a copy of the GNU General Public License
* along with this program; if not write to the Free Software
* Foundation Inc Temple Place Suite Boston MA USA
*/
package cneduynuseichinesechessinfrastructuresearch;
import javautilRandom;
/**
* A <em>Transpositon Table</em> maintains a mass of node had evaluated
* In the table we use <code>HashTable</code> to store each game tree node
* @author <>
* @version Jun
*/
final public class TranspositionTable {
// XXX currently using bits hash code
/**
* transposition tables size
*/
final static int SIZE = * * ;
/**
* holds the chessboard condition<br>
* <ul>
* <li>: kinds of chessman from to </li>
* </li> : * matrics form chessboard
* </ul>
* @see cneduynuseichinesechesmonConstants
* @see cneduynuseichinesechesmonSituation#chessboard
*/
static int[][][] hashCodes = new int[][][];
/**
* the holds [ ] for min value and max value
*/
static HashNode[][] items = new HashNode[][SIZE];
/**
* a bits integer acts for current hash code
*/
static int curHashCode;
/**
* Transposition table hit count
*/
public static int hashHitCount = ;
/**
* singleton
*/
private static TranspositionTable instance = new TranspositionTable();
/**
* Gets the single instance
* @return transposition table single instance
*/
public static TranspositionTable getInstance() {
if (instance == null) {
instance = new TranspositionTable();
}
return instance;
}
/**
* Initializes the hash code of the specified chessboard situation
* @param chessboard the specified chessboard situation
*/
final static void initHashCode(int[][] chessboard) {
curHashCode = calcCurHashCode(chessboard);
}
/**
* Private default constructor
*/
private TranspositionTable() {
Random random = new Random();
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
for (int k = ; k < ; k++) {
hashCodes[i][j][k] = Mathabs(randomnextInt());
}
}
}
for (int i = ; i < ; i++) {
for (int j = ; j < SIZE; j++) {
items[i][j] = new HashNode();
}
}
}
/**
* Calculates the hash code for the specified chessboard situation
* @param chessboard the specified chessboar situation
* @return bits hash code
*/
final public static int calcCurHashCode(int[][] chessboard) {
int ret = ;
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
ret ^= hashCodes[chessboard[i][j]][i][j];
}
}
return ret;
}
/**
* Save a chessboard situation into transposition table
* @param type type of this hash item
* @param depth depth depth of search
* @param value value of this hash value
*/
final public static void save(NodeType type int depth int value) {
// depth % : for max for min
HashNode item = items[depth % ][curHashCode % SIZE];
itemdepth = depth;
itemhashCode = curHashCode;
itemtype = type;
itemvalue = value;
}
/**
* Lookup a chessboard situation in transposition table
* @param depth depth of search
* @param alpha min value to max value the floor
* @param beta max value to min value the ceiling
* @return if find the result returns value otherwise
* returns <code></code>
*/
final public static int lookup(int depth int alpha int beta) {
// depth % : for max for min
HashNode item = items[depth % ][curHashCode % SIZE];
if (itemdepth == depth && itemhashCode == curHashCode) {
hashHitCount++;
switch (itemtype) {
case exact:
return itemvalue;
case lowerBound:
if (itemvalue >= beta) {
return itemvalue;
} else {
break;
}
case upperBound:
if (itemvalue <= alpha) {
return itemvalue;
} else {
break;
}
}
}
// doesnt hit the target
return ;
}
/**
* Recovery the hash value of a motion had done
* @param fromX x coordinate of which chessman do this move
* @param fromY y coordinate of which chessman do this move
* @param toX x coordinate of which chessmans destination
* @param toY y coordinate of which chessmans destination
* @param chessmanId the target positions chessman
* @param chessboard current chessboard situation
*/
final public static void unMoveHash(int fromX int fromY int toX int toY
int chessmanId int[][] chessboard) {
int toId = chessboard[toX][toY];
// retrieves the random number before the motion done
curHashCode ^= hashCodes[toId][fromX][fromY];
// removes chessman which position is toId
curHashCode ^= hashCodes[toId][toX][toY];
if (chessmanId != ) {
// recovery hash value chessman be eaten
curHashCode ^= hashCodes[chessmanId][toX][toY];
}
}
/**
* Generates the hash value of a motion on the current situation
* @param fromX x coordinate of which chessman do this move
* @param fromY y coordinate of which chessman do this move
* @param toX x coordinate of which chessmans destination
* @param toY y coordinate of which chessmans destination
* @param chessboard current chessboard situation
*/
final public static void moveHash(int fromX int fromY int toX int toY
int[][] chessboard) {
int fromId toId;
fromId = chessboard[fromX][fromY];
toId = chessboard[toX][toY];
// removes chessman which position is fromId
curHashCode ^= hashCodes[fromId][fromX][fromY];
if (toId != ) {
// if toId position has a chessman removes it
curHashCode ^= hashCodes[toId][toX][toY];
}
// retrieves the random number at toId
curHashCode ^= hashCodes[fromId][toX][toY];
}
/**
* Hash item type description
*/
enum NodeType {
/**
* the hash items value had evaluated
*/
exact
/**
* the hash items value is low bound
*/
lowerBound
/**
* the hash items value is upper bound
*/
upperBound
/**
* the hash items value is unknown
*/
unknown
};
/**
* Hash item description
*/
final class HashNode {
/**
* bits hash code
*/
int hashCode;
/**
* items type
*/
NodeType type = NodeTypeunknown;
/**
* search depth
*/
int depth;
/**
* items value
*/
int value;
}
}
转载请保留作者信息
作者
Blog
MSN & Gmail & QQ
