Créez Puyopuyo AI avec Python
J'ai créé Puyopuyo AI avec Python, je vais donc l'écrire sous forme d'article. Je vais vous expliquer à partir des bases afin que même ceux qui ne le connaissent pas puissent facilement l'imaginer, donc si vous le connaissez déjà, veuillez l'ignorer.
algorithme
Tout d'abord, l'ordinateur pré-lit et décide où le mettre ensuite, par exemple "mettez-le ensuite, mettez-le ensuite ...". Bien sûr, plus cette perspective est profonde, mieux c'est, mais comme il n'y a que trois mains visibles, Puyo, NEXT Puyo et NEXTNEXT Puyo, nous continuerons d'explorer tout en complétant le futur invisible Tsumo. Je vais. Cette fois, j'essaye de rechercher jusqu'à 10 sbires. Il y a 22 modèles pour mettre Puyo, et si vous pensez à 10 serviteurs, tous les modèles que vous pouvez mettre sont 22 ^ 10. Cela prend beaucoup de temps pour calculer cela, nous utilisons donc la recherche par faisceau pour éviter de rechercher davantage de mains mal notées. Cette fois, la largeur du faisceau a été fixée à 50. Pour la fonction d'évaluation (la norme par laquelle l'ordinateur évalue la bonté de la main), reportez-vous à cet article et lisez «Quand deux Puyo de chaque couleur sont déposés dans chaque colonne. Nombre maximum de chaînes qui se produisent x 10 + 1ème colonne, 6ème hauteur de colonne x 2 + 2ème colonne, 5ème hauteur de colonne + nombre total de connexions de chaque Puyo ^ 2 ".
code
Lorsque vous exécutez le code, un GIF montrant comment il est assemblé et une image du tableau après 30 minutes sont créés. (Veuillez mettre l'image de Puyo dans le dossier img à l'avance) copy.deepcopy est lent, j'ai donc utilisé le module cPickle pour l'accélérer. C'est assez rapide. Si vous le faites avec copy.deepcopy, il faut environ 2 heures pour assembler 15 mains. J'ai également estimé que la notation d'inclusion de liste devenait plus rapide.
puyoAI.py
import pprint
import random
import _pickle as cPickle
import time
from PIL import Image
#Comptez la hauteur de x colonnes
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 = []
#Tout le chemin pour mettre Puyo en position couchée
for x in range(6):
if x+1 < 6:
#Lorsque la 14e étape n'est pas remplie
if search_height(field,x) < 14 and search_height(field,x+1) < 14:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#Avec les spécifications de Puyo Puyo, la 14ème étape Puyo disparaît
if search_height(field,x)+1 != 14:
copy_field[-(search_height(field,x)+1)][x] = next[0]
#Avec les spécifications de Puyo Puyo, la 14ème étape Puyo disparaît
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)
#Lorsque les deux sont des Puyo de la même couleur, il existe un moyen de couvrir le champ après l'avoir placé, alors coupez-le
if next[0] != next[1]:
for x in range(6):
if x+1 < 6:
#Lorsque la 14e étape n'est pas remplie
if search_height(field,x) < 14 and search_height(field,x+1) < 14:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#Avec les spécifications de Puyo Puyo, la 14ème étape Puyo disparaît
if search_height(field,x)+1 != 14:
copy_field[-(search_height(field,x)+1)][x] = next[1]
#Avec les spécifications de Puyo Puyo, la 14ème étape Puyo disparaît
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)
#Tout le chemin pour mettre Puyo verticalement
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]
#Avec les spécifications de Puyo Puyo, la 14ème étape Puyo disparaît
if search_height(field,x)+2 != 14:
copy_field[-(search_height(field,x)+2)][x] = next[1]
all_possible_moves.append(copy_field)
#Lorsque les deux sont des Puyo de la même couleur, il existe un moyen de couvrir le champ après l'avoir placé, alors coupez-le
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]
#Avec les spécifications de Puyo Puyo, la 14ème étape Puyo disparaît
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
#La 14e ligne est vide
else:
field[y][x] = 0
y -= 1
return field
def chain(field,chain_count):
global n
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#Marquer où 4 ou plus sont connectés
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
#Quitter s'il n'y a pas de drapeaux
flag_count = 0
for y in copy_field:
flag_count += y.count(1)
if flag_count == 0:
return copy_field,chain_count
#Lâchez le Puyo flottant
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
#Nombre maximum de chaînes lorsque deux Puyo de chaque couleur sont déposés dans chaque rangée
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("Profondeur de recherche actuelle:{}".format(depth))
if depth > 10:
return depth0s
evaluation_results = []
for depth0 in depth0s:
for depth1 in possible_moves(depth0[1],next):
#Puyo disparaît Ne placez pas,Ne pas placer dans la 12e rangée de la 3e rangée
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 disparaît Ne placez pas,Ne pas placer dans la 12e rangée de la 3e rangée
if chain(depth1,0)[1] == 0 and depth1[2][2] == 0:
for depth2 in possible_moves(depth1,next[1]):
#Puyo disparaît Ne placez pas,Ne pas placer dans la 12e rangée de la 3e rangée
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)])
#Adoptez la main avec la valeur d'évaluation totale la plus élevée
#dic = {champ:Valeur d'évaluation}
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:
#Faire du champ une chaîne et en faire la clé du dictionnaire
#Entrez la valeur initiale(0)
dic["".join([str(x) for y in i[0] for x in y])] = 0
for i in beam_search_result:
#Ajouter une valeur d'évaluation au champ
dic["".join([str(x) for y in i[0] for x in y])] += i[2]
#Le champ avec la note totale la plus élevée(Chaîne)
final_choice = sorted(dic.items(), key=lambda x:x[1], reverse=True)[0][0]
#Conversion d'une chaîne de caractères en tableau bidimensionnel et retour
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("temps de traitement:{}Secondes".format(time.time()-start))
if __name__ == "__main__":
initial_field = [[0]*6 for i in range(14)]
main()
résultat
30 résultats de simulation de virage
État de montage
Apparence disparaissant (** 10 chaînes **)
Mauvais endroit
・ Il est très lent de penser à un mouvement ・ Il faut environ 30 minutes pour assembler 30 mains
Remède
・ Faisons-le dans un langage plus rapide tel que c ++ ・ Utilisons un tableau de bits ・ Hash le tableau pour éliminer le besoin d'évaluer le même tableau plusieurs fois.
Recommended Posts