File size: 5,065 Bytes
079c32c |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
import Cache from "./cache";
import { FIVE, FOUR } from "./eval";
const MAX = 1000000000;
// 缓存内容：depth, value, move
export const cache_hits = {
search: 0,
total: 0,
hit: 0
};
const onlyThreeThreshold = 6;
const cache = new Cache(); // 放在这里，则minmax, vct和vcf会共用同一个缓存
const factory = (onlyThree = false, onlyFour = false) => {
// depth 表示总深度，cDepth表示当前搜索深度
const helper = (board, role, depth, cDepth = 0, path = [], alpha = -MAX, beta = MAX) => {
cache_hits.search++;
if (cDepth >= depth || board.isGameOver()) {
return [board.evaluate(role), null, [...path]];
}
const hash = board.hash();
const prev = cache.get(hash);
if (prev && prev.role === role) {
if ((Math.abs(prev.value) >= FIVE || prev.depth >= depth - cDepth) && prev.onlyThree === onlyThree && prev.onlyFour === onlyFour) // 不能连五的，则minmax 和 vct vcf 的缓存不能通用
{
cache_hits.hit++;
return [prev.value, prev.move, [...path, ...prev.path]];
}
}
let value = -MAX;
let move = null;
let bestPath = [...path]; // Copy the current path
let bestDepth = 0;
let points = board.getValuableMoves(role, cDepth, onlyThree || cDepth > onlyThreeThreshold, onlyFour);
if (cDepth === 0) {
console.log('points:', points);
}
// board.display(points);
if (!points.length) {
// points = board.getValidMoves(role);
return [board.evaluate(role), null, [...path]];
}
for (let d = cDepth + 1; d <= depth; d += 1) {
// 迭代加深过程中只找己方能赢的解，因此只搜索偶数层即可
if (d % 2 !== 0) continue;
let breakAll = false;
for (let i = 0; i < points.length; i++) {
const point = points[i];
board.put(point[0], point[1], role);
let newPath = [...path, point]; // Add current move to path
let [currentValue, currentMove, currentPath] = helper(board, -role, d, cDepth + 1, newPath, -beta, -alpha);
currentValue = -currentValue;
board.undo();
// 迭代加深的过程中，除了能赢的棋，其他都不要
// 原因是：除了必胜的，其他评估不准。比如必输的棋，由于走的步数偏少，也会变成没有输，比如 5步之后输了，但是1步肯定不会输，这时候1步的分数是不准确的，显然不能选择。
if (currentValue >= FIVE || d === depth) {
// 必输的棋，也要挣扎一下，选择最长的路径
if ((currentValue > value) ||
(currentValue <= -FIVE && value <= -FIVE && currentPath.length > bestDepth)) {
value = currentValue;
move = point;
bestPath = currentPath;
bestDepth = currentPath.length;
}
}
alpha = Math.max(alpha, value);
if (alpha >= FIVE) { // 自己赢了也结束，但是对方赢了还是要继续搜索的
breakAll = true;
break;
}
if (alpha >= beta) {
break;
}
}
if (breakAll) {
break;
}
}
// 缓存
if ((cDepth < onlyThreeThreshold || onlyThree || onlyFour) && (!prev || prev.depth < depth - cDepth)) {
cache_hits.total += 1;
cache.put(hash, {
depth: depth - cDepth, // 剩余搜索深度
value,
move,
role,
path: bestPath.slice(cDepth), // 剩余搜索路径
onlyThree,
onlyFour,
});
}
const res = [value, move, bestPath];
return res;
}
return helper;
}
const _minmax = factory();
export const vct = factory(true);
export const vcf = factory(false, true);
export const minmax = (board, role, depth = 4, enableVCT = true) => {
if (enableVCT) {
const vctDepth = depth + 8;
// 先看自己有没有杀棋
let [value, move, bestPath] = vct(board, role, vctDepth);
if (value >= FIVE) {
return [value, move, bestPath];
}
[value, move, bestPath] = _minmax(board, role, depth);
// 假设对方有杀棋，先按自己的思路走，走完之后看对方是不是还有杀棋
// 如果对方没有了，那么就说明走的是对的
// 如果对方还是有，那么要对比对方的杀棋路径和自己没有走棋时的长短
// 如果走了棋之后路径变长了，说明走的是对的
// 如果走了棋之后，对方杀棋路径长度没变，甚至更短，说明走错了，此时就优先封堵对方
board.put(move[0], move[1], role);
let [value2, move2, bestPath2] = vct(board.reverse(), role, vctDepth)
board.undo();
if (value < FIVE && value2 === FIVE && bestPath2.length > bestPath.length) {
let [value3, move3, bestPath3] = vct(board.reverse(), role, vctDepth)
if (bestPath2.length <= bestPath3.length) {
return [value, move2, bestPath2]; // value2 是被挡住的，所以这里还是用value
}
}
return [value, move, bestPath];
} else {
return _minmax(board, role, depth);
}
}
|