搜索是电脑棋手AI的核心，有效的搜索算法很关键。本文给出了一些常用的搜索算法代码，以及这些算法的改进。例如配合置换表，历史启发表，开局库。算法的深入学习可以参考注释里给出的地址 : )
view plaincopy to clipboardprint? /*
* @(#)SearchEngine.java
* Author: 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* Created on May 24， 2008， 10:51:52 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 3 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.， 59 Temple Place - Suite 330， Boston， MA 02111-1307， USA.
*/
package cn.edu.ynu.sei.chinesechess.infrastructure.search;
import cn.edu.ynu.sei.chinesechess.infrastructure.common.Motion;
import cn.edu.ynu.sei.chinesechess.infrastructure.common.Situation;
import cn.edu.ynu.sei.chinesechess.infrastructure.search.TranspositionTable.NodeType;
import java.util.Collections;
import java.util.List;
/**
* This class descripts some search algorithms of game tree.
* @author 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* @version 1.1.2.6， Jun 7， 2008
*/
public class SearchEngine {
/**
* value while win a game
*/
public static final int WIN = 54;
/**
* 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 = 5;
/**
* For Performance Test.
* @param args should be <codenull</code
*/
public static void main(String[] args) {
SearchEngine instance;
instance = new SearchEngine(new Situation());
System.out.println("Getting start search!");
long startTime = System.nanoTime();
//instance.basicAlphaBetaSearch(SEARCH_DEPTH， -WIN， WIN);
//instance.alphaBetaWithHistoryHeuristicSearch(SEARCH_DEPTH， -WIN， WIN);
//instance.alphaBetaWithTranspositonSearch(SEARCH_DEPTH， -WIN， WIN);
//instance.principalVariationSearch(SEARCH_DEPTH， -WIN， WIN);
//instance.principalVariationWithHHSearch(SEARCH_DEPTH， -WIN， WIN);
instance.negaScoutWithHHTTSearch(SEARCH_DEPTH， -WIN， WIN);
[8][9]
long estimatedTime = System.nanoTime， otherwise， returns bound(
* determined by cut-off)
*/
final int principalVariationSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
if (depth <= 0) {
return situation.evaluate();
}
List<Motion motions = situation.generatePossibleMoves();
situation.makeMove(motions.get(0).fromX， motions.get(0).fromY，
motions.get(0).toX， motions.get(0).toY);
int best = -principalVariationSearch(depth - 1， -beta， -alpha);
situation.unMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motions.get(0);
}
for (int i = 1; i < motions.size(); i++) {
if (best < beta) {
if (bestalpha) {
alpha = best;
}
[8][9]
Motion motion = motions.get(i);
situation.makeMove(motion.fromX， motion.fromY， motion.toX， motion.toY);
int score = -principalVariationSearch(depth - 1， -alpha - 1， -alpha);
if (scorealpha && score < beta) {
// fail high， re-search
best = -principalVariationSearch(depth - 1， -beta， -score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (scorebest) {
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situation.unMove();
}
}
return best;
}
/**
* Principal Variation with History Heuristic SearchEngine method(fail-soft 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 cut-off)
*/
@SuppressWarnings("unchecked")
final int principalVariationWithHHSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
if (depth <= 0) {
return situation.evaluate();
}
List<Motion motions = situation.generatePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motion.value = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX， motion.toY);
}
Collections.sort(motions);
}
Motion motion = motions.get(0);
situation.makeMove(motion.fromX， motion.fromY，
motion.toX， motion.toY);
int best = -principalVariationWithHHSearch(depth - 1， -beta， -alpha);
situation.unMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
int oldValue = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY);
HistoryHeuristicTable.setValue(motions.get(0).fromX，
motions.get(0).fromY，
motions.get(0).toX，
motions.get(0).toY，
(oldValue + 2 << depth));
}
for (int i = 1; i < motions.size(); i++) {
if (best < beta) {
if (bestalpha) {
alpha = best;
}
motion = motions.get(i);
situation.makeMove(motion.fromX， motion.fromY， motion.toX， motion.toY);
int score = -principalVariationWithHHSearch(depth - 1， -alpha - 1，
-alpha);
if (scorealpha && score < beta) {
best = -principalVariationWithHHSearch(depth - 1， -beta， -score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (scorebest) {
int oldValue = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY);
HistoryHeuristicTable.setValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY，
(oldValue + 2 << depth));
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situation.unMove();
}
}
return best;
}
/**
* Alpha-Beta 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 cut-off)
*/
final int alphaBetaWithTranspositonSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
// lookup transposition table
int score = TranspositionTable.lookup(depth， alpha， beta);
if (score != 88250) {
// hit the target!
return score;
}
if (depth <= 0) {
score = situation.evaluate();
// save the node
TranspositionTable.save(NodeType.exact， depth， score);
return score;
}
NodeType hashItemType = NodeType.unknown;
List<Motion motions = situation.generatePossibleMoves();
for (Motion motion : motions) {
int toId = situation.makeMove(motion.fromX， motion.fromY， motion.toX，
motion.toY);
score = -alphaBetaWithTranspositonSearch(depth - 1， -beta， -alpha);
situation.unMove();
if (scorealpha) {
alpha = score;
hashItemType = NodeType.exact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha = beta) {
TranspositionTable.save(NodeType.lowerBound， depth， alpha);
return beta;
}
}
}
if (hashItemType != NodeType.unknown) {
TranspositionTable.save(NodeType.exact， depth， alpha);
} else {
TranspositionTable.save(NodeType.upperBound， 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 cut-off)
*/
@SuppressWarnings("unchecked")
final int negaScoutWithHHTTSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
// lookup transpositiont table
int score = TranspositionTable.lookup(depth， alpha， beta);
if (score != 88250) {
// hit the target!
return score;
}
if (depth <= 0) {
score = situation.evaluate();
[8][9]
TranspositionTable.save(NodeType.exact， depth， score);
return score;
}
List<Motion motions = situation.generatePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motion.value = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX， motion.toY);
}
Collections.sort(motions);
}
int bestmove = 0;
int a = alpha;
int b = beta;
int t;
int oldValue;
NodeType hashItemType = NodeType.unknown;
for (int i = 0; i < motions.size(); i++) {
Motion motion = motions.get(i);
int toId = situation.makeMove(motion.fromX， motion.fromY， motion.toX，
motion.toY);
t = -negaScoutWithHHTTSearch(depth - 1， -b， -a);
if (ta && t < beta && i0) {
a = -negaScoutWithHHTTSearch(depth - 1， -beta， -t);
hashItemType = NodeType.exact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
bestmove = i;
}
situation.unMove();
if (a < t) {
hashItemType = NodeType.exact;
a = t;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
if (a = beta) {
TranspositionTable.save(NodeType.lowerBound， depth， a);
oldValue = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY);
HistoryHeuristicTable.setValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY，
(oldValue + 2 << depth));
return a;
}
b = a + 1; // set a new numm window
}
oldValue = HistoryHeuristicTable.getValue(motions.get(bestmove).fromX，
motions.get(bestmove).fromY，
motions.get(bestmove).toX，
motions.get(bestmove).toY);
HistoryHeuristicTable.setValue(motions.get(bestmove).fromX，
motions.get(bestmove).fromY，
motions.get(bestmove).toX，
motions.get(bestmove).toY，
(oldValue + 2 << depth));
if (hashItemType != NodeType.unknown) {
TranspositionTable.save(NodeType.exact， depth， alpha);
} else {
TranspositionTable.save(NodeType.upperBound， depth， alpha);
}
return a;
}
/**
* Constructor with parameters.
* @param situation the specified situation
*/
public SearchEngine(Situation situation) {
this.situation = situation;
}
}
/*
* @(#)SearchEngine.java
* Author: 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* Created on May 24， 2008， 10:51:52 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 3 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.， 59 Temple Place - Suite 330， Boston， MA 02111-1307， USA.
*/
package cn.edu.ynu.sei.chinesechess.infrastructure.search;
import cn.edu.ynu.sei.chinesechess.infrastructure.common.Motion;
import cn.edu.ynu.sei.chinesechess.infrastructure.common.Situation;
import cn.edu.ynu.sei.chinesechess.infrastructure.search.TranspositionTable.NodeType;
import java.util.Collections;
import java.util.List;
/**
* This class descripts some search algorithms of game tree.
* @author 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* @version 1.1.2.6， Jun 7， 2008
*/
public class SearchEngine {
/**
* value while win a game
*/
public static final int WIN = 54;
/**
* 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 = 5;
/**
* For Performance Test.
* @param args should be <codenull</code
*/
public static void main(String[] args) {
SearchEngine instance;
instance = new SearchEngine(new Situation());
System.out.println("Getting start search!");
long startTime = System.nanoTime();
//instance.basicAlphaBetaSearch(SEARCH_DEPTH， -WIN， WIN);
[8][9]
//instance.alphaBetaWithHistoryHeuristicSearch， otherwise， returns bound(
* determined by cut-off)
*/
final int principalVariationSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
if (depth <= 0) {
return situation.evaluate();
}
List<Motion motions = situation.generatePossibleMoves();
situation.makeMove(motions.get(0).fromX， motions.get(0).fromY，
motions.get(0).toX， motions.get(0).toY);
int best = -principalVariationSearch(depth - 1， -beta， -alpha);
situation.unMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motions.get(0);
}
for (int i = 1; i < motions.size(); i++) {
if (best < beta) {
if (bestalpha) {
alpha = best;
}
Motion motion = motions.get(i);
situation.makeMove(motion.fromX， motion.fromY， motion.toX， motion.toY);
int score = -principalVariationSearch(depth - 1， -alpha - 1， -alpha);
if (scorealpha && score < beta) {
// fail high， re-search
best = -principalVariationSearch(depth - 1， -beta， -score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (scorebest) {
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situation.unMove();
}
}
return best;
}
/**
* Principal Variation with History Heuristic SearchEngine method(fail-soft 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 cut-off)
*/
@SuppressWarnings("unchecked")
final int principalVariationWithHHSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
if (depth <= 0) {
return situation.evaluate();
}
List<Motion motions = situation.generatePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motion.value = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX， motion.toY);
}
Collections.sort(motions);
}
Motion motion = motions.get(0);
situation.makeMove(motion.fromX， motion.fromY，
motion.toX， motion.toY);
int best = -principalVariationWithHHSearch(depth - 1， -beta， -alpha);
situation.unMove();
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
int oldValue = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY);
HistoryHeuristicTable.setValue(motions.get(0).fromX，
motions.get(0).fromY，
motions.get(0).toX，
motions.get(0).toY，
(oldValue + 2 << depth));
}
for (int i = 1; i < motions.size(); i++) {
if (best < beta) {
if (bestalpha) {
alpha = best;
}
motion = motions.get(i);
[8][9]
situation.makeMove(motion.fromX， motion.fromY， motion.toX， motion.toY);
int score = -principalVariationWithHHSearch(depth - 1， -alpha - 1，
-alpha);
if (scorealpha && score < beta) {
best = -principalVariationWithHHSearch(depth - 1， -beta， -score);
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
} else if (scorebest) {
int oldValue = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY);
HistoryHeuristicTable.setValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY，
(oldValue + 2 << depth));
best = score;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
situation.unMove();
}
}
return best;
}
/**
* Alpha-Beta 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 cut-off)
*/
final int alphaBetaWithTranspositonSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
// lookup transposition table
int score = TranspositionTable.lookup(depth， alpha， beta);
if (score != 88250) {
// hit the target!
return score;
}
if (depth <= 0) {
score = situation.evaluate();
// save the node
TranspositionTable.save(NodeType.exact， depth， score);
return score;
}
NodeType hashItemType = NodeType.unknown;
List<Motion motions = situation.generatePossibleMoves();
for (Motion motion : motions) {
int toId = situation.makeMove(motion.fromX， motion.fromY， motion.toX，
motion.toY);
score = -alphaBetaWithTranspositonSearch(depth - 1， -beta， -alpha);
situation.unMove();
if (scorealpha) {
alpha = score;
hashItemType = NodeType.exact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
if (alpha = beta) {
TranspositionTable.save(NodeType.lowerBound， depth， alpha);
return beta;
}
}
}
if (hashItemType != NodeType.unknown) {
TranspositionTable.save(NodeType.exact， depth， alpha);
} else {
TranspositionTable.save(NodeType.upperBound， 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 cut-off)
*/
@SuppressWarnings("unchecked")
final int negaScoutWithHHTTSearch(int depth， int alpha， int beta) {
if (situation.gameOver() != 0) {
return -WIN;
}
// lookup transpositiont table
int score = TranspositionTable.lookup(depth， alpha， beta);
if (score != 88250) {
// hit the target!
return score;
}
if (depth <= 0) {
score = situation.evaluate();
TranspositionTable.save(NodeType.exact， depth， score);
return score;
}
List<Motion motions = situation.generatePossibleMoves();
// History heuristic
if (depth < SEARCH_DEPTH) {
for (Motion motion : motions) {
motion.value = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX， motion.toY);
}
Collections.sort(motions);
}
int bestmove = 0;
int a = alpha;
int b = beta;
int t;
int oldValue;
NodeType hashItemType = NodeType.unknown;
for (int i = 0; i < motions.size(); i++) {
Motion motion = motions.get(i);
int toId = situation.makeMove(motion.fromX， motion.fromY， motion.toX，
motion.toY);
t = -negaScoutWithHHTTSearch(depth - 1， -b， -a);
if (ta && t < beta && i0) {
a = -negaScoutWithHHTTSearch(depth - 1， -beta， -t);
hashItemType = NodeType.exact;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
bestmove = i;
}
situation.unMove();
if (a < t) {
hashItemType = NodeType.exact;
a = t;
if (depth == SEARCH_DEPTH) {
bestMotion = motion;
}
}
if (a = beta) {
TranspositionTable.save(NodeType.lowerBound， depth， a);
oldValue = HistoryHeuristicTable.getValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY);
HistoryHeuristicTable.setValue(motion.fromX，
motion.fromY，
motion.toX，
motion.toY，
(oldValue + 2 << depth));
return a;
}
b = a + 1; // set a new numm window
}
oldValue = HistoryHeuristicTable.getValue(motions.get(bestmove).fromX，
motions.get(bestmove).fromY，
motions.get(bestmove).toX，
motions.get(bestmove).toY);
HistoryHeuristicTable.setValue(motions.get(bestmove).fromX，
motions.get(bestmove).fromY，
motions.get(bestmove).toX，
motions.get(bestmove).toY，
(oldValue + 2 << depth));
if (hashItemType != NodeType.unknown) {
TranspositionTable.save(NodeType.exact， depth， alpha);
} else {
TranspositionTable.save(NodeType.upperBound， depth， alpha);
}
return a;
}
/**
* Constructor with parameters.
* @param situation the specified situation
*/
public SearchEngine(Situation situation) {
this.situation = situation;
}
}
view plaincopy to clipboardprint? /*
* @(#)Book.java
* Author: 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* Created on Jun 5， 2008， 4:45:31 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 3 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.
*
[8][9]
* 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.， 59 Temple Place - Suite 330， Boston， MA 02111-1307， USA.
*/
package cn.edu.ynu.sei.chinesechess.infrastructure.search;
import cn.edu.ynu.sei.chinesechess.infrastructure.common.Situation;
import cn.edu.ynu.sei.chinesechess.infrastructure.fen.FEN;
import cn.edu.ynu.sei.chinesechess.infrastructure.fen.FENAccessor;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Opening book， endgame book， or any chessboard situation book.
* Currently， this class ONLY can read FEN file.
* @author 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* @version 1.0.0.0， Jun 5， 2008
*/
final public class Book {
/**
* book situation hash map
*/
public Map<Integer， FEN hashMap = new HashMap<Integer， FEN();
/**
* Packaged default constructor.
*/
Book() {
List<FEN fens = FENAccessor.readFile("book_final");
Integer hashCode = 0;
for (FEN fen : fens) {
hashCode = TranspositionTable.calcCurHashCode(fen.chessboard);
hashMap.put(hashCode， fen);
}
}
/**
* This book exists the specified chessboard situation?
* @param chessboard the specified chessboard
* @return if exists， returns <codetrue</code， otherwise，
* returns <codefalse</code
*/
final public boolean exists(int[][] chessboard) {
FEN f = hashMap.get(TranspositionTable.calcCurHashCode(chessboard));
if (f != null && f.isBlackDone == false) {
return true;
}
return false;
}
}
/*
* @(#)Book.java
* Author: 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* Created on Jun 5， 2008， 4:45:31 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 3 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.， 59 Temple Place - Suite 330， Boston， MA 02111-1307， USA.
*/
package cn.edu.ynu.sei.chinesechess.infrastructure.search;
import cn.edu.ynu.sei.chinesechess.infrastructure.common.Situation;
import cn.edu.ynu.sei.chinesechess.infrastructure.fen.FEN;
import cn.edu.ynu.sei.chinesechess.infrastructure.fen.FENAccessor;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Opening book， endgame book， or any chessboard situation book.
* Currently， this class ONLY can read FEN file.
* @author 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* @version 1.0.0.0， Jun 5， 2008
*/
final public class Book {
/**
* book situation hash map
*/
public Map<Integer， FEN hashMap = new HashMap<Integer， FEN();
/**
* Packaged default constructor.
*/
Book() {
List<FEN fens = FENAccessor.readFile("book_final");
Integer hashCode = 0;
for (FEN fen : fens) {
hashCode = TranspositionTable.calcCurHashCode(fen.chessboard);
hashMap.put(hashCode， fen);
}
}
/**
* This book exists the specified chessboard situation?
* @param chessboard the specified chessboard
* @return if exists， returns <codetrue</code， otherwise，
* returns <codefalse</code
*/
final public boolean exists(int[][] chessboard) {
FEN f = hashMap.get(TranspositionTable.calcCurHashCode(chessboard));
if (f != null && f.isBlackDone == false) {
return true;
}
return false;
}
}
view plaincopy to clipboardprint? /*
* @(#)HistoryHeuristicTable.java
* Author: 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* Created on May 29， 2008， 11:51:10 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 3 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.， 59 Temple Place - Suite 330， Boston， MA 02111-1307， USA.
*/
package cn.edu.ynu.sei.chinesechess.infrastructure.search;
/**
* A <emHistory Heuristic Table</em maintains all best motion in
* the past.
* ({@link cn.edu.ynu.sei.chinesechess.common.Motion#value})
* @author 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* @version 1.0.1.4， Jun 7， 2008
*/
final class HistoryHeuristicTable {
/**
* hold all best moves
*/
static int[][][][] holds = new int[9][10][9][10];
/**
* 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 chessman‘s destination
* @param toY y coordinate of which chessman‘s destination
* @return this move‘s 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 chessman‘s destination
* @param toY y coordinate of which chessman‘s destination
* @param newValue the new value
*/
[8][9]
final static void setValue(int fromX， int fromY， int toX， int toY， int newValue) {
holds[fromX][fromY][toX][toY] = newValue;
}
}
/*
* @(#)TranspositionTable.java
* Author: 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* Created on Jun 1， 2008， 11:04:57 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 3 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.， 59 Temple Place - Suite 330， Boston， MA 02111-1307， USA.
*/
package cn.edu.ynu.sei.chinesechess.infrastructure.search;
import java.util.Random;
/**
* A <emTranspositon Table</em maintains a mass of node had evaluated.
* In the table， we use <codeHashTable</code to store each game tree node.
* @author 88250 <DL88250@gmail.com， http://blog.csdn.net/DL88250
* @version 1.0.0.5， Jun 7， 2008
*/
final public class TranspositionTable {
// XXX currently， using 32-bits hash code
/**
* transposition table‘s size
*/
final static int SIZE = 1024 * 32 * 8;
/**
* holds the chessboard condition<br
* <ul
* <li15: 14 kinds of chessman， from 1 to 14</li
* </li9， 10: 9 * 10 matrics form chessboard
* </ul
* @see cn.edu.ynu.sei.chinesechess.infrastructure.common.Constants
* @see cn.edu.ynu.sei.chinesechess.infrastructure.common.Situation#chessboard
*/
static int[][][] hashCodes = new int[15][9][10];
/**
* the holds， [0， 1] for min value and max value
*/
static HashNode[][] items = new HashNode[SIZE];
/**
* a 32-bits integer， acts for current hash code
*/
static int curHashCode;
/**
* Transposition table hit count
*/
public static int hashHitCount = 0;
/**
* 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 = 0; i < 15; i++) {
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 10; k++) {
hashCodes[i][j][k] = Math.abs(random.nextInt());
}
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < SIZE; j++) {
items[i][j] = new HashNode();
}
}
}
/**
* Calculates the hash code for the specified chessboard situation.
* @param chessboard the specified chessboar situation
* @return 32-bits hash code
*/
final public static int calcCurHashCode(int[][] chessboard) {
int ret = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 10; 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 % 2: 0 for max， 1 for min
HashNode item = items[depth % 2][curHashCode % SIZE];
item.depth = depth;
item.hashCode = curHashCode;
item.type = type;
item.value = 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 <code88250</code
*/
final public static int lookup(int depth， int alpha， int beta) {
// depth % 2: 0 for max， 1 for min
HashNode item = items[depth % 2][curHashCode % SIZE];
if (item.depth == depth && item.hashCode == curHashCode) {
hashHitCount++;
switch (item.type) {
case exact:
return item.value;
case lowerBound:
if (item.value = beta) {
return item.value;
} else {
break;
}
case upperBound:
if (item.value <= alpha) {
return item.value;
} else {
break;
}
}
}
// doesn‘t hit the target
[8][9]
作者：88250
Blog：http:/blog.csdn.net/DL88250
MSN & Gmail & QQ：DL88250@gmail.com
[8][9]
