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
| 92 def alphaBetaWithMemory(node, alpha, beta, depth, printDepth):
93 indent=printDepth-depth
94 indentString=" "*indent
95 #print indentString,"in ABwM(node=%d, alpha=%d, beta=%d, depth=%d)"%(node,alpha,beta,depth)
96 transTableInfo=transTable.lookup(node, depth)
97
98 if transTableInfo:
99 #print indentString,"got transTableInfo: [%d, %d] depth: %d"%(transTableInfo.lowerBound,
100 # transTableInfo.upperBound,
101 # transTableInfo.furthestDepthSearched)
102 if transTableInfo.lowerBound >= beta:
103 return transTableInfo.lowerBound
104 if transTableInfo.upperBound <= alpha:
105 return transTableInfo.upperBound
106 alpha = max(alpha, transTableInfo.lowerBound)
107 beta = min(beta, transTableInfo.upperBound)
108
109 terminal=isTerminal(node)
110 if depth==0 or terminal:
111 g=evaluate(node, AIPLAYER)
112 #print indentString,"evaluating [%d] got %d"%(node,g)
113 elif isMaximizing(node):
114 g = NEGINFINITY
115 a = alpha
116 for c in getChildren(node):
117 if g >= beta:
118 break
119 g=max(g,alphaBetaWithMemory(c, a, beta, depth-1, printDepth))
120 a=max(a,g)
121 else:
122 g = POSINFINITY
123 b = beta
124 for c in getChildren(node):
125 if g <= alpha:
126 break
127 g = min(g,alphaBetaWithMemory(c, alpha, b, depth-1, printDepth))
128 b = min(b,g)
129
130 if g <= alpha:
131 transTable.storeUpperBound(node,g)
132 elif g > alpha and g < beta:
133 transTable.storeLowerBound(node,g)
134 transTable.storeUpperBound(node,g)
135 raise "never happens"
136 else:
137 transTable.storeLowerBound(node,g)
138 transTable.storeDepth(node, depth)
139 transTable.setTerminal(node, terminal)
140 return g |
Partager