Erstelle Puyopuyo AI mit Python
Ich habe Puyopuyo AI mit Python gemacht, also werde ich es als Artikel schreiben. Ich werde es anhand der Grundlagen erklären, damit auch diejenigen, die nicht damit vertraut sind, es sich leicht vorstellen können. Wenn Sie es also bereits kennen, überspringen Sie es bitte.
Algorithmus
Zuerst liest der Computer vor und entscheidet, wo er als nächstes abgelegt werden soll, z. B. "Als nächstes, als nächstes ...". Je tiefer dieser Ausblick ist, desto besser, aber da jetzt nur drei Hände zu sehen sind, Puyo, NEXT Puyo und NEXTNEXT Puyo, werden wir weiter erforschen und gleichzeitig den unsichtbaren zukünftigen Tsumo ergänzen. Ich werde. Dieses Mal versuche ich bis zu 10 Schergen zu suchen. Es gibt 22 Muster für das Setzen von Puyo, und wenn Sie an 10 Schergen denken, können Sie nur 22 ^ 10 Muster setzen. Die Berechnung dauert sehr lange, daher verwenden wir die Strahlensuche, um eine weitere Suche nach schlecht bewerteten Händen zu vermeiden. Diesmal wurde die Strahlbreite auf 50 eingestellt. Informationen zur Bewertungsfunktion (der Standard, nach dem der Computer die Güte der Hand bewertet) finden Sie in diesem Artikel und lesen Sie "Wenn zwei Puyo jeder Farbe in jeder Spalte abgelegt werden." Maximale Anzahl von Ketten, die auftreten x 10 + 1. Spalte, 6. Spaltenhöhe x 2 + 2. Spalte, 5. Spaltenhöhe + Gesamtzahl der Verbindungen jedes Puyo ^ 2 ".
Code
Wenn Sie den Code ausführen, werden nach 30 Minuten ein GIF für die Zusammenstellung und ein Image der Karte erstellt. (Bitte legen Sie das Bild von Puyo im Voraus in den Ordner img) copy.deepcopy ist langsam, daher habe ich das cPickle-Modul verwendet, um es zu beschleunigen. Das ist ziemlich schnell. Wenn Sie dies mit copy.deepcopy tun, dauert es ungefähr 2 Stunden, um 15 Hände zusammenzubauen. Ich hatte auch das Gefühl, dass die Notation der Listeneinbeziehung schneller wurde.
puyoAI.py
import pprint
import random
import _pickle as cPickle
import time
from PIL import Image
#Zählen Sie die Höhe von x Spalten
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 = []
#Den ganzen Weg, um Puyo im Liegen zu setzen
for x in range(6):
if x+1 < 6:
#Wenn die 14. Stufe nicht gefüllt ist
if search_height(field,x) < 14 and search_height(field,x+1) < 14:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#Mit den Spezifikationen von Puyo Puyo verschwindet die 14. Stufe Puyo
if search_height(field,x)+1 != 14:
copy_field[-(search_height(field,x)+1)][x] = next[0]
#Mit den Spezifikationen von Puyo Puyo verschwindet die 14. Stufe Puyo
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)
#Wenn beide Puyo der gleichen Farbe sind, gibt es eine Möglichkeit, das Feld nach dem Platzieren abzudecken. Schneiden Sie es also ab
if next[0] != next[1]:
for x in range(6):
if x+1 < 6:
#Wenn die 14. Stufe nicht gefüllt ist
if search_height(field,x) < 14 and search_height(field,x+1) < 14:
copy_field = cPickle.loads(cPickle.dumps(field, -1))
#Mit den Spezifikationen von Puyo Puyo verschwindet die 14. Stufe Puyo
if search_height(field,x)+1 != 14:
copy_field[-(search_height(field,x)+1)][x] = next[1]
#Mit den Spezifikationen von Puyo Puyo verschwindet die 14. Stufe Puyo
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)
#Den ganzen Weg, um Puyo vertikal zu setzen
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]
#Mit den Spezifikationen von Puyo Puyo verschwindet die 14. Stufe Puyo
if search_height(field,x)+2 != 14:
copy_field[-(search_height(field,x)+2)][x] = next[1]
all_possible_moves.append(copy_field)
#Wenn beide Puyo der gleichen Farbe sind, gibt es eine Möglichkeit, das Feld nach dem Platzieren abzudecken. Schneiden Sie es also ab
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]
#Mit den Spezifikationen von Puyo Puyo verschwindet die 14. Stufe Puyo
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
#Die 14. Zeile ist leer
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, bei dem 4 oder mehr verbunden sind
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
#Beenden Sie das Programm, wenn keine Flags vorhanden sind
flag_count = 0
for y in copy_field:
flag_count += y.count(1)
if flag_count == 0:
return copy_field,chain_count
#Lass den schwimmenden Puyo fallen
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
#Maximale Anzahl von Ketten, wenn zwei Puyo jeder Farbe in jede Reihe fallen gelassen werden
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("Aktuelle Suchtiefe:{}".format(depth))
if depth > 10:
return depth0s
evaluation_results = []
for depth0 in depth0s:
for depth1 in possible_moves(depth0[1],next):
#Puyo verschwindet Nicht platzieren,Nicht in die 12. Reihe der 3. Reihe stellen
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 verschwindet Nicht platzieren,Nicht in die 12. Reihe der 3. Reihe stellen
if chain(depth1,0)[1] == 0 and depth1[2][2] == 0:
for depth2 in possible_moves(depth1,next[1]):
#Puyo verschwindet Nicht platzieren,Nicht in die 12. Reihe der 3. Reihe stellen
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)])
#Nehmen Sie die Hand mit dem höchsten Gesamtbewertungswert an
#dic = {Feld:Bewertungswert}
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:
#Machen Sie das Feld zu einer Zeichenfolge und zum Schlüssel des Wörterbuchs
#Geben Sie den Anfangswert ein(0)
dic["".join([str(x) for y in i[0] for x in y])] = 0
for i in beam_search_result:
#Bewertungswert zum Feld hinzufügen
dic["".join([str(x) for y in i[0] for x in y])] += i[2]
#Das Feld mit der höchsten Gesamtbewertung(String)
final_choice = sorted(dic.items(), key=lambda x:x[1], reverse=True)[0][0]
#Konvertieren Sie von einer Zeichenfolge in ein zweidimensionales Array und kehren Sie zurück
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("Verarbeitungszeit:{}Sekunden".format(time.time()-start))
if __name__ == "__main__":
initial_field = [[0]*6 for i in range(14)]
main()
Ergebnis
Ergebnisse der 30-Runden-Simulation
Montagezustand
Aussehen verschwindet (** 10 Kette **)
Schlechter Platz
・ Es ist sehr langsam, über einen Zug nachzudenken ・ Die Montage von 30 Händen dauert ca. 30 Minuten
Abhilfe
・ Machen wir es in einer schnelleren Sprache wie c ++ ・ Verwenden wir ein Bitboard ・ Hash die Karte, um zu vermeiden, dass dieselbe Karte mehrmals ausgewertet werden muss.
Recommended Posts