![Java中国象棋博弈程序探秘[5]——搜索算法,第1张](/aiimages/Java%E4%B8%AD%E5%9B%BD%E8%B1%A1%E6%A3%8B%E5%8D%9A%E5%BC%88%E7%A8%8B%E5%BA%8F%E6%8E%A2%E7%A7%98%5B5%5D%E2%80%94%E2%80%94%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95.png "Java中国象棋博弈程序探秘[5]——搜索算法,第1张")
转载请保留作者信息：
作者：88250
Blog：http:/blog.csdn.net/DL88250
MSN & Gmail & QQ：[email protected]
搜索是电脑棋手AI的核心，有效的搜索算法很关键。本文给出了一些常用的搜索算法代码，以及这些算法的改进。例如配合置换表，历史启发表，开局库。算法的深入学习可以参考注释里给出的地址 : )
/* * @(#)SearchEngine.java * Author: 88250 <[email protected]>, 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 <[email protected]>, 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 <code>null</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); long estimatedTime = System.nanoTime() - startTime; System.out.println("Evaluated node count: " + Situation.nodeEvaluatedCount); System.out.println("TT hit count: " + TranspositionTable.hashHitCount); System.out.println("Best motion: " + instance.bestMotion.toString()); System.out.println("Elapsed Time: " + estimatedTime / 1000000000.0 + "s"); System.out.println(""); } /** * Finds the best move on the specified chessboard situation. * @param boardSituation the specified chessboard situation * @return the evaluate value */ public int findTheBestMove(int[][] boardSituation) { TranspositionTable.initHashCode(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 = situation.generatePossibleMoves(); for (Motion motion : motions) { situation.makeMove(motion.fromX, motion.fromY, motion.toX, motion.toY); if (book.exists(situation.chessboard)) { // this situation exists in book! bestMotion = motion; situation.unMove(); return true; } situation.unMove(); } return false; } /** * Basic Alpha-Beta 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 cut-off) */ final int basicAlphaBetaSearch(int depth, int alpha, int beta) { if (situation.gameOver() != 0) { return -WIN; } if (depth <= 0) { return situation.evaluate(); } List<Motion> motions = situation.generatePossibleMoves(); for (Motion motion : motions) { situation.makeMove(motion.fromX, motion.fromY, motion.toX, motion.toY); int score = -basicAlphaBetaSearch(depth - 1, -beta, -alpha); situation.unMove(); if (score > alpha) { alpha = score; if (depth == SEARCH_DEPTH) { bestMotion = motion; } if (alpha >= beta) { return beta; } } } return alpha; } /** * Alpha-Beta 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 cut-off) */ @SuppressWarnings("unchecked") final int alphaBetaWithHistoryHeuristicSearch(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); } // XXX do sort algorithm by myself for performance? Collections.sort(motions); } for (Motion motion : motions) { situation.makeMove(motion.fromX, motion.fromY, motion.toX, motion.toY); int score = -alphaBetaWithHistoryHeuristicSearch(depth - 1, -beta, -alpha); situation.unMove(); if (score > alpha) { alpha = score; HistoryHeuristicTable.setValue(motion.fromX, motion.fromY, motion.toX, motion.toY, (HistoryHeuristicTable.getValue( motion.fromX, motion.fromY, motion.toX, motion.toY) + 2 << depth)); if (depth == SEARCH_DEPTH) { bestMotion = motion; } if (alpha >= beta) { return beta; } } } return alpha; } /** * Principal Variation SearchEngine method. * <p>Probably the best of the alpha-beta 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 alpha-beta 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 * zero-width window to test each successive move against the first * move. Only if the zero-width search fails does it do a normal search. * </p> * <p> * More detalis, please visits:<br> * <a href="http://www.ics.uci.edu/~eppstein/180a/index.html"> * ICS 180, Winter 1999: Strategy and board game programming</a><br> * or Read this paper:<br> * Alexander Reinefild, AN IMPROVEMENT TO THE SCOUT TREE SEARCH ALGORITHM, * 1983 * </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 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 (best > alpha) { 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 (score > alpha && score < beta) { // fail high, re-search best = -principalVariationSearch(depth - 1, -beta, -score); if (depth == SEARCH_DEPTH) { bestMotion = motion; } } else if (score > best) { 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 (best > alpha) { 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 (score > alpha && score < beta) { best = -principalVariationWithHHSearch(depth - 1, -beta, -score); if (depth == SEARCH_DEPTH) { bestMotion = motion; } } else if (score > best) { 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 (score > alpha) { 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 (t > a && t < beta && i > 0) { 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; } }
/* * @(#)Book.java * Author: 88250 <[email protected]>, 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 <[email protected]>, 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 <code>true</code>, otherwise, * returns <code>false</code> */ final public boolean exists(int[][] chessboard) { FEN f = hashMap.get(TranspositionTable.calcCurHashCode(chessboard)); if (f != null && f.isBlackDone == false) { return true; } return false; } }
/* * @(#)HistoryHeuristicTable.java * Author: 88250 <[email protected]>, 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 <em>History Heuristic Table</em> maintains all best motion in * the past. * ({@link cn.edu.ynu.sei.chinesechess.common.Motion#value}) * @author 88250 <[email protected]>, 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 */ final static void setValue(int fromX, int fromY, int toX, int toY, int newValue) { holds[fromX][fromY][toX][toY] = newValue; } } /* * @(#)TranspositionTable.java * Author: 88250 <[email protected]>, 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 <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 88250 <[email protected]>, 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> * <li>15: 14 kinds of chessman, from 1 to 14</li> * </li>9, 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[2][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 <code>88250</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 return 88250; } /** * 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 chessman's destination * @param toY y coordinate of which chessman's destination * @param chessmanId the target position's 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 != 0) { // 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 chessman's destination * @param toY y coordinate of which chessman's 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 != 0) { // 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 item's value had evaluated */ exact, /** * the hash item's value is low bound */ lowerBound, /** * the hash item's value is upper bound */ upperBound, /** * the hash item's value is unknown */ unknown }; /** * Hash item description. */ final class HashNode { /** * 32-bits hash code */ int hashCode; /** * item's type */ NodeType type = NodeType.unknown; /** * search depth */ int depth; /** * item's value */ int value; } }
可以把代码贴到带Javadoc查看的IDE里看一下，那样比较清晰 : )
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）