Spaces:
Sleeping
Sleeping
File size: 4,948 Bytes
7d23b62 |
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 |
from .cache import Cache
from .eval import FIVE
# Checked
MAX = 1000000000
cache_hits = {
"search": 0,
"total": 0,
"hit": 0
}
onlyThreeThreshold = 6
cache = Cache()
def factory(onlyThree=False, onlyFour=False):
def helper(board, role, depth, cDepth=0, path=(), alpha=-MAX, beta=MAX):
cache_hits["search"] += 1
if cDepth >= depth or board.isGameOver():
return [board.evaluate(role), None, (path)]
hash = board.hash()
prev = cache.get(hash)
if prev and prev["role"] == role:
if (
(abs(prev["value"]) >= FIVE or prev["depth"] >= depth - cDepth)
and prev["onlyThree"] == onlyThree
and prev["onlyFour"] == onlyFour
):
cache_hits["hit"] += 1
return [prev["value"], prev["move"], path + prev["path"]]
value = -MAX
move = None
bestPath = path # Copy the current path
bestDepth = 0
# points = board.getValuableMoves(role, cDepth, onlyThree or cDepth > onlyThreeThreshold, onlyFour)
points = board.getValuableMoves(role, cDepth, onlyThree or cDepth > onlyThreeThreshold, onlyFour)
if cDepth == 0:
print('points:', points)
if not len(points):
return [board.evaluate(role), None, path]
for d in range(cDepth + 1, depth + 1):
# 迭代加深过程中只找己方能赢的解，因此只搜索偶数层即可
if d % 2 != 0:
continue
breakAll = False
for point in points:
board.put(point[0], point[1], role)
newPath = tuple(list(path) + [point]) # Add current move to path
currentValue, currentMove, currentPath = helper(board, -role, d, cDepth + 1, tuple(newPath) , -beta, -alpha)
currentValue = -currentValue
board.undo()
## 迭代加深的过程中，除了能赢的棋，其他都不要
## 原因是：除了必胜的，其他评估不准。比如必输的棋，由于走的步数偏少，也会变成没有输，比如5
### 步之后输了，但是1步肯定不会输，这时候1步的分数是不准确的，显然不能选择。
if currentValue >= FIVE or d == depth:
# 必输的棋，也要挣扎一下，选择最长的路径
if (
currentValue > value
or (currentValue <= -FIVE and value <= -FIVE and len(currentPath) > bestDepth)
):
value = currentValue
move = point
bestPath = currentPath
bestDepth = len(currentPath)
alpha = max(alpha, value)
if alpha >= FIVE:
breakAll = True
break
if alpha >= beta:
break
if breakAll:
break
if (cDepth < onlyThreeThreshold or onlyThree or onlyFour) and (not prev or prev["depth"] < depth - cDepth):
cache_hits["total"] += 1
cache.put(hash, {
"depth": depth - cDepth,
"value": value,
"move": move,
"role": role,
"path": bestPath[cDepth:],
"onlyThree": onlyThree,
"onlyFour": onlyFour,
})
return [value, move, bestPath]
return helper
_minmax = factory()
vct = factory(True)
vcf = factory(False, True)
def minmax(board, role, depth=4, enableVCT=False):
if enableVCT:
vctDepth = depth + 8
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)
value2, move2, bestPath2 = vct(board.reverse(), role, vctDepth)
board.undo()
if value < FIVE and value2 == FIVE and len(bestPath2) > len(bestPath):
value3, move3, bestPath3 = vct(board.reverse(), role, vctDepth)
if len(bestPath2) <= len(bestPath3):
return [value, move2, bestPath2] # value2 是被挡住的，所以这里还是用value
return [value, move, bestPath]
else:
return _minmax(board, role, depth) |