水玉潰しゲームソルバーに挑戦

水玉潰しを解くスクリプトを書こうと思い立ちました。が、やたらと時間がかかります。かたっぱしから手を生成して、それをシミュレートするという力技なので、時間がかかるのは当然です。ラスト何か数手であっても数分かかったりします。何かヒューリスティックを考えないといけませんね。

def main():
pattern = [[0,4,4,0,0,0],
[0,0,0,0,0,0],
[2,0,0,0,0,0],
[3,0,0,0,0,0],
[3,0,0,0,0,0],
[0,0,0,0,0,0]]
solution, tank = solve(pattern, 13,13)
print solution, tank

def play(game, sequence=[]):

for x,y in sequence:

game.dropByUser(x,y)

def solve(pattern, tank=10, limit=2):

tankMax = -1

solution = None

game = Game()

for currentLimit in xrange(1, limit+1):

print currentLimit

# for each sequence:

for seq in sequences(currentLimit):

# heuristics

if unsolvable(pattern, seq):

continue

# play game

game.init(pattern, tank)

play(game, seq)

# if solved and tank is larger than prev best, 

# store tank and solution

if game.isSolved() and game.tank > tankMax:

solution = seq

tankMax = game.tank

if solution:

return solution, tankMax

return solution, tankMax

def sequences(limit):

if limit==0:

yield []

return

for x in xrange(6):

for y in xrange(6):

for tmp in sequences(limit-1):

yield [(x,y)] + tmp

return

_tmp_pattern = [[0 for x in range(6)] for y in range(6)]

def unsolvable(pattern, seq):

for y in xrange(6):

for  x in xrange(6):

_tmp_pattern[y][x] = pattern[y][x]

for x,y in seq:

_tmp_pattern[y][x] += 1

if max([max(z) for z in _tmp_pattern]) < 5:

return True

else:

return False



class Game:

def __init__(self):

self.tank = 0

self.cells = {}

for y in xrange(6):

for x in xrange(6):

self.cells[x,y] = Cell(self)

self.splashes = []

self.chain = 0

    def init(self, pattern, tank=10):

for y in xrange(6):

for x in xrange(6):

self.cells[x,y].drop = pattern[y][x]

self.tank = tank

    def dropByUser(self, x, y):

self.chain = 0

return self.drop(x, y)

    def drop(self, x, y):

self.tank -= 1

self.cells[x,y].growDrop()

while len(self.splashes) > 0:

s = self.splashes.pop(0)

s.move()

if s.alive:

self.splashes.append(s)

    def notifyCrash(self, cell):

self.chain += 1

if self.chain == 3:

self.tank += 1

self.chain = 0

for (x,y),value in self.cells.items():

if value==cell:

break

for dx,dy in [(1,0), (-1,0), (0,1), (0,-1)]:

self.splashes.append(Splash(self, x,y,dx,dy))

    def isSolved(self):

for c in self.cells.values():

if c.drop!=0:

return False

return True

    def __str__(self):

string = "tank: %d＼n" % self.tank

for y in xrange(6):

for x in xrange(6):

string += "%d " % self.cells[x,y].drop

string += "＼n"

return string

class Cell:

def __init__(self, game):

self.game = game

self.drop = 0

    def growDrop(self):

self.drop += 1

if self.drop==5:

self.drop = 0

self.game.notifyCrash(self)

class Splash:

def __init__(self, game, x, y, dx, dy):

self.x = x

self.y = y

self.dx = dx

self.dy = dy

self.game = game

self.alive = True

    def move(self):

self.x += self.dx

self.y += self.dy

if (self.x<0 or 5
self.alive = False

elif self.game.cells[self.x, self.y].drop > 0:

self.game.cells[self.x, self.y].growDrop()

self.alive = False



if __name__ == "__main__":

main()