Make Puyo Puyo AI with Python
I made Puyo Puyo AI with Python, so I will write it as an article. I will explain from the basics so that even those who are not familiar with it can easily imagine it, so if you already know it, please skip over.
algorithm
First, the computer pre-reads and decides where to put it next, such as "put it next, put it next ...". Of course, the deeper this look-ahead is, the better, but since there are only three hands that can be seen now, Puyo, NEXT Puyo, and NEXT NEXT Puyo, we will search while complementing the invisible future Tsumo. I will. This time, I try to search up to 10 minions. There are 22 patterns of actions to put Puyo, and if you think about 10 minions, all the patterns you can put are 22 ^ 10. It takes a very long time to calculate this, so we use beam search to avoid further searching for poorly rated hands. This time, the beam width was set to 50. For the evaluation function (the standard by which the computer evaluates the goodness of the hand), refer to this article and read "When two Puyo of each color are dropped in each column. Maximum number of chains that occur x 10 + 1th column, 6th column height x 2 + 2nd column, 5th column height + total number of connections of each Puyo ^ 2 ".
code
When you execute the code, a GIF that looks like it is assembled and an image of the board after 30 minutes are created. (Please put the image of Puyo in the img folder in advance) copy.deepcopy is slow, so I used the cPickle module to speed it up. This is pretty fast. If you do it with copy.deepcopy, it will take about 2 hours to assemble 15 hands. I also felt that the list comprehension was faster.
puyoAI.py
import pprint
import random
import _pickle as cPickle
import time
from PIL import Image
#Count the height of x columns
def search_height(field,x):
return len([y[x] for y in field if y[x] != 0])
def next_create():
color_type = ["G","Y","B","R"]
return [random.choice(color_type) for i in range(2)]
def possible_moves(field,next):
all_possible_moves = []
#All the way to put Puyo when lying down
for x in range(6):
if x+1 < 6:
#When the 14th stage is not filled
if search_height(field,x) < 14 and search_height(field,x+1) < 14:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#With the specifications of Puyo Puyo, the 14th stage Puyo disappears
if search_height(field,x)+1 != 14:
copy_field[-(search_height(field,x)+1)][x] = next[0]
#With the specifications of Puyo Puyo, the 14th stage Puyo disappears
if search_height(field,x+1)+1 != 14:
copy_field[-(search_height(field,x+1)+1)][x+1] = next[1]
all_possible_moves.append(copy_field)
#When both are the same color Puyo, there is a way to cover the field after placing it, so cut it
if next[0] != next[1]:
for x in range(6):
if x+1 < 6:
#When the 14th stage is not filled
if search_height(field,x) < 14 and search_height(field,x+1) < 14:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#With the specifications of Puyo Puyo, the 14th stage Puyo disappears
if search_height(field,x)+1 != 14:
copy_field[-(search_height(field,x)+1)][x] = next[1]
#With the specifications of Puyo Puyo, the 14th stage Puyo disappears
if search_height(field,x+1)+1 != 14:
copy_field[-(search_height(field,x+1)+1)][x+1] = next[0]
all_possible_moves.append(copy_field)
#All the way to put Puyo vertically
for x in range(6):
if search_height(field,x) <= 12:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
copy_field[-(search_height(field,x)+1)][x] = next[0]
#With the specifications of Puyo Puyo, the 14th stage Puyo disappears
if search_height(field,x)+2 != 14:
copy_field[-(search_height(field,x)+2)][x] = next[1]
all_possible_moves.append(copy_field)
#When both are the same color Puyo, there is a way to cover the field after placing it, so cut it
if next[0] != next[1]:
for x in range(6):
if search_height(field,x) <= 12:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
copy_field[-(search_height(field,x)+1)][x] = next[1]
#With the specifications of Puyo Puyo, the 14th stage Puyo disappears
if search_height(field,x)+2 != 14:
copy_field[-(search_height(field,x)+2)][x] = next[0]
all_possible_moves.append(copy_field)
return all_possible_moves
def count(field,y,x):
global n
c = field[y][x]
field[y][x] = 1
n +=1
if x+1 < 6 and field[y][x+1] == c and c != 1:
count(field,y,x+1)
if y+1 < 14 and field[y+1][x] == c and c != 1:
count(field,y+1,x)
if x-1 >= 0 and field[y][x-1] == c and c != 1:
count(field,y,x-1)
if y-1 >= 0 and field[y-1][x] == c and c != 1:
count(field,y-1,x)
return n
def drop(field,y,x):
while y >= 0:
if y > 0:
field[y][x] = field[y-1][x]
y -= 1
#The 14th row is blank
else:
field[y][x] = 0
y -= 1
return field
def chain(field,chain_count):
global n
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#Flag where 4 or more are connected
for y in range(14):
for x in range(6):
n = 0
if field[y][x] != 0 and count(cPickle.loads(cPickle.dumps(field, -1)),y,x) >= 4:
copy_field[y][x] = 1
#Exit if there are no flags
flag_count = 0
for y in copy_field:
flag_count += y.count(1)
if flag_count == 0:
return copy_field,chain_count
#Drop the floating Puyo
for y in range(14):
for x in range(6):
if copy_field[y][x] == 1:
drop(copy_field,y,x)
chain_count +=1
return chain(copy_field,chain_count)
def height_evaluation(field):
point = 0
for x in range(6):
if x == 0 or x == 5:
point += len([y[x] for y in field if y[x] != 0])*2
if x == 1 or x == 4:
point += len([y[x] for y in field if y[x] != 0])
return point
#Maximum number of chains when two Puyo of each color are dropped in each row
def feature_chain_evaluation(field):
chain_counts = []
color_type = ["G","Y","B","R"]
for x in range(6):
for color in color_type:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
if [y[x] for y in field].count(0) > 2:
copy_field[-(search_height(copy_field,x)+1)][x] = color
copy_field[-(search_height(copy_field,x)+2)][x] = color
chain_counts.append(chain(copy_field,0)[1])
else:
chain_counts.append(0)
return max(chain_counts)
def count_evaluation(field):
global n
point = 0
for y in range(14):
for x in range(6):
if field[y][x] != 0:
n = 0
point += count(cPickle.loads(cPickle.dumps(field, -1)),y,x)**2
return point
def beam_search(depth0s,next,depth):
print("Current search depth:{}".format(depth))
if depth > 10:
return depth0s
evaluation_results = []
for depth0 in depth0s:
for depth1 in possible_moves(depth0[1],next):
#Puyo disappears Do not place,Do not place in the 12th row of the 3rd row
if chain(depth1,0)[1] == 0 and depth1[2][2] == 0:
evaluation_results.append([depth0[0],depth1,feature_chain_evaluation(depth1)*10 + height_evaluation(depth1) + count_evaluation(depth1)])
return beam_search(sorted(evaluation_results, key=lambda x:x[2], reverse=True)[:50],next_create(),depth+1)
def next_move(field,next):
evaluation_results = []
for depth1 in possible_moves(field,next[0]):
#Puyo disappears Do not place,Do not place in the 12th row of the 3rd row
if chain(depth1,0)[1] == 0 and depth1[2][2] == 0:
for depth2 in possible_moves(depth1,next[1]):
#Puyo disappears Do not place,Do not place in the 12th row of the 3rd row
if chain(depth2,0)[1] == 0 and depth2[2][2] == 0:
evaluation_results.append([depth1,depth2,feature_chain_evaluation(depth2)*10 + height_evaluation(depth2) + count_evaluation(depth2)])
#Adopt the hand with the highest total evaluation value
#dic = {field:Evaluation value}
dic = {}
beam_search_result = beam_search(sorted(evaluation_results, key=lambda x:x[2], reverse=True)[:50],next[2],3)
for i in beam_search_result:
#Make the field a string and make it the key of the dictionary
#Enter the initial value(0)
dic["".join([str(x) for y in i[0] for x in y])] = 0
for i in beam_search_result:
#Add evaluation value to field
dic["".join([str(x) for y in i[0] for x in y])] += i[2]
#The field with the highest total evaluation value(String)
final_choice = sorted(dic.items(), key=lambda x:x[1], reverse=True)[0][0]
#Convert from a character string to a two-dimensional array and return
return [[n if n != "0" else 0 for n in final_choice[i:i+6]] for i in range(0,len(final_choice),6)]
def field_to_img(field):
green = Image.open("img/green.png ")
yellow = Image.open("img/yellow.png ")
blue = Image.open("img/blue.png ")
red = Image.open("img/red.png ")
blank = Image.open("img/blank.png ")
imgs = [green,yellow,blue,red,blank]
color_type = ["G","Y","B","R",0]
field_img = Image.new("RGB", (green.width*6, green.height*14))
start_y = 0
for y in field:
field_x_img = Image.new("RGB", (green.width*6, green.height))
start_x = 0
for x in y:
for img,color in zip(imgs,color_type):
if x == color:
field_x_img.paste(img, (start_x, 0))
start_x += img.width
field_img.paste(field_x_img, (0, start_y))
start_y += field_x_img.height
return field_img
def main():
start = time.time()
imgs = []
field = initial_field
next = [next_create(),next_create(),next_create()]
for i in range(30):
field = next_move(field,next)
pprint.pprint(field)
imgs.append(field_to_img(field))
next.pop(0)
next.append(next_create())
imgs[0].save("result.gif",save_all=True, append_images=imgs[1:], optimize=False, duration=500, loop=0)
imgs[-1].save("result.png ")
print("processing time:{}Seconds".format(time.time()-start))
if __name__ == "__main__":
initial_field = [[0]*6 for i in range(14)]
main()
result
30th turn simulation result
State of assembling
Appearance disappearing (** 10 chain **)
Bad place
・ It's very slow to think about one move ・ It takes about 30 minutes to assemble 30 hands
Remedy
・ Let's do it in a faster language such as c ++ ・ Let's use a bitboard ・ Hash the board to eliminate the need to evaluate the same board multiple times.
Recommended Posts