這是好多年前做過(guò)的一個(gè)東西，現(xiàn)在用優(yōu)化算法來(lái)實(shí)現(xiàn)一下。
一． 目標(biāo)描述
俄羅斯方塊大家應(yīng)該都玩過(guò)。
這里的目標(biāo)是設(shè)計(jì)一個(gè)模型讓電腦計(jì)算判斷一個(gè)方塊到哪個(gè)位置最好，讓電腦自己控制方塊的平移旋轉(zhuǎn)，并使游戲能夠長(zhǎng)時(shí)間運(yùn)行下去。
二． 模型設(shè)計(jì)
1.俄羅斯方塊類型
俄羅斯方塊的所有類型如下圖：
一共7種類型，19個(gè)不同的放置類型。
2.方塊掉落位置判斷
俄羅斯方塊的地圖，我copy了一個(gè)寬10，高20的。
在此地圖下，由于計(jì)算量不大，我們可以遍歷每一個(gè)塊下落后的位置來(lái)判斷是否要在該處下落。
如上圖，對(duì)于一個(gè)確定的放置類型，我們可以從左到右依次遍歷其下落后的位置，上圖中，該方塊一共有9個(gè)不同位置，加上旋轉(zhuǎn)，一共有（9+8）*2 = 34種不同情況。
上圖顯示了位置1,4,9的最終下落后的情況，作為人類可以明確知道位置9要優(yōu)于位置1,4，現(xiàn)在要如何將這一信息傳達(dá)給電腦，讓電腦也將方塊落在位置9呢？
3.方塊位置優(yōu)劣判斷模型
Tips:這個(gè)是我自己的模型，僅供參考。
判斷優(yōu)劣有幾個(gè)指標(biāo)
1. 整體的高度height
2. 各列高度差之和height_diff_sum
3. 空格的數(shù)量 space_num
4. 各行缺少方塊數(shù)
5. 消除行數(shù)
在上圖中，沒(méi)有完整行需要消除，整體的高度為4,（第4列最高），空格數(shù)為3（第2,8,10列）各一個(gè)。
高度差為右側(cè)與左側(cè)之差，分別為0,1,1,4,2,1,0,0,0,1，總共為10。
各方缺少方塊數(shù)為第一行缺4塊，第二行缺1塊，第三行卻5塊，第四行缺9塊。為了方便計(jì)算我將其分為了兩類：1：只缺一塊的行；2：缺多塊的行。
上面的方塊可記為：
- 最大高度height = 4
- 高度差height_diff_sum = 10
- 空格數(shù)space_num = 3
- 缺一塊行數(shù)space_1_row = 1
- 缺大于一塊行數(shù)space_2_row = 3
- 完成行數(shù)complete = 0
接下來(lái)就可以使用這些數(shù)據(jù)來(lái)計(jì)算該方塊的得分了。
Score = w1* height+
w2*height_diff_sum+
w3*space_num+
w4*space_1_row+
w5*space_2_row+
w6*complete
對(duì)于每一個(gè)下落的方塊，將其旋轉(zhuǎn)平移然后下落，然后計(jì)算整體方塊的得分，選取整體得分最少的位置落下該方塊，然后循環(huán)往復(fù)。
三． 優(yōu)化算法結(jié)合
有了上面的模型，就可以明確優(yōu)化算法所要優(yōu)化的參數(shù)即：w1-w6這6個(gè)參數(shù)。
那么構(gòu)建的適應(yīng)度函數(shù)的輸入則是一個(gè)6維的向量。然而輸出是什么呢？輸出當(dāng)然是從游戲開(kāi)始到目前為止所消除的總行數(shù)。
現(xiàn)在問(wèn)題來(lái)了，對(duì)于每一次游戲，出現(xiàn)的方塊是隨機(jī)的，這就意味著，該適應(yīng)度函數(shù)，即使確定了輸入，也無(wú)法得到固定的輸出。
不過(guò)這也不是大問(wèn)題，雖然是隨機(jī)，但肯定有一定的概率分布，我們可以每次讓電腦進(jìn)行多次游戲，然后取平均值，來(lái)減弱隨機(jī)的干擾。我更過(guò)分一點(diǎn)，將多次游戲的最低得分作為適應(yīng)度函數(shù)的輸出。
那么優(yōu)化算法的適應(yīng)度函數(shù)計(jì)算過(guò)程如下圖：
由于每計(jì)算一次適應(yīng)度函數(shù)，都要進(jìn)行數(shù)局游戲，隨著參數(shù)越來(lái)越優(yōu)，游戲得分越來(lái)越高，每局游戲的時(shí)間也會(huì)越來(lái)越長(zhǎng)。這會(huì)導(dǎo)致在算法前期，每一次迭代的運(yùn)行速度很快，但是隨著參數(shù)的優(yōu)化，每次迭代所需的時(shí)間會(huì)越來(lái)越長(zhǎng)。我們最終的目標(biāo)是游戲能夠無(wú)限玩下去，那么優(yōu)化算法的運(yùn)行時(shí)間也會(huì)接近無(wú)限長(zhǎng)。
為了縮短算法的運(yùn)行時(shí)間，我給模型添加了一點(diǎn)限制，減少游戲整體的高度。正常游戲?yàn)閷?0，高20；優(yōu)化的時(shí)候，使用寬10高10來(lái)進(jìn)行計(jì)算。這樣能夠縮短優(yōu)化算法的運(yùn)行時(shí)間，雖然對(duì)結(jié)果會(huì)有些許影響，但應(yīng)該問(wèn)題不大。
四． 代碼實(shí)現(xiàn)
實(shí)現(xiàn)算法之前要先有一個(gè)俄羅斯方塊游戲，在網(wǎng)上copy了一個(gè)，改造了一下。這次的代碼將使用python實(shí)現(xiàn)。所需要的庫(kù)pygame和其他的計(jì)算庫(kù)請(qǐng)自行搜索安裝。
1. 正常的俄羅斯方塊游戲
import random
import sys
import pygame
class GameTetris:
block_I = [[0, -2], [0, -1], [0, 0], [0, 1]] # 0
block_I_1 = [[-2, 0], [-1, 0], [0, 0], [1, 0]] # 1
block_O = [[0, 0], [0, 1], [1, 1], [1, 0]] # 2
block_S = [[0, -1], [0, 0], [-1, 0], [-1, 1]] # 3
block_S_1 = [[-1, -1], [0, -1], [0, 0], [1, 0]] # 4
block_Z = [[0, 1], [0, 0], [-1, 0], [-1, -1]] # 5
block_Z_1 = [[-1, 1], [0, 1], [0, 0], [1, 0]] # 6
block_T = [[0, 0], [0, 1], [1, 0], [-1, 0]] # 7
block_T_1 = [[0, 0], [0, 1], [1, 0], [0, -1]] # 8
block_T_2 = [[0, 0], [1, 0], [0, -1], [-1, 0]] # 9
block_T_3 = [[0, 0], [0, 1], [-1, 0], [0, -1]] # 10
block_J = [[0, 0], [1, 0], [-1, 0], [1, -1]] # 11
block_J_1 = [[0, 0], [0, -1], [0, 1], [1, 1]] # 12
block_J_2 = [[0, 0], [1, 0], [-1, 0], [-1, 1]] # 13
block_J_3 = [[0, 0], [0, 1], [0, -1], [-1, -1]] # 14
block_L = [[0, 0], [1, 0], [-1, 0], [1, 1]] # 15
block_L_1 = [[0, 0], [0, -1], [0, 1], [-1, 1]] # 16
block_L_2 = [[0, 0], [1, 0], [-1, 0], [-1, -1]] # 17
block_L_3 = [[0, 0], [0, 1], [0, -1], [1, -1]] # 18
all_block = [block_I, block_I_1,
block_O,
block_S, block_S_1,
block_Z, block_Z_1,
block_T, block_T_1, block_T_2, block_T_3,
block_J, block_J_1, block_J_2, block_J_3,
block_L, block_L_1, block_L_2, block_L_3
]
# 旋轉(zhuǎn)用
rotate_cur_id = [1, 2, 4, 6, 10, 14, 18]
# 如果是上面的id則旋轉(zhuǎn)后為下面的id,否則直接+1
rotate_next_id = [0, 1, 3, 5, 7, 11, 15]
# 方塊邊長(zhǎng)
block_size = 25
# 窗口尺寸
window_with = 16
window_hight = 20
# 地圖尺寸
map_height = 21
map_width = 10
gameover = False
pause = False
press = False
times = 0
score = 0
# 方塊地圖
map_block = None
# 當(dāng)前方塊id
cur_id = 0
# 下一個(gè)方塊的id
next_id = 0
cur_block = None
next_block = None
# 方塊的初始位置
block_initial_position = None
screen = None
# 初始化數(shù)據(jù)
def init_data(self):
self.gameover = False
self.pause = False
self.press = False
self.times = 0
self.score = 0
# 當(dāng)前方塊id
self.cur_id = 0
# 下一個(gè)方塊的id
self.next_id = 0
# 方塊的初始位置
self.block_initial_position = [self.map_height - 2, int(self.map_width / 2)]
# 新建空白方塊地圖
self.map_block = [[0 for column in range(0, self.map_width)] for row in range(0, self.map_height)]
# 初始化當(dāng)前方塊和下一個(gè)方塊
self.next_id = random.randint(0, 18)
self.next_block = self.all_block[self.next_id].copy()
self.cur_id = random.randint(0, 18)
self.cur_block = self.all_block[self.cur_id].copy()
# 下落、位置、數(shù)組檢測(cè)、得分、屏幕信息
def block_move_down(self):
y_drop = self.block_initial_position[0]
x_move = self.block_initial_position[1]
y_drop -= 1
for row, column in self.cur_block:
row += y_drop
column += x_move
# 如果要下降的位置已有方塊，則跳出
if row < 0:
break
if self.map_block[row][column] == 1:
break
else:
# 如果要下降的位置沒(méi)有方塊則移動(dòng)到該位置
self.block_initial_position.clear()
self.block_initial_position.extend([y_drop, x_move])
# 沒(méi)有到底
return False
return True
# 計(jì)算有沒(méi)有完成的行
def check_complete(self):
y_drop, x_move = self.block_initial_position
# 將當(dāng)前塊的位置加入地圖
for row, column in self.cur_block:
self.map_block[y_drop + row][x_move + column] = 1
complete_row = []
# 計(jì)算地圖中是否有完成的行
for row in range(0, self.map_height - 1):
if 0 not in self.map_block[row]:
complete_row.append(row)
complete_row.sort(reverse=True)
# 將完成的行消除
for row in complete_row:
self.map_block.pop(row)
self.map_block.append([0 for column in range(0, self.map_width)])
# 計(jì)算得分
self.score += len(complete_row)
# 將下一塊復(fù)制到當(dāng)前塊
self.cur_id = self.next_id
self.cur_block = self.all_block[self.cur_id].copy()
# 隨機(jī)生成新的下一塊
self.next_id = random.randint(0, 18)
self.next_block = self.all_block[self.next_id].copy()
# 將新的方塊的起始位置還原到中上
self.block_initial_position.clear()
self.block_initial_position.extend([self.map_height - 2, int(self.map_width / 2)])
y_drop, x_move = self.block_initial_position
for row, column in self.cur_block:
row += y_drop
column += x_move
if self.map_block[row][column]:
self.gameover = True
# 不再繼續(xù)下落
return False
# 方塊的移動(dòng)，防止出界，碰撞
def move_left_right(self, n):
y_drop, x_move = self.block_initial_position
x_move += n
for row, column in self.cur_block:
row += y_drop
column += x_move
if column < 0 or column > self.map_width - 1 or self.map_block[row][column]:
break
else:
self.block_initial_position.clear()
self.block_initial_position.extend([y_drop, x_move])
# 旋轉(zhuǎn),位置都進(jìn)行變化
def rotate(self,):
if self.cur_id not in self.rotate_cur_id:
self.cur_id = self.cur_id + 1
else:
for i in range(0, len(self.rotate_cur_id)):
if self.cur_id == self.rotate_cur_id[i]:
self.cur_id = self.rotate_next_id[i]
break
rotating_position = self.all_block[self.cur_id].copy()
y_drop, x_move = self.block_initial_position
for row, column in rotating_position:
row += y_drop
column += x_move
if column < 0 or column > self.map_width - 1 or self.map_block[row][column]:
break
else:
self.cur_block.clear()
self.cur_block.extend(rotating_position)
def draw_grid(self):
color = (200, 200, 200)
# 繪制網(wǎng)格
# 縱向
for i in range(0, self.map_width + 1):
pygame.draw.line(self.screen, color, (i * self.block_size, 0),
(i * self.block_size, self.window_hight * self.block_size), 1)
# 橫向
for i in range(0, self.map_height + 1):
pygame.draw.line(self.screen, color, (0, i * self.block_size),
(self.map_width * self.block_size, i * self.block_size), 1)
# 左右分隔線
pygame.draw.line(self.screen, (0, 0, 0), (self.map_width * self.block_size, 0),
(self.map_width * self.block_size, self.window_hight * self.block_size), 2)
# 繪制右邊下一塊的網(wǎng)格
for i in range(1, 6):
pygame.draw.line(self.screen, color, ((self.map_width + i) * self.block_size, (1) * self.block_size),
((self.map_width + i) * self.block_size, (5) * self.block_size), 1)
for i in range(1, 6):
pygame.draw.line(self.screen, color, ((self.map_width + 1) * self.block_size, i * self.block_size),
((self.map_width + 5) * self.block_size, i * self.block_size), 1)
# 方塊設(shè)置、變化、背景改變
def update_screen(self):
# 繪制當(dāng)前塊
y_drop, x_move = self.block_initial_position
for row, column in self.cur_block:
row = row + y_drop
column += x_move
pygame.draw.rect(self.screen, (255, 165, 0), (
column * self.block_size + 1, (self.map_height - row - 2) * self.block_size + 1, self.block_size - 1,
self.block_size - 1))
# 繪制下一塊
for row, column in self.next_block:
pygame.draw.rect(self.screen, (255, 165, 0), (
(self.map_width + column + 3) * self.block_size + 1, (2-row) * self.block_size + 1, self.block_size - 1,
self.block_size - 1))
# 如果方塊掉落到底則改變顏色
for row in range(0, self.map_height - 1):
for column in range(0, self.map_width):
bottom_block = self.map_block[row][column]
if bottom_block:
pygame.draw.rect(self.screen, (0, 0, 255), (
column * self.block_size + 1, (self.map_height - row - 2) * self.block_size + 1,
self.block_size - 1, self.block_size - 1))
def run(self):
self.init_data()
pygame.init()
self.screen = pygame.display.set_mode((self.window_with * self.block_size, self.window_hight * self.block_size))
pygame.display.set_caption("俄羅斯方塊")
while True:
self.screen.fill((255, 255, 255))
self.draw_grid()
pygame.display.set_caption(str(self.score) + '分')
if self.pause:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_SPACE:
self.pause = (~self.pause)
if not self.pause:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_LEFT:
self.move_left_right(-1)
elif event.type == pygame.KEYDOWN and event.key == pygame.K_RIGHT:
self.move_left_right(1)
elif event.type == pygame.KEYDOWN and event.key == pygame.K_UP:
self.rotate()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_DOWN:
self.press = True
elif event.type == pygame.KEYUP and event.key == pygame.K_DOWN:
self.press = False
elif event.type == pygame.KEYDOWN and event.key == pygame.K_SPACE:
self.pause = (~self.pause)
if self.press:
self.times += 10
if self.times >= 50:
is_bottom = self.block_move_down()
if is_bottom:
self.check_complete()
self.times = 0
else:
self.times += 1
if self.gameover:
sys.exit()
self.update_screen()
pygame.time.Clock().tick(200)
pygame.display.flip()
if __name__ == '__main__':
game = GameTetris()
game.run()
這是一個(gè)正常的俄羅斯方塊，運(yùn)行后效果如下：
2. 差分進(jìn)化算法python實(shí)現(xiàn)
實(shí)現(xiàn)基本與matlab版本結(jié)構(gòu)一致：
| 文件名 | 文件描述 |
|---|---|
| Unit.py | 個(gè)體基類 |
| Algorithm_Impl.py | 算法基類 |
| DE_Unit.py | 差分進(jìn)化算法個(gè)體 |
| DE_Base.py | 差分進(jìn)化算法基礎(chǔ)實(shí)現(xiàn) |
| DE_Impl.py | 差分進(jìn)化算法實(shí)現(xiàn) |
# 個(gè)體基類
class Unit:
dim = 0
position = None
value = 0
def __init__(self, dim):
self.dim = dim
self.position = [0]*dim
# 優(yōu)化算法基類
import sys
import numpy as np
class Algorithm_Impl:
# 當(dāng)前最優(yōu)位置
position_best = None
# 當(dāng)前最優(yōu)適應(yīng)度
value_best = - sys.float_info.max
# 歷史最優(yōu)適應(yīng)度
value_best_history = list()
# 是否為求最大值, 默認(rèn)為是
is_cal_max = True
# 適應(yīng)度函數(shù)，需要單獨(dú)傳入
fitfunction = None
# 調(diào)用適應(yīng)度函數(shù)次數(shù)
cal_fit_num = 0
# 維度
dim = 1
# 種群中個(gè)體的數(shù)量
size = 1
# 最大迭代次數(shù)
iter_max = 1
# 解空間下界
range_min_list = list()
# 解空間上界
range_max_list = list()
# 種群列表
unit_list = list()
# 構(gòu)造函數(shù)
def __init__(self, dim, size, iter_max, range_min_list, range_max_list):
self.size = size
self.dim = dim
self.iter_max = iter_max
self.range_min_list = range_min_list
self.range_max_list = range_max_list
# 默認(rèn)為求最大值
self.is_cal_max = True
# 初始化算法中的個(gè)體
def init_unit(self):
self.position_best = np.zeros((1, self.dim))[0]
self.value_best_history = []
# 設(shè)置初始最優(yōu)值，由于是求最大值，所以設(shè)置了最大浮點(diǎn)數(shù)的負(fù)值
self.value_best = - sys.float_info.max
self.unit_list.clear()
# for s in range(self.size):
# unit = Unit(self.dim)
# unit.position = np.random.rand((1, self.dim)).dot(
# self.range_max_list - self.range_min_list) + self.range_min_list
# unit.value = self.fitfunction(params=unit.position)
# self.unit_list.append(unit)
# 計(jì)算適應(yīng)度函數(shù)
def cal_fitfunction(self, position=None):
if position is None:
return 0
if self.fitfunction is None:
return 0
return self.fitfunction(params=position)
# 設(shè)置適應(yīng)度函數(shù)
def set_fitfunction(self, fit_function):
self.fitfunction = fit_function
# 運(yùn)行入口
def run(self):
self.init_unit()
self.iteration()
return
# 循環(huán)迭代
def iteration(self):
for i in range(self.iter_max):
self.update(i)
return
# 更新一次迭代
def update(self, iter):
# 記錄最優(yōu)值
for i in range(self.size):
if self.unit_list[i].value > self.value_best:
self.value_best = self.unit_list[i].value
self.position_best = self.unit_list[i].position
print('第', iter, '代')
if self.is_cal_max:
self.value_best_history.append(self.value_best)
print('最優(yōu)值=', self.value_best)
else:
self.value_best_history.append(-self.value_best)
print('最優(yōu)值=', -self.value_best)
print('最優(yōu)解=', self.position_best.tolist())
return
# 某一維度越界值處理
def get_out_bound_value_one(self, d, value):
if value > self.range_max_list[d]:
value = self.range_max_list[d]
if value < self.range_min_list[d]:
value = self.range_min_list[d]
return value
# 全部值越界處理
def get_out_bound_value(self, value):
for d in range(self.dim):
if value[d] > self.range_max_list[d]:
value[d] = self.range_max_list[d]
if value[d] < self.range_min_list[d]:
value[d] = self.range_min_list[d]
return value
# 差分進(jìn)化算法個(gè)體
from optimization_algorithm.frame.Unit import Unit
class DE_Unit(Unit):
# 個(gè)體的新位置(變異位置)
position_new = None
def __init__(self, dim):
super().__init__(dim)
# 差分進(jìn)化算法
import copy
import random
import numpy as np
from optimization_algorithm.algorithm_differential_evolution.DE_Unit import DE_Unit
from optimization_algorithm.frame.Algorithm_Impl import Algorithm_Impl
class DE_Base(Algorithm_Impl):
# 交叉概率
cross_rate = 0.3
# 變異概率
alter_factor = 0.5
# 初始化算法中的個(gè)體
def init_unit(self):
super().init_unit()
for s in range(self.size):
unit = DE_Unit(self.dim)
unit.position = np.random.rand(1, self.dim)[0]*(
self.range_max_list - self.range_min_list) + self.range_min_list
unit.value = self.fitfunction(params=unit.position)
self.unit_list.append(unit)
# 更新
def update(self, i):
super(DE_Base, self).update(i)
self.altered()
self.cross()
self.choose()
# 變異
def altered(self):
for s in range(self.size):
# 生成3個(gè)不重復(fù)的隨機(jī)數(shù)
randList = random.sample(range(0, self.size), 3)
new_position = self.unit_list[randList[0]].position + self.alter_factor * (
self.unit_list[randList[1]].position - self.unit_list[randList[2]].position)
new_position = self.get_out_bound_value(new_position)
self.unit_list[s].position_new = copy.deepcopy(new_position)
# 交叉
def cross(self):
for s in range(self.size):
rnbr = random.randint(0, self.dim)
for d in range(self.dim):
rnd = random.uniform(0.0, 1.0)
if rnd > self.cross_rate and rnbr != d:
self.unit_list[s].position_new[d] = self.unit_list[s].position[d]
self.unit_list[s].position_new = self.get_out_bound_value(self.unit_list[s].position_new)
# 選擇
def choose(self):
for s in range(self.size):
new_value = self.cal_fitfunction(self.unit_list[s].position_new)
if new_value > self.unit_list[s].value:
self.unit_list[s].position = copy.deepcopy(self.unit_list[s].position_new)
self.unit_list[s].value = new_value
if new_value > self.value_best:
self.position_best = copy.deepcopy(self.unit_list[s].position)
self.value_best = new_value
# 差分進(jìn)化算法實(shí)現(xiàn)
from optimization_algorithm.algorithm_differential_evolution.DE_Base import DE_Base
class DE_Impl(DE_Base):
def __init__(self, dim, size, iter_max, range_min_list, range_max_list):
super().__init__(dim, size, iter_max, range_min_list, range_max_list)
# 測(cè)試腳本
import numpy as np
from optimization_algorithm.algorithm_differential_evolution.DE_Base import DE_Base
if __name__ == '__main__':
def fit_function(**kwargs):
params = kwargs['params']
if params is None:
params = []
result = 0
for d in range(len(params)):
result += params[d] * params[d]
return -result
## 算法實(shí)例
# 維度
dim = 30
# 種群數(shù)量
size = 60
# 最大迭代次數(shù)
iter_max = 1000
# 取值范圍上界
range_max_list = np.ones((1, dim))[0] * 100
# 取值范圍下界
range_min_list = np.ones((1, dim))[0] * -100
# 實(shí)例化差分進(jìn)化算法類
base = DE_Base(dim, size, iter_max, range_min_list, range_max_list)
base.is_cal_max = False
# 確定適應(yīng)度函數(shù)
base.fitfunction = fit_function
# 運(yùn)行
base.run()
print(base.value_best)
print(base.position_best)
3. 使用優(yōu)化算法進(jìn)行優(yōu)化
4. 自動(dòng)化俄羅斯方塊
這兩個(gè)部分放在一起，因?yàn)?中的結(jié)果將成為4中的輸入，可以分布進(jìn)行，也可以順序進(jìn)行
import sys
import pygame
from game.tetris.GameTetris import GameTetris
from optimization_algorithm.algorithm_differential_evolution.DE_Base import DE_Base
import numpy as np
class GameTetrisAuto(GameTetris):
rotate_num = 0
x_offset = 0
y_offset = 0
weight_params = []
top = GameTetris.map_height - 2
score_min = 99999
# 檢查是否有整行，是否結(jié)束游戲
def check_complete(self):
GameTetris.check_complete(self)
if 1 in self.map_block[self.top]:
self.gameover = True
self.rotate_num, self.x_offset = self.get_x_rotate_num(self.map_block, self.cur_id)
def run_auto(self):
self.init_data()
pygame.init()
self.screen = pygame.display.set_mode((self.window_with * self.block_size, self.window_hight * self.block_size))
pygame.display.set_caption("俄羅斯方塊")
self.rotate_num, self.x_offset = self.get_x_rotate_num(self.map_block, self.cur_id)
while True:
self.screen.fill((255, 255, 255))
self.draw_grid()
pygame.display.set_caption(str(self.score) + '分')
if self.gameover:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_SPACE:
self.pause = (~self.pause)
else:
if self.pause:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_SPACE:
self.pause = (~self.pause)
if not self.pause:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_LEFT:
self.move_left_right(-1)
elif event.type == pygame.KEYDOWN and event.key == pygame.K_RIGHT:
self.move_left_right(1)
elif event.type == pygame.KEYDOWN and event.key == pygame.K_UP:
self.rotate()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_DOWN:
self.press = True
elif event.type == pygame.KEYUP and event.key == pygame.K_DOWN:
self.press = False
elif event.type == pygame.KEYDOWN and event.key == pygame.K_SPACE:
self.pause = (~self.pause)
if self.rotate_num > 0:
# 旋轉(zhuǎn)一次
self.rotate()
self.rotate_num = self.rotate_num - 1
if self.x_offset > 0:
# 右移一次
self.x_offset = self.x_offset - 1
self.move_left_right(1)
if self.x_offset < 0:
# 左移一次
self.x_offset = self.x_offset + 1
self.move_left_right(-1)
is_bottom = self.block_move_down()
if is_bottom:
self.check_complete()
if self.gameover:
# 游戲結(jié)束后不退出
# sys.exit()
continue
self.update_screen()
pygame.time.Clock().tick(200)
pygame.display.flip()
# 計(jì)算當(dāng)前地圖和當(dāng)前方塊能得到的最優(yōu)地圖
def get_x_rotate_num(self, map_block, cur_id):
# 獲取當(dāng)前方塊的id及其旋轉(zhuǎn)后可能的形狀
temp_id = cur_id
id_list = list()
id_list.append(temp_id)
for i in range(0, 4):
if temp_id not in self.rotate_cur_id:
temp_id = temp_id + 1
else:
for j in range(0, len(self.rotate_cur_id)):
if temp_id == self.rotate_cur_id[j]:
temp_id = self.rotate_next_id[j]
break
if temp_id == cur_id:
break
id_list.append(temp_id)
value_min = 1000
res_id = 0
x_move = 0
# 遍歷該方塊的旋轉(zhuǎn)后的方塊
for i in id_list:
cur_block = self.all_block[i]
value, x_offset = self.get_block_down_map(map_block, cur_block)
if value < value_min:
value_min = value
res_id = i
x_move = x_offset
rotate_num = 0
# 計(jì)算需要旋轉(zhuǎn)多少次
for i in id_list:
if i == res_id:
break
else:
rotate_num = rotate_num + 1
return rotate_num, x_move
# 根據(jù)當(dāng)前地圖和當(dāng)前方塊，計(jì)算掉落后的值
def get_block_down_map(self, map_block, cur_block):
init_position = [self.map_height - 2, int(self.map_width / 2)]
y_pos, x_pos = init_position
value_min = 9999999
x_offset = 0
# 遍歷每一個(gè)寬度
for i in range(int(-self.map_width / 2), int(self.map_width / 2)):
# 判斷x坐標(biāo)上是否超出邊界
is_out_width = False
for row, column in cur_block:
x = column + (x_pos + i)
if x < 0 or x > self.map_width - 1:
is_out_width = True
break
if is_out_width:
# 超出邊界則跳過(guò)
continue
x_move, y_move = 0, 0
# 復(fù)制當(dāng)前地圖
temp_map_block = [[x for x in y] for y in map_block]
# 遍歷每一個(gè)高度
is_bottom = False
for j in range(1, self.map_height):
for row, column in cur_block:
x_move = x_pos + i
y_move = y_pos - j
x = column + x_move
y = row + y_move
# 如果要下降的位置已有方塊，則跳出
if y < 0:
is_bottom = True
break
if temp_map_block[y][x] == 1:
is_bottom = True
break
if is_bottom:
y_move = y_move + 1
break
if y_move + 2 >= self.map_height:
break
# 將當(dāng)前塊的位置加入地圖
for row, column in cur_block:
temp_map_block[y_move + row][x_move + column] = 1
value = self.cal_map_value(temp_map_block)
if value < value_min:
value_min = value
x_offset = i
# 返回該組合的值，和x方向偏移量
return value_min, x_offset
# 根據(jù)當(dāng)前map_block計(jì)算評(píng)分
def cal_map_value(self, map_block):
weight_space = self.weight_params[0]
weight_height_diff = self.weight_params[1]
weight_complete = self.weight_params[2]
weight_hight_max = self.weight_params[3]
weight_space_row_1 = self.weight_params[4]
weight_space_row_2 = self.weight_params[5]
space = 0
height_diff = 0
complete = 0
hight_max = 0
space_row_1 = 0
space_row_2 = 0
complete_row = []
# 計(jì)算地圖中是否有完成的行
for row in range(0, self.map_height - 1):
if 1 in map_block[row] and row > hight_max:
hight_max = row
if 0 not in map_block[row]:
complete_row.append(row)
complete = complete + 1
complete_row.sort(reverse=True)
# 將完成的行消除
for row in complete_row:
map_block.pop(row)
map_block.append([0 for column in range(0, self.map_width)])
# 每一列的高度
col_height = [0 for col in range(0, self.map_width)]
# 每一列的方塊數(shù)
col_block_num = [0 for col in range(0, self.map_width)]
# 消除行后計(jì)算各種空格數(shù)
for row in range(0, self.map_height - 4):
for column in range(0, self.map_width):
if map_block[row][column] == 1:
col_block_num[column] = col_block_num[column] + 1
if row > col_height[column]:
col_height[column] = row
if row < hight_max - 2 and sum(map_block[row]) < self.map_width - 2:
space_row_2 = space_row_2 + 1
elif row < hight_max - 2 and sum(map_block[row]) < self.map_width - 1:
space_row_1 = space_row_1 + 1
# 計(jì)算高度差之和
for col in range(0, self.map_width):
space = space + (col_height[col] - col_block_num[col])
if col < self.map_width - 1:
height = abs(col_height[col + 1] - col_height[col])
else:
height = abs(col_height[col] - col_height[col - 1])
if height > 2:
height_diff = height_diff + height - 2
value = space * weight_space + \
height_diff * weight_height_diff + \
complete * weight_complete + \
hight_max * weight_hight_max + \
space_row_1 * weight_space_row_1 + \
space_row_2 * weight_space_row_2
return value
# 計(jì)算此局游戲得分，不需要界面
def cal_score(self):
self.init_data()
self.rotate_num, self.x_offset = self.get_x_rotate_num(self.map_block, self.cur_id)
while True:
if self.rotate_num > 0:
# 旋轉(zhuǎn)一次
self.rotate()
self.rotate_num = self.rotate_num - 1
if self.x_offset > 0:
# 右移一次
self.x_offset = self.x_offset - 1
self.move_left_right(1)
if self.x_offset < 0:
# 左移一次
self.x_offset = self.x_offset + 1
self.move_left_right(-1)
# 繼續(xù)下落
is_bottom = self.block_move_down()
if is_bottom:
self.check_complete()
if self.score > self.score_min:
return self.score_min
if self.gameover:
# 游戲結(jié)束后不退出
# sys.exit()
return self.score
# 計(jì)算適應(yīng)度值，內(nèi)部循環(huán)了數(shù)次取最差值返回
def cal_value(self, params):
self.score_min = 9999999
self.weight_params = params
scores = []
num = 4
for i in range(0, num):
score = self.cal_score()
if 1000 < score < self.score_min:
self.score_min = score
scores.append(min(score, self.score_min))
return sum(scores) / num
if __name__ == '__main__':
game = GameTetrisAuto()
game.init_data()
# 對(duì)參數(shù)進(jìn)行優(yōu)化
# 維度
dim = 6
# 種群數(shù)量
size = 20
# 最大迭代次數(shù)
iter_max = 1000
range_max_list = np.array([10, 10, 10, 10, 10, 10])
# 取值范圍下界
range_min_list = np.array([-10, -10, -10, -10, -10, -10])
# 實(shí)例化差分進(jìn)化算法類
de_base = DE_Base(dim, size, iter_max, range_min_list, range_max_list)
game.top = game.map_height - 10
def fit_function(**kwargs):
params = kwargs['params']
if params is None:
params = []
game.top = int(game.map_height / 3)
return game.cal_value(params)
de_base.fitfunction = fit_function
de_base.run()
print(de_base.position_best.tolist())
# 取出上一步的結(jié)果傳回給游戲
param_list = [8.64986860882939, 3.0577645457613123, -3.555880051448894, 1.6129266015244417, 2.4287251847128744,
4.67971499710595]
game.top = game.map_height - 2
game.weight_params = param_list
game.run_auto()
print(game.score)
上面注釋掉的代碼是使用算法求解最優(yōu)解的代碼，后面的param_list是我求解出來(lái)的一組解，大約能跑數(shù)千分（暴斃是肯定會(huì)暴斃的，概率問(wèn)題）。
最終運(yùn)行效果如下：
大家可以自己改造一下模型，求一求最優(yōu)解，這里沒(méi)有優(yōu)化很久，拋磚引玉了。
我的所有代碼的目錄如下表，如果代碼import報(bào)錯(cuò)可以按照我的代碼目錄進(jìn)行修改，也可以根據(jù)ide的提示自行變更。
| \game\tetris\GameTetris.py |
| \game\tetris\GameTetrisAuto.py |
| \optimization_algorithm\frame\Unit.py |
| \optimization_algorithm\frame\Algorithm_Impl.py |
| \optimization_algorithm\algorithm_differential_evolution\DE_Unit.py |
| \optimization_algorithm\algorithm_differential_evolution\DE_Base.py |
| \optimization_algorithm\algorithm_differential_evolution\DE_Impl.py |
五． 總結(jié)
本文使用優(yōu)化算法實(shí)現(xiàn)了俄羅斯方塊的自動(dòng)化運(yùn)行。
實(shí)質(zhì)上是建立了一個(gè)模型讓游戲自動(dòng)運(yùn)行，然后使用優(yōu)化算法對(duì)模型進(jìn)行調(diào)優(yōu)?？梢钥闯黾词故且粋€(gè)簡(jiǎn)單的游戲，使用優(yōu)化算法來(lái)求解時(shí)也不像面對(duì)測(cè)試函數(shù)那般直接運(yùn)行即可，我們會(huì)遇到不少的細(xì)節(jié)問(wèn)題。
在這次應(yīng)用中，遇到了兩個(gè)最關(guān)鍵的問(wèn)題是：
1.適應(yīng)度函數(shù)不是一個(gè)冪等性函數(shù)，即使是同樣的輸入，輸出的結(jié)果可能會(huì)有很大的差別；
2.適應(yīng)度函數(shù)的運(yùn)行時(shí)間也不是固定的，越優(yōu)的解所需要的運(yùn)行時(shí)間也越長(zhǎng)（假設(shè)最優(yōu)解能讓游戲無(wú)限制的玩下去，那么其運(yùn)行時(shí)間亦是無(wú)限長(zhǎng)的，那么我們永遠(yuǎn)也無(wú)法得到最優(yōu)解）。
面對(duì)這些問(wèn)題，得明確我們的目的是什么，這里是讓游戲自行長(zhǎng)時(shí)間的運(yùn)行下去。
問(wèn)題1，我在求解適應(yīng)度函數(shù)是循環(huán)了數(shù)次，選取最差值作為當(dāng)前輸入?yún)?shù)的適應(yīng)度值，即選取下限最高的參數(shù)。但這也在加重問(wèn)題2。
問(wèn)題2，為了減少運(yùn)行時(shí)間，我修改了“訓(xùn)練集”，讓算法求解時(shí)，游戲結(jié)束條件變得更為苛刻，在正常運(yùn)行時(shí)，游戲結(jié)束條件較為寬松。
此文僅供娛樂(lè)，不是什么游戲都能（適合）用優(yōu)化算法求解的。
