查表
我們的AI算法在開局會有搜索空間過大的情況，所以不能及時去發(fā)現(xiàn)比較好的解。這個時候我們可以用人類的經(jīng)驗去輔助它。因為開局的格式比較小，我們可以很容易枚舉完開局的前3步的可能性。這樣可以很好的提高它在開局時的速度。
我們?yōu)榱丝梢詼p少枚舉的狀態(tài)，可以做一個對旋轉(zhuǎn)，翻轉(zhuǎn)，平移的映射。這樣可以使得本來需要枚舉的情況可以極大的減少。比如說開局下斜著的4個角是等價。開局下水平和豎直也是等價。因為他們都可以通過旋轉(zhuǎn)，平移，和翻轉(zhuǎn)操作變化得到。
public enum PositionTranslator {
CLOCKWISE_0{
@Override
Position translate(int y, int x) {
return new Position(y, x);
}
@Override
Position deTranslate(int y, int x) {
return CLOCKWISE_0.translate(y, x);
}
}, CLOCKWISE_90{
@Override
Position translate(int y, int x) {
return new Position(-x, y);
}
@Override
Position deTranslate(int y, int x) {
return CLOCKWISE_270.translate(y, x);
}
}, CLOCKWISE_180{
@Override
Position translate(int y, int x) {
return new Position(-y,-x);
}
@Override
Position deTranslate(int y, int x) {
return CLOCKWISE_180.translate(y, x);
}
}, CLOCKWISE_270{
@Override
Position translate(int y, int x) {
return new Position(x, -y);
}
@Override
Position deTranslate(int y, int x) {
return CLOCKWISE_90.translate(y, x);
}
};
abstract Position translate(int y, int x);
abstract Position deTranslate(int y, int x);
public static int toDeltaX(int x) {
return x - 7;
}
public static int toDeltaY(int y) {
return 7 - y;
}
public static int toOriginX(int dx) {
return dx + 7;
}
public static int toOriginY(int dy) {
return 7 - dy;
}
public Position originDeTranslateThenOrigin(Position p) {
Position res = deTranslate(toDeltaY(p.y), toDeltaX(p.x));
return new Position(toOriginY(res.y), toOriginX(res.x), p.winning);
}
public Position originTranslateThenOrigin(int y, int x) {
Position res = translate(toDeltaY(y), toDeltaX(x));
return new Position(toOriginY(res.y), toOriginX(res.x));
}
public Piece originTranslateThenOrigin(Piece p) {
int y = p.getY(), x = p.getX();
Position res = originTranslateThenOrigin(y, x);
return new Piece(res.x, res.y, p.getPlayer());
}
public String translateToString(int dy, int dx) {
Position pos = translate(dy, dx);
return toString(toOriginY(pos.y) , toOriginX(pos.x));
}
public static String toString(int y, int x) {
assert y >= 0 && y < 15;
assert x >= 0 && x < 15;
String ys = (y + 1) + "";
char xs = (char) ('a' + x);
return xs + ys;
}
public static PositionTranslator select(int dy, int dx) {
if (dx > 0 && dy <= 0) return CLOCKWISE_0;
else if (dx >= 0 && dy > 0) return CLOCKWISE_90;
else if (dx < 0 && dy >= 0) return CLOCKWISE_180;
else if (dx <= 0 && dy < 0) return CLOCKWISE_270;
return CLOCKWISE_0;
}
public static PositionTranslator selectByOrigin(int y, int x) {
return select(toDeltaY(y), toDeltaX(x));
}
}
下面我們可以在開局的時候避免大量的搜索。這里我們可以去查一些基本棋譜，找到比較好的開局下法。然后這需要用一個坐標(biāo)象限的枚舉，然后算法會根據(jù)旋轉(zhuǎn)，平移，翻轉(zhuǎn)等操作找到正確的落子位置。
這個時候我們必須要維護2套棋盤，一個是內(nèi)部計算用的棋盤，我們統(tǒng)一翻轉(zhuǎn)到右下角的象限。另一個是展現(xiàn)給用戶看的棋盤。是回歸到用戶下棋位置對應(yīng)的AI落子。
舉個例子，如果用戶開始下在，中心點的左上。我們會在實際棋盤里，下在右下，然后去查棋譜，應(yīng)該怎么下。如果查到應(yīng)該下在正下，在實際棋盤里下正下。但是我們呈現(xiàn)給用戶看的就是正上。
public class ChessboardByteArrayAlgoConsistent extends ChessboardByteArrayAlgo implements IConsistentAlgo {
@Getter
private PositionTranslator positionTranslator;
private Deque<Position> originAllSteps = new ArrayDeque<>();
public ChessboardByteArrayAlgoConsistent(int size) {
super(size);
}
@Override
public void setPiece(Piece piece) {
originAllSteps.offerLast(new Position(piece.getY(), piece.getX()));
if (allSteps.isEmpty()) {
if (piece.getY() != 7 || piece.getX() != 7) {
positionTranslator = PositionTranslator.selectByOrigin(piece.getY(), piece.getX());
} else {
super.setPiece(piece);
return;
}
}
if (positionTranslator == null && allSteps.size() == 1) {
positionTranslator = PositionTranslator.selectByOrigin(piece.getY(), piece.getX());
}
Piece np = positionTranslator.originTranslateThenOrigin(piece);
allSteps.offerLast(new Position(np.getY(), np.getX()));
location[getIdx(np.getY(),np.getX())] = (byte) piece.getPlayer().getId();
}
@Override
public boolean isTerminal(Piece piece) {
if (positionTranslator == null) return false;
Piece np = positionTranslator.originTranslateThenOrigin(piece);
return isTerminal(np.getX(), np.getY());
}
@Override
public boolean isLegalMove(Piece piece) {
if (positionTranslator == null) return true;
Piece np = positionTranslator.originTranslateThenOrigin(piece);
return isLegalMove(np.getX(), np.getY());
}
@Override
public ChessboardByteArrayAlgoConsistent clone() {
ChessboardByteArrayAlgoConsistent cloned = new ChessboardByteArrayAlgoConsistent(size);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
cloned.setPiece(j, i, getValInBoard(j, i));
}
}
cloned.allSteps = new ArrayDeque<>(allSteps);
cloned.originAllSteps = new ArrayDeque<>(originAllSteps);
cloned.positionTranslator = positionTranslator;
return cloned;
}
@Override
public String generateStepsCode() {
return BoardToString.serialize(originAllSteps);
}
}
同時我們寫一個算法，要求做到，只要滿足表里的棋子樣式（就是經(jīng)過平移，翻轉(zhuǎn)或旋轉(zhuǎn)都是一個圖案的情況下），找到對應(yīng)的落子。
舉個例子，比如表里的落子為：
1695821880828.png
當(dāng)用戶下成下圖，我們應(yīng)該可以查表找到對應(yīng)紅圈的位置
1695821942914.png
下面是算法實現(xiàn)
public class ConsistentPattern {
public static Position findBestMove(List<Position> shape, Map<String, Position> patchedKey) {
return findBestMoveInternal(shape.stream().map(i -> new int[]{i.x, i.y}).collect(Collectors.toList()), patchedKey);
}
private static Position findBestMoveInternal(List<int[]> shape, Map<String, Position> patchedKey) {
int[] blackXs = new int[(shape.size() + 1) >> 1];
int[] blackYs = new int[(shape.size() + 1) >> 1];
int[] whiteXs = new int[shape.size() >> 1];
int[] whiteYs = new int[shape.size() >> 1];
int[] blackOuts = new int[blackXs.length];
int[] whiteOuts = new int[whiteXs.length];
for (int rotateType = 0; rotateType < 8; ++rotateType) {
// 先旋轉(zhuǎn)
fulfillXYs(shape, rotateType, blackXs, blackYs, whiteXs, whiteYs);
// 再位移
int[] myx = fulfillOuts(blackXs, blackYs, whiteXs, whiteYs, blackOuts, whiteOuts);
String candidate = getString(blackOuts, whiteOuts);
if (!patchedKey.containsKey(candidate)) continue;
Position bestRawMovePos = patchedKey.get(candidate);
int[] bestRawMove = new int[]{bestRawMovePos.x, bestRawMovePos.y};
// 先位移
bestRawMove[0] += myx[0];
bestRawMove[1] += myx[1];
// 再旋轉(zhuǎn)
deRotate(rotateType, bestRawMove);
return new Position(bestRawMove[1], bestRawMove[0]);
}
return null;
}
private static void rotate(int rotateType, int[] bestRawMove) {
//x y, x -y, -x y, -x -y, y x, y -x, -y x, -y -x
int x = bestRawMove[0], y = bestRawMove[1];
int nx = rotateType <=1 ? x : rotateType <=3 ? -x : rotateType <=5 ? y : -y;
int ny = rotateType <=3 ? (rotateType %2==0 ? y : -y) : (rotateType %2==0 ? x : -x);
bestRawMove[0] = nx;
bestRawMove[1] = ny;
}
private static void deRotate(int rotateType, int[] bestRawMove) {
//after: x y, x -y, -x y, -x -y, y x, y -x, -y x, -y -x
//apply: x y, x -y, -x y, -x -y, y x, -y x, y -x, -y -x
//res : x y, x y, x y, x y, x y, x y, x y, x y
int x = bestRawMove[0], y = bestRawMove[1];
int nx = rotateType <=1 ? x : rotateType <=3 ? -x : rotateType %2 == 0 ? y : -y;
int ny = rotateType <=3 ? (rotateType %2==0 ? y : -y) : (rotateType <= 5 ? x : -x);
bestRawMove[0] = nx;
bestRawMove[1] = ny;
}
public static String canonical(List<Position> shape) {
return canonicalInternal(shape.stream().map(i -> new int[]{i.x, i.y}).collect(Collectors.toList()), new int[2]);
}
public static String canonical(List<Position> shape, int[] bestXandY) {
return canonicalInternal(shape.stream().map(i -> new int[]{i.x, i.y}).collect(Collectors.toList()), bestXandY);
}
private static String canonicalInternal(List<int[]> shape, int[] bestXandY) {
String ans = "";
int[] blackXs = new int[(shape.size() + 1) >> 1];
int[] blackYs = new int[(shape.size() + 1) >> 1];
int[] whiteXs = new int[shape.size() >> 1];
int[] whiteYs = new int[shape.size() >> 1];
int[] blackOuts = new int[blackXs.length];
int[] whiteOuts = new int[whiteXs.length];
int[] tmpBest = bestXandY.clone();
for (int rotateType = 0; rotateType < 8; ++rotateType) {
fulfillXYs(shape, rotateType, blackXs, blackYs, whiteXs, whiteYs);
int[] myx = fulfillOuts(blackXs, blackYs, whiteXs, whiteYs, blackOuts, whiteOuts);
String candidate = getString(blackOuts, whiteOuts);
if (ans.compareTo(candidate) < 0) {
ans = candidate;
int[] tmp = bestXandY.clone();
rotate(rotateType, tmp);
tmp[0] -= myx[0];
tmp[1] -= myx[1];
tmpBest = tmp;
}
}
bestXandY[0] = tmpBest[0];
bestXandY[1] = tmpBest[1];
return ans;
}
private static String getString(int[] blackOuts, int[] whiteOuts) {
String candidate = new StringBuilder(Arrays.toString(blackOuts)).append(":").append(Arrays.toString(whiteOuts)).toString() ;
return candidate;
}
private static int[] fulfillOuts(int[] blackXs, int[] blackYs, int[] whiteXs, int[] whiteYs, int[] blackOuts, int[] whiteOuts) {
int mx = blackXs[0], my = blackYs[0];
for (int x: blackXs) mx = Math.min(mx, x);
for (int x: whiteXs) mx = Math.min(mx, x);
for (int y: blackYs) my = Math.min(my, y);
for (int y: whiteYs) my = Math.min(my, y);
for (int j = 0; j < blackOuts.length; j++) {
blackOuts[j] = (blackYs[j] - my) * 15 + (blackXs[j] - mx);
}
for (int j = 0; j < whiteOuts.length; j++) {
whiteOuts[j] = (whiteYs[j] - my) * 15 + (whiteXs[j] - mx);
}
Arrays.sort(blackOuts);
Arrays.sort(whiteOuts);
return new int[]{mx, my};
}
private static void fulfillXYs(List<int[]> shape, int c, int[] blackXs, int[] blackYs, int[] whiteXs, int[] whiteYs) {
int t = 0;
for (int i = 0; i < shape.size(); i += 2) {
int[] z = shape.get(i);
int x = z[0], y = z[1];
//x y, x -y, -x y, -x -y, y x, y -x, -y x, -y -x
blackXs[t] = c <=1 ? x : c <=3 ? -x : c <=5 ? y : -y;
blackYs[t++] = c <=3 ? (c %2==0 ? y : -y) : (c %2==0 ? x : -x);
}
t = 0;
for (int i = 1; i < shape.size(); i += 2) {
int[] z = shape.get(i);
int x = z[0], y = z[1];
//x y, x -y, -x y, -x -y, y x, y -x, -y x, -y -x
whiteXs[t] = c <=1 ? x : c <=3 ? -x : c <=5 ? y : -y;
whiteYs[t++] = c <=3 ? (c %2==0 ? y : -y) : (c %2==0 ? x : -x);
}
}
}
有了這個我們可以快速的把一些開局棋譜，運用到各種維度上了。
Zobrist緩存
最后說一下緩存的優(yōu)化。棋盤類里有個非常有名的緩存叫zobrist
Zobrist緩存（Zobrist Hashing）是一種在計算機博弈和搜索算法中常用的技術(shù)，用于高效地存儲和檢索游戲局面的信息，以提高搜索算法的性能。它的名稱來自于其發(fā)明者Albert L. Zobrist，他是計算機博弈領(lǐng)域的先驅(qū)之一。
Zobrist緩存的主要思想是使用隨機生成的哈希鍵（稱為Zobrist鍵）來表示棋盤上每個局部位置的狀態(tài)。這個哈希鍵通常是一個固定位數(shù)的二進制數(shù)或整數(shù)，它可以唯一地標(biāo)識棋盤上的每種可能局面。Zobrist鍵的生成是隨機的，但在程序的每次運行中都是固定的，以確保相同的局面生成相同的鍵。
Zobrist緩存的工作流程如下：
初始化：在程序啟動時，為每個可能的棋盤局面生成隨機的Zobrist鍵，通常是一個固定位數(shù)的二進制數(shù)。這些鍵被存儲在一個稱為Zobrist表的數(shù)據(jù)結(jié)構(gòu)中。
計算局面哈希：對于給定的棋盤局面，通過將每個局部位置的Zobrist鍵按位異或（XOR）在一起來計算整個局面的哈希鍵。這個哈希鍵可以用來唯一地標(biāo)識該局面。
緩存和檢索：在搜索算法中，每次評估一個新的局面時，可以使用局面的哈希鍵來檢查Zobrist表，看是否已經(jīng)計算過這個局面的評估值。如果已經(jīng)計算過，就可以直接從緩存中獲取評估值，而不必重新計算。這大大提高了搜索算法的效率，特別是在深度搜索中。
更新緩存：如果在搜索過程中發(fā)現(xiàn)了一個新的局面，可以計算其評估值并將局面的哈希鍵與評估值存儲在Zobrist表中，以供后續(xù)檢索使用。
Zobrist緩存在博弈樹搜索算法（如博弈樹搜索、Alpha-Beta剪枝、Minimax等）中廣泛應(yīng)用，因為它能夠有效地減少了冗余計算，提高了搜索的速度。然而，需要注意的是，Zobrist緩存可能存在哈希沖突，即不同的局面生成相同的哈希鍵，因此需要一種方法來處理沖突，通常是通過使用開放尋址法或鏈表來解決。
下面是代碼實現(xiàn)：
public class Zobrist {
public static int DISABLE_CACHE_MASK = 100_000_000;
private final long[] zobristTable;
@Getter
private Map<Long, ResultAndDepth> transpositionTable;
@Getter
private long hash = 0;
@Getter
private int cacheMatch = 0;
private int size;
public Zobrist(IChessboardAIAlgo chessBoardAlgo) {
size = chessBoardAlgo.getSize();
zobristTable = new long[size * size * 2];
transpositionTable = new HashMap<>();
SecureRandom secureRandom = new SecureRandom();
for (int i = 0; i < zobristTable.length; i++) {
zobristTable[i] = secureRandom.nextLong();
}
calculateInitialHash(chessBoardAlgo);
}
public void updateHash(int y, int x, int role) {
if (role < 1 || role > 2) {
throw new IllegalArgumentException("Invalid move");
}
hash ^= zobristTable[(y * size + x) * 2 + (role - 1)];
}
private void calculateInitialHash(IChessboardAIAlgo chessBoardAlgo) {
for (int y = 0; y < size; y++) {
for (int x = 0; x < size; x++) {
int i = y * size + x;
int val = chessBoardAlgo.getValInBoard(x, y);
if (val != 0) {
hash ^= zobristTable[(i << 1) + (val - 1)];
}
}
}
}
public Optional<Integer> tryGet(int depth) {
if (!transpositionTable.containsKey(hash)) return Optional.empty();
ResultAndDepth scoreAndDepth = transpositionTable.get(hash);
if (scoreAndDepth.depth >= depth) {
cacheMatch++;
return Optional.of(scoreAndDepth.result);
}
return Optional.empty();
}
public int setAndReturnScore(int result, int depth) {
if (Math.abs(result) != DISABLE_CACHE_MASK)
transpositionTable.put(hash, new ResultAndDepth(result, depth));
return result;
}
private class ResultAndDepth {
int result;
int depth;
public ResultAndDepth(int result, int depth) {
this.result = result;
this.depth = depth;
}
}
}
優(yōu)化算殺深度
要做出五子棋強力AI，算殺模塊真的非常重要；如果他能在規(guī)定時間算出殺解，那么基本就很早可以勝券在握了。五子棋無禁手黑棋有著很大優(yōu)勢。所以我們要利用好查表和算殺，就可以基本做出一個黑棋先手必勝的AI了。
那么我們上一版設(shè)計的算殺AI會有2個缺陷，他可以算出殺解，但是我們指定深度，對手可以通過不斷沖四，去消耗掉我們的深度，最終會讓我們的算法無法判斷是否可以殺棋，而返回不能算殺的結(jié)論。
那么要優(yōu)化這一個缺陷的技術(shù)，叫單步拓展。也就是如果對手步數(shù)是沖四，我們就不消耗遞歸的層數(shù)。但是這樣就會造成時間上的極大退化。
原因是因為，假設(shè)對手有2步?jīng)_四，算殺過程中，這2步?jīng)_四，可以插進其他任意的算殺步子里。這樣排列組合的結(jié)果非常大。假設(shè)算殺需要15步棋，那么2個沖四，可以任意使用，大概會多17 * 18 的復(fù)雜度的提高。讓原來1秒的計算，變成5分鐘。當(dāng)然沖四更多，則計算讓費更大。
這時ZOBRIST緩存 就發(fā)揮了很好的效果。因為他只記錄棋盤狀態(tài)，不管你算殺是發(fā)生在哪一步，如果這個局面之前計算過，他就可以提早剪枝。
下面我們來看下帶ZOBRIST緩存的算殺代碼。
public class VCX extends RecursiveBaseAIAlgo implements IWinningAlgo {
private final int TIME_LIMIT_MS = 55_000;
private int nextPoint = -1;
private final long[] zobristTable;
private long hash = 0;
private long startTime = 0;
private Map<Long, Boolean> zobristCache;
private int firstDepth;
private int timeFactor;
private VCXCachedScoreManager vcxCachedScoreManager;
@Setter
private DebugContext debugContext = DebugContext.DISABLE;
public VCX(IChessboardAIAlgo chessBoardAlgo, int humanColor) {
this(chessBoardAlgo, humanColor, 23, VCXOptimization.FAST);
}
public VCX(IChessboardAIAlgo chessBoardAlgo, int humanColor, int firstDepth) {
this(chessBoardAlgo, humanColor, firstDepth, VCXOptimization.FAST);
}
public VCX(IChessboardAIAlgo chessBoardAlgo, int humanColor, int firstDepth, VCXOptimization killOptimization) {
super(chessBoardAlgo, new VCXCachedScoreManager(chessBoardAlgo, humanColor, killOptimization), humanColor);
this.vcxCachedScoreManager = (VCXCachedScoreManager) scoreManager;
this.firstDepth = firstDepth;
this.timeFactor = killOptimization.factor;
zobristTable = new long[size * size * 2];
SecureRandom secureRandom = new SecureRandom();
for (int i = 0; i < zobristTable.length; i++)
zobristTable[i] = secureRandom.nextLong();
}
@Override
public boolean isAbsoluteForcedWin() {
return true;
}
@Override
public Position aiFindPos() {
nextPoint = -1;
int oriFirstDepth = firstDepth;
startTime = System.currentTimeMillis();
// 迭代加深
for (int i = Math.max(oriFirstDepth - 16, 5); i <= oriFirstDepth; i += 4) {
firstDepth = i;
zobristCache = new HashMap<>();
if (aiWin(aiColor, i, -1)) break;
if ((System.currentTimeMillis() - startTime) * timeFactor > TIME_LIMIT_MS) break;
}
firstDepth = oriFirstDepth;
if (nextPoint == -1)
return Position.EMPTY;
return new Position(getY(nextPoint), getX(nextPoint), true);
}
// lastMaxPoint, 為了優(yōu)化性能, 方便剪枝
boolean aiWin(int role, int depth, int lastMaxPoint) {
// 因為會根據(jù)lastMaxPoint 進行進攻剪枝，所以CACHE里的輸不一定是輸
Boolean cached = zobristCache.get(hash);
if (cached != null) return cached;
if (depth <= 0) return setAndReturn(false);
List<Long> candidates = vcxCachedScoreManager.findAIKillSteps(lastMaxPoint);
if (!candidates.isEmpty() && score(candidates.get(0)) >= Score.FOUR.value) {
if (depth == firstDepth)
nextPoint = pos(candidates.get(0));
return setAndReturn(true);
}
if (candidates.isEmpty()) return setAndReturn(false);
debugContext.debugStartInfo(depth, firstDepth);
int maxPoint = -1;
for (long p : candidates) {
if (Thread.currentThread().isInterrupted()) return false;
if (System.currentTimeMillis() - startTime > TIME_LIMIT_MS) return false;
int pos = pos(p), score = score(p);
if (!debugContext.isInDebugStep(depth, firstDepth, pos)) continue;
int y = getY(pos), x = getX(pos);
addPiece(y, x, pos,true);
if (score > -Score.FIVE.value) {
maxPoint = pos;
}
boolean humanLose = humanLose(Player.enemyColor(role), depth - 1, maxPoint);
debugContext.debugResultInfo(depth, y, x, firstDepth, String.format("human lose: %s", humanLose));
removePiece(y, x, pos, true);
if (humanLose) {
if (depth == firstDepth)
nextPoint = pos;
return setAndReturn(true);
}
}
return setAndReturn(false);
}
private boolean humanLose(int role, int depth, int lastMaxPoint) {
Boolean cached = zobristCache.get(hash);
if (cached != null) return cached;
// 超過回合數(shù)，代表防守成功
if (depth <= 0) return setAndReturn(false);
List<Long> candidates = vcxCachedScoreManager.findHumanDefendSteps();
// 如果發(fā)現(xiàn)對面沒有進攻手段（活三，沖四，活四），則代表防守成功
if (candidates.isEmpty()) return setAndReturn(false);
// 如果對面能成五，發(fā)現(xiàn)自己有成五；
// 如果對面不能成五，發(fā)現(xiàn)自己有活四；
if (-1 * score(candidates.get(0)) >= Score.FOUR.value)
return setAndReturn(false);
debugContext.debugStartInfo(depth, firstDepth);
for (long p : candidates) {
int pos = pos(p);
if (!debugContext.isInDebugStep(depth, firstDepth, pos)) continue;
int y = getY(pos), x = getX(pos);
addPiece(y, x, pos, false);
boolean aiWin = aiWin(Player.enemyColor(role), depth - 1, lastMaxPoint);
debugContext.debugResultInfo(depth, y, x, firstDepth, String.format("ai Win:%s",aiWin));
removePiece(y, x, pos, false);
if (!aiWin) return setAndReturn(false);
}
return setAndReturn(true);
}
protected void addPiece(int y, int x, int nextStep, boolean isAI) {
int color = isAI ? aiColor : humanColor;
hash ^= zobristTable[(nextStep << 1) | (color - 1)];
super.addPiece(y, x, isAI);
}
protected void removePiece(int y, int x, int nextStep, boolean isAI) {
int color = isAI ? aiColor : humanColor;
hash ^= zobristTable[(nextStep << 1) | (color - 1)];
super.removePiece(y, x, isAI);
}
private boolean setAndReturn(boolean res) {
zobristCache.put(hash, res);
return res;
}
}
迭代加深
上面算殺過程中還運用了一個提速的技巧，如果我們7步可以算出殺解，要是一開始走錯了路子。他會搜的非常深，其實那個正確的路子只要7步。這時可以用迭代加深的搜索來解決這個問題。
迭代加深算法（Iterative Deepening Search，簡稱IDS）是一種用于解決搜索問題的深度優(yōu)先搜索（Depth-First Search，DFS）算法的改進版本。它的主要思想是通過不斷增加搜索深度來逐漸擴展搜索范圍，直到找到解決方案或達到最大搜索深度為止。IDS結(jié)合了DFS的簡單性和廣度優(yōu)先搜索（Breadth-First Search，BFS）的逐層擴展特性，因此通常用于在有限搜索空間中找到解決方案。
IDS的基本工作流程如下：
從初始節(jié)點開始，設(shè)置初始搜索深度為1。
使用深度優(yōu)先搜索（DFS）來探索搜索樹，但限制搜索深度不超過當(dāng)前設(shè)定的深度。
如果在當(dāng)前深度下找到了解決方案，就停止搜索并返回解決方案。
如果在當(dāng)前深度下沒有找到解決方案，增加搜索深度，并回到步驟2，繼續(xù)搜索。
重復(fù)步驟2到步驟4，直到找到解決方案或達到最大搜索深度為止。
IDS的優(yōu)點包括：
完備性：IDS保證會找到解決方案，如果解存在于搜索空間中。這是因為它逐漸增加搜索深度，最終會探索整個搜索樹。
空間效率：與BFS不同，IDS不需要在內(nèi)存中存儲整個搜索樹，只需要存儲當(dāng)前深度的節(jié)點，因此對內(nèi)存的要求較低。
可控制的搜索深度：IDS允許你在搜索過程中控制搜索的深度，這在處理搜索空間大小未知或不確定的情況下很有用。
然而，IDS的主要缺點是其多次重復(fù)搜索相同的節(jié)點，因為每次增加深度時都會重新搜索之前的部分。這可能會導(dǎo)致性能問題，特別是在搜索空間龐大的情況下。
但是這個額外性能開銷不算高。原因是因為對于許多狀態(tài)空間，大多數(shù)節(jié)點位于底層。所以上層的重復(fù)其實并不重要。經(jīng)過我自己測試，如果搜不到解，使用了迭代加深的時間開銷只多15%，但是在有解的情況下，他能極快的返回結(jié)果。
