Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Alpha beta pruning solution in Clear category for Haunted House by nickie
from math import hypot
moves = ["N", "W", "S", "E"]
def move(house, m, p):
# if the way is blocked, move fails
if m in house[p]: return None
# if we're at the exit, let's get out!
if m == "N" and p == 0: return -1
# if the move is within bounds, it succeeds
if m == "N" and p // 4 >= 1: return p-4
if m == "W" and p % 4 >= 1: return p-1
if m == "S" and p // 4 < 3: return p+4
if m == "E" and p % 4 < 3: return p+1
# otherwise it fails
return None
def solve(house, me, gh):
# minmax with visited states and alpha/beta pruning
seen = set()
solved = dict()
# my moves
def mine(p, depth, alpha, beta):
# if the ghost got us or we moved too far, we lost
if depth == 0 or p[0] == p[1]: return ("X", -1000)
# if not already solved, look for the best possible move
if not p in solved:
best = "X"
for m in moves:
moved = move(house, m, p[0])
if moved == None: continue
q = (moved, p[1])
if q in seen: continue
seen.add(q)
val = ghost(q, depth, alpha, beta)
if alpha < val:
alpha = val
best = m
if beta <= alpha: break
solved[p] = (best, alpha)
return solved[p]
# ghost's moves
def ghost(p, depth, alpha, beta):
# if we're out, we won
if p[0] < 0: return 1000
# otherwise, look for the ghost's best possible move
dist = 1000
best = []
for m in moves:
moved = move(house, m, p[1])
if moved == None: continue
q = (p[0], moved)
mx, my = divmod(q[0], 4)
gx, gy = divmod(q[1], 4)
d = hypot(abs(mx-gx), abs(my-gy))
if d < dist:
dist = d
best = [q]
elif d == dist:
best.append(q)
# careful, it may be more than one
for q in best:
m, val = mine(q, depth-1, alpha, beta)
beta = min(beta, val)
if beta <= alpha: break
return beta
# look for my best move
init = (me, gh)
m, val = mine(init, 30, -1000, 1000)
return solved
solved = None
def checkio(house, me, gh):
# zero based coordinates
me -= 1
gh -= 1
# if you haven't solved it yet, what do you wait?
global solved
if solved == None:
solved = solve(house, me, gh)
# look up the answer
m, val = solved[(me, gh)]
return m
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
checkio(
["", "S", "S", "",
"E", "NW", "NS", "",
"E", "WS", "NS", "",
"", "N", "N", ""],
16, 1)
checkio(
["", "", "", "",
"E", "ESW", "ESW", "W",
"E", "ENW", "ENW", "W",
"", "", "", ""],
11, 6)
Nov. 6, 2013
Comments:
