羊了个羊是前段时间很火的一款广告，其玩法简单，但是通关困难。这里，我们将广告难度降一降，确保其有通关的可能。
一． 目标描述
在玩儿的时候真的不知道这游戏是否有解，感觉就像一个迷宫一样，但是不知道起点和终点之间是否有一条通路。所以这里要确保游戏有解，同时保持游戏的难度不太低。
由于不便使用游戏源码，这里自行实现了一个类似的游戏，用于计算和判断，游戏就叫《马了个马》吧。
实现目标有三步：
- 实现《马了个马》。
- 为游戏编写自动模式，判断游戏是否有解。
- 使用优化算法确保游戏有解。
二． 实现《马了个马》
1. 图片素材
图片素材没有《羊了个羊》那么多，一共12张图片。
0.jpg
1.jpg
2.jpg
3.jpg
4.jpg
5.jpg
6.jpg
7.jpg
8.jpg
9.jpg
10.jpg
11.jpg
2. 游戏的数据结构
游戏中不同层之间会相互遮挡，被遮住的图片会无法点击。
为了方便后续计算，我将图片存储在了一个“链表树”中。每一张图都是其中的一个节点，被自己遮挡的图片为自己的子节点，遮挡自己的图片为自己的父节点。每个节点都要记录下自己全部的父节点和子节点。
这样，就有了一个较为简单判断图片能否点击的方法：如果一张图片的父节点数量为0，那么它可以点击。让一张图片成为可点击所需的最少步数为其父节点数量之和（也包括父节点的父节点，递归计算）。
如上图，其节点情况如下表
| 颜色 | 父节点 | 子节点 |
|---|---|---|
| 红 | 无 | 蓝 |
| 蓝 | 红 | 橙，绿 |
| 橙 | 蓝 | 无 |
| 绿 | 蓝 | 无 |
从表中可知，红色图片为可点击图片，蓝色图片不可点击，变为可点击至少要1步（点击红色），橙色和绿色为不可点击图片，变为可点击至少需要2步（依次点击红色，蓝色图片）。
该节点的代码实现如下：
class CardTreeNode:
level = -1
x = -1
y = -1
image_id = -1
parent_list = []
child_list = []
def __init__(self,level,x,y,image_id):
self.level = level
self.x = x
self.y = y
self.image_id = image_id
self.parent_list = []
self.child_list = []
其中level,x,y表示该图片在游戏地图中的位置，parent_list为父节点的位置列表，child_list为子节点的位置列表。
3. 游戏实现
将图片放在同一文件夹下即可。
代码如下：
import sys
import tkinter
from math import floor
import numpy as np
import pygame
import pygame.gfxdraw
from tkinter import messagebox
from game.hooorse.CardTreeNode import CardTreeNode
class GameHooorse:
# 卡片尺寸
card_length = 60
# 窗口大小：平铺多少张卡片
window_height = 12
window_width = 8
# 卡的种类
type_num = 12
# 每种卡的组数
card_num = 1
# 总层数
level_num = 2
# 各层各边卡片数
level_card_num_1 = 6
level_card_num_2 = 5
# 每层卡片的左上位置
left_1 = (window_width - level_card_num_1) / 2
top_1 = (window_height - level_card_num_1) / 2 - 2
left_2 = (window_width - level_card_num_2) / 2
top_2 = (window_height - level_card_num_2) / 2 - 2
# 卡片图
card_tree_map = dict()
# 卡片槽
sorted_list = []
# 卡片槽最大值
max_sorted = 10
# 卡片总数
all_card_num = 0
# 剩余卡片数量
left_card = 0
gameover = -1 # -1 未完成，0 失败，1，完成
# 初始化数据
def init_data(self):
self.card_tree_map.clear()
self.gameover = -1
self.sorted_list = []
self.all_card_num = 3 * self.card_num * self.type_num
self.left_card = self.all_card_num
# 初始化卡片
def init_card(self):
# 卡列表，记录所有的卡
card_list = []
# 将卡按顺序加入数组
for i in range(self.type_num):
for j in range(self.card_num):
card_list.append(i)
card_list.append(i)
card_list.append(i)
# 空白的卡数量，即不存在的卡
left_space_num = - self.type_num * self.card_num * 3
for i in range(0, self.level_num):
if i % 2 == 0:
left_space_num = left_space_num + self.level_card_num_1 * self.level_card_num_1
else:
left_space_num = left_space_num + self.level_card_num_2 * self.level_card_num_2
# 在卡列表中混入不存在的卡
for i in range(left_space_num):
card_list.append(-1)
# 将数组乱序
np.random.shuffle(card_list)
# 按顺序将乱序卡组填入地图中
cursor = 0
for i in range(0, self.level_num):
if i % 2 == 0:
level_card_num = self.level_card_num_1
else:
level_card_num = self.level_card_num_2
for j in range(level_card_num):
for k in range(level_card_num):
key = (i, j, k)
if card_list[cursor] == -1:
cursor = cursor + 1
continue
# 将有图片的位置保存为树
node = CardTreeNode(i, j, k, card_list[cursor])
self.card_tree_map[key] = node
cursor = cursor + 1
self.cal_can_click()
# 根据id获取图像
def get_image_by_id(self, id):
image_name = str(int(id)) + ".jpg"
image = pygame.image.load(image_name).convert()
image = pygame.transform.scale(image, (self.card_length, self.card_length))
return image
# 计算图片是否能被点击
def cal_can_click(self):
# 逆序遍历
for i in range(self.level_num - 1, -1, -1):
if i % 2 == 0:
for j in range(self.level_card_num_1):
for k in range(self.level_card_num_1):
parent_key = (i, j, k)
if parent_key not in self.card_tree_map:
continue
for m in range(i - 1, -1, -1):
if m % 2 == 0:
child_key = (m, j, k)
# 不相邻层，位置相同
# 被挡住了不能点击
self.set_parent_child(parent_key, child_key)
else:
# 四个角
if j == 0 and k == 0:
child_key = (m, j, k)
self.set_parent_child(parent_key, child_key)
elif j == 0 and k == self.level_card_num_1 - 1:
child_key = (m, 0, self.level_card_num_2 - 1)
self.set_parent_child(parent_key, child_key)
elif j == self.level_card_num_1 - 1 and k == 0:
child_key = (m, self.level_card_num_2 - 1, 0)
self.set_parent_child(parent_key, child_key)
elif j == self.level_card_num_1 - 1 and k == self.level_card_num_1 - 1:
child_key = (m, self.level_card_num_2 - 1, self.level_card_num_2 - 1)
self.set_parent_child(parent_key, child_key)
# 四条边
elif j == 0:
child_key = (m, 0, k)
self.set_parent_child(parent_key, child_key)
child_key = (m, 0, k - 1)
self.set_parent_child(parent_key, child_key)
elif k == 0:
child_key = (m, j, 0)
self.set_parent_child(parent_key, child_key)
child_key = (m, j - 1, 0)
self.set_parent_child(parent_key, child_key)
elif j == self.level_card_num_1 - 1:
child_key = (m, self.level_card_num_2 - 1, k)
self.set_parent_child(parent_key, child_key)
child_key = (m, self.level_card_num_2 - 1, k - 1)
self.set_parent_child(parent_key, child_key)
elif k == self.level_card_num_1 - 1:
child_key = (m, j, self.level_card_num_2 - 1)
self.set_parent_child(parent_key, child_key)
child_key = (m, j - 1, self.level_card_num_2 - 1)
self.set_parent_child(parent_key, child_key)
else:
# 内部
child_key = (m, j, k)
self.set_parent_child(parent_key, child_key)
child_key = (m, j - 1, k)
self.set_parent_child(parent_key, child_key)
child_key = (m, j, k - 1)
self.set_parent_child(parent_key, child_key)
child_key = (m, j - 1, k - 1)
self.set_parent_child(parent_key, child_key)
else:
for j in range(self.level_card_num_2):
for k in range(self.level_card_num_2):
parent_key = (i, j, k)
if parent_key not in self.card_tree_map:
continue
for m in range(i - 1, -1, -1):
if m % 2 == 0:
child_key = (m, j, k)
self.set_parent_child(parent_key, child_key)
child_key = (m, j + 1, k)
self.set_parent_child(parent_key, child_key)
child_key = (m, j, k + 1)
self.set_parent_child(parent_key, child_key)
child_key = (m, j + 1, k + 1)
self.set_parent_child(parent_key, child_key)
else:
# 被挡住了不能点击
child_key = (m, j, k)
self.set_parent_child(parent_key, child_key)
def set_parent_child(self, parent_key, child_key):
if parent_key not in self.card_tree_map:
return
if child_key not in self.card_tree_map:
return
self.card_tree_map[child_key].parent_list.append(parent_key)
self.card_tree_map[parent_key].child_list.append(child_key)
# 点击事件
def on_click(self, pos):
x = pos[0]
y = pos[1]
# # 逆序遍历
for i in range(self.level_num - 1, -1, -1):
if i % 2 == 0:
# 将点击坐标转化为图片的左上角位置
x_index = floor((x / self.card_length) - self.left_1)
y_index = floor((y / self.card_length) - self.left_1)
if x_index < 0 or x_index >= self.level_card_num_1:
continue
if y_index < 0 or y_index >= self.level_card_num_1:
continue
else:
# 将点击坐标转化为图片的左上角位置
x_index = floor((x / self.card_length) - self.left_2)
y_index = floor((y / self.card_length) - self.left_2)
if x_index < 0 or x_index >= self.level_card_num_2:
continue
if y_index < 0 or y_index >= self.level_card_num_2:
continue
key = (i, x_index, y_index)
# 消除这一块
if key in self.card_tree_map:
if len(self.card_tree_map[key].parent_list) > 0:
continue
self.left_card = self.left_card - 1 # 剩余卡数减1
self.sorted_list.append(self.card_tree_map[key].image_id)
self.sorted_list = sorted(self.sorted_list)
# 将该块的child删除此parent
for node in self.card_tree_map[key].child_list:
self.card_tree_map[node].parent_list.remove(key)
self.card_tree_map.pop(key)
self.remove_3_card()
return
# 3消
def remove_3_card(self):
cur_id = -1
same_num = 1
index = 0
remove_index_list = []
for i in self.sorted_list:
if i == cur_id:
same_num = same_num + 1
else:
cur_id = i
same_num = 1
if same_num == 3:
remove_index_list.extend([index,index - 1,index - 2])
same_num = 0
index = index + 1
temp_list = []
for index in range(len(self.sorted_list)):
if index not in remove_index_list:
temp_list.append(self.sorted_list[index])
self.sorted_list.clear()
self.sorted_list.extend(temp_list)
if len(self.sorted_list) >= self.max_sorted:
self.gameover = 0
else:
if self.left_card == 0:
self.gameover = 1
# 绘制屏幕
def draw_screen(self):
# 绘制每一层的图片
for i in range(self.level_num):
if i % 2 == 0:
# 绘制偶数层图片
level_card_num = self.level_card_num_1
left = self.left_1
top = self.top_1
else:
# 绘制偶数层图片
level_card_num = self.level_card_num_2
left = self.left_2
top = self.top_2
for j in range(level_card_num):
for k in range(level_card_num):
key = (i, j, k)
if key not in self.card_tree_map:
continue
image_id = self.card_tree_map[key].image_id
if image_id == -1:
continue
image = self.get_image_by_id(image_id)
pygame.draw.rect(image, (255, 255, 255), [0, 0, self.card_length, self.card_length], 2,
border_radius=3)
# 如果不能点击则降低透明度
if len(self.card_tree_map[key].parent_list) > 0:
pygame.gfxdraw.box(image, [0, 0, self.card_length, self.card_length], (0, 0, 0, 150))
self.screen.blit(image,
((j + left) * self.card_length, (k + top) * self.card_length))
# 绘制下方槽位
pygame.draw.rect(self.screen, (255, 255, 255), (
0, (self.window_height - 3) * self.card_length, self.window_width * self.card_length, 2 * self.card_length),
1)
# 绘制槽位内的图
for i in range(len(self.sorted_list)):
image = self.get_image_by_id(self.sorted_list[i])
pygame.draw.rect(image, (255, 255, 255), [0, 0, self.card_length, self.card_length], 2, border_radius=3)
if i < 8:
self.screen.blit(image, (i * self.card_length, (self.window_height - 3) * self.card_length))
else:
self.screen.blit(image, (i % 8 * self.card_length, (self.window_height - 2) * self.card_length))
def run(self):
root = tkinter.Tk()
root.withdraw()
pygame.init()
self.screen = pygame.display.set_mode(
(self.window_width * self.card_length, self.window_height * self.card_length))
pygame.display.set_caption("马了个马")
while True:
self.screen.fill((110, 110, 110))
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
elif event.type == pygame.MOUSEBUTTONUP:
self.on_click(event.pos)
self.draw_screen()
# 成功或失败
if self.gameover == 0:
messagebox.showinfo("游戏失败", "游戏失败")
self.init_data()
self.init_card()
elif self.gameover == 1:
messagebox.showinfo("游戏结束", "游戏完成")
self.init_data()
self.init_card()
pygame.time.Clock().tick(200)
pygame.display.flip()
if __name__ == "__main__":
game = GameHooorse()
# 层数
game.level_num = 2
# 每种卡片组数
game.card_num = 1
game.init_data()
game.init_card()
game.run()
代码运行效果如下：
三． 自动化《马了个马》
为了判断游戏是否有解，我需要电脑帮我去判断，总不能靠人工去玩儿吧。于是我根据我的游玩习惯，编写了一个自动玩儿的代码来进行游戏。注意该代码运行有解是游戏有解的非充分非必要条件，仅提供一个估算作用。
1. 规则
计算3消一类图片所需要的点击数，然后将所需点击数从小到大排列，选择点击数最少的图片进行点击。
如上图，可点击的图片中，3消完成所需图片数量如下：
易知，蝴蝶是所需点击数最少的图片，所以下一步会优先点击蝴蝶。
在实际的游戏中，情况要复杂的多，对每一张图片计算所需点击数计算量也不小。为了减少计算量，我会按照以下方式来遍历：
1. 计算父节点数量为0的图片类型所需的点击数，如果无解，则跳到2，否则返回解
2. 计算父节点不大于1的图片类型所需的点击数，如果无解，则跳到3，否则返回解
3. 计算父节点不大于1的图片类型所需的点击数，如果无解，则跳到4，否则返回解
4. 。。。。
按照这种方式，上面的游戏中，将不会计算麻雀图片所需要的点击数，因为麻雀图片每一张图都有至少一个父节点。在上图中其实影响不大，不过上图只有两层，而实际游戏中可能会有几十层，彼时将会节约巨大的计算量。
按照上述规则，如果游戏能够结束，那么则游戏必定有解。
2. 代码实现
import sys
import tkinter
from tkinter import messagebox
import pygame
from game.hooorse.GameHooorse import GameHooorse
class GameHooorseAuto(GameHooorse):
times = 0
# 点击事件
def on_click_xy(self, key):
# 消除这一块
if key in self.card_tree_map:
if len(self.card_tree_map[key].parent_list) > 0:
return
self.left_card = self.left_card - 1 # 剩余卡数减1
self.sorted_list.append(self.card_tree_map[key].image_id)
self.sorted_list = sorted(self.sorted_list)
# 将该块的child删除此parent
for node in self.card_tree_map[key].child_list:
self.card_tree_map[node].parent_list.remove(key)
# 将点击的图片移除
self.card_tree_map.pop(key)
# 检查能否3消
self.remove_3_card()
return
def run_auto(self):
root = tkinter.Tk()
root.withdraw()
pygame.init()
self.screen = pygame.display.set_mode(
(self.window_width * self.card_length, self.window_height * self.card_length))
pygame.display.set_caption("马了个马")
while True:
self.screen.fill((110, 110, 110))
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
elif event.type == pygame.MOUSEBUTTONUP:
self.on_click(event.pos)
if self.times >= 5:
# 计算点击位置并点击
pos = self.get_click_pos()
self.on_click_xy(pos)
self.times = 0
else:
self.times += 1
self.draw_screen()
# 成功或失败
if self.gameover == 0:
messagebox.showinfo("游戏失败", "游戏失败")
self.init_data()
self.init_card()
elif self.gameover == 1:
messagebox.showinfo("游戏结束", "游戏完成")
self.init_data()
self.init_card()
pygame.time.Clock().tick(200)
pygame.display.flip()
# 计算此次点击的位置
def get_click_pos(self):
# 计算槽位中各图片的数量
sorted_id_num = dict()
for id in self.sorted_list:
if id not in sorted_id_num:
sorted_id_num[id] = 1
else:
sorted_id_num[id] = sorted_id_num[id] + 1
# 将可点击的图片也按照槽中图片计算，只是数量为0
for key in self.card_tree_map:
image_id = self.card_tree_map[key].image_id
if image_id not in sorted_id_num:
sorted_id_num[image_id] = 0
result_pos = None
pos_list_map = dict()
pos_num_map = dict()
# 阈值：父类压盖数量
threshold_num = 0
while result_pos is None:
# 遍历槽中的图片：下方槽中或者上方可点击的类型
for image_id in sorted_id_num:
# 计算点击该类图片实现3消所需的点击次数
pos_list = self.get_click_pos_by_image_id(image_id, 3 - sorted_id_num[image_id], threshold_num)
if pos_list is None or len(pos_list) == 0:
continue
if len(pos_list) == 1:
result_pos = pos_list[0]
break
# 将点击位置序列存入map,key为序列长度
pos_list_map[image_id] = pos_list
pos_num_map[image_id] = len(pos_list)
if result_pos is None:
if len(pos_list_map) > 0:
# 选择点击次数最少的类型来点击
image_id = sorted(pos_num_map.items(), key=lambda x: x[1], reverse=False)[0][0]
result_pos = pos_list_map[image_id][0]
# 在该阈值下找不到符合条件的位置则降低条件
threshold_num = threshold_num + 1
return result_pos
# 通过图片id,需要点击的数量，父类数量确定点击序列
def get_click_pos_by_image_id(self, image_id, num, threshold_num):
# 获取点击序列及父类数量
pos_parent_map = dict()
pos_parent_num = dict()
for key in self.card_tree_map:
node = self.card_tree_map[key]
if node.image_id != image_id:
continue
if len(node.parent_list) > threshold_num:
continue
parent_pos_list = self.get_parent_list(key)
pos_parent_map[key] = parent_pos_list
pos_parent_num[key] = len(parent_pos_list)
result_list = []
# 按需要点击的图片数量，从小到大排序
sorted_num = sorted(pos_parent_num.items(), key=lambda x: x[1], reverse=False)
if num > len(sorted_num):
return None
# 选取点击数量最少的序列作为结果返回
for i in range(num):
key = sorted_num[i][0] # 排在第一位的key
pos_parent_map[key].reverse()
result_list.extend(pos_parent_map[key])
return result_list
# 递归，获取指定位置的父节点
def get_parent_list(self, key):
node = self.card_tree_map[key]
parent_list = [key]
for parent_key in node.parent_list:
if parent_key not in parent_list:
parent_list.append(parent_key)
else:
# 将父节点放在最后
parent_list.remove(parent_key)
parent_list.append(parent_key)
pp_list = self.get_parent_list(parent_key)
for p in pp_list:
if p not in parent_list:
parent_list.append(p)
else:
# 将父节点放在最后
parent_list.remove(p)
parent_list.append(p)
return parent_list
if __name__ == '__main__':
game = GameHooorseAuto()
game.level_num = 2
game.card_num = 1
game.max_sorted = 7
# 初始化数据
game.init_data()
# 初始化方块
game.init_card()
game.run_auto()
其运行效果如下：
四． 优化《马了个马》
1.测试通关率
优化之前先看看代码通关的概率。
每类图片10组，共10*12*3=360张图片。
游戏层数，由于每两层的图片数为6*6+5*5=61张，故至少需要12层。
每次游戏如果失败，游戏的完成度=消除图片数/图片总数。
每次进行100次游戏
| 层数 | 通关率 | 完成度 |
|---|---|---|
| 12 | 0.36 | 0.7954 |
| 13 | 0.27 | 0.734 |
| 14 | 0.27 | 0.7116 |
| 15 | 0.06 | 0.5726 |
| 16 | 0.07 | 0.5022 |
| 17 | 0.07 | 0.5395 |
| 18 | 0.02 | 0.4365 |
| 19 | 0.03 | 0.4277 |
| 20 | 0.01 | 0.4217 |
| 21 | 0.02 | 0.3964 |
| 22 | 0 | 0.3537 |
| 23 | 0 | 0.3250 |
| 24 | 0 | 0.3499 |
| 25 | 0 | 0.3340 |
| 26 | 0 | 0.2993 |
| 27 | 0 | 0.3217 |
| 28 | 0 | 0.3094 |
| 29 | 0.01 | 0.3317 |
| 30 | 0 | 0.3299 |
可以看到，在图片数量为360时，若层数超过15层，通关率将直线下降，最终将会稳定在0，完成度为1/3左右。
后面优化时将会使用26层来进行试验。
2.优化方式
显然，这次优化的适应度函数为游戏的完成度，目标就是将完成度提升到100%。
那么如何提升游戏的完成度呢？
我的方案是：交换两张图片位置，如果完成度提高则保留该操作。反复进行该操做，完成度到达100%时停止。
上图中每一次循环都是一次完整的优化过程，即每一次循环都是在优化算法中经历数次迭代，最后得出结果去更新地图。每一次循环都会交换两张图片的位置，优化算法则是用来确定每一次交换哪两张图片。
3.代码实现
import copy
from game.hooorse.GameHooorseAuto import GameHooorseAuto
from optimization_algorithm.algorithm_differential_evolution.DE_Base import DE_Base
import numpy as np
class GameHooorseAutoOpt(GameHooorseAuto):
# 卡片位置列表，优化时使用
card_key_list = None
# 传入卡片树,后面需要
def set_card_tree_map(self, tree_map):
self.card_tree_map.clear()
for key in tree_map:
node = copy.deepcopy(tree_map[key])
self.card_tree_map[key] = node
self.card_key_list = sorted(self.card_tree_map)
def get_score(self, params):
if params is not None and len(params) > 0:
id1 = int(params[0])
id2 = int(params[1])
key1 = self.card_key_list[id1]
key2 = self.card_key_list[id2]
image_1 = self.card_tree_map[key1].image_id
image_2 = self.card_tree_map[key2].image_id
# 交换选择的两个位置的图片
self.card_tree_map[key1].image_id = image_2
self.card_tree_map[key2].image_id = image_1
while True:
if self.times >= 5:
pos = self.get_click_pos()
self.on_click_xy(pos)
self.times = 0
else:
self.times += 1
if self.gameover != -1:
# 计算完成率
return 1 - self.left_card / self.all_card_num
def opt():
game = GameHooorseAutoOpt()
game.level_num = 26
game.card_num = 10
game.max_sorted = 7
game.init_data()
game.init_card()
# 复制原有的卡片树用以保存原游戏
temp_card_tree_map = dict()
for key in game.card_tree_map:
node = copy.deepcopy(game.card_tree_map[key])
temp_card_tree_map[key] = node
# 维度
dim = 2
# 种群数量
size = 5
# 最大迭代次数
iter_max = 10
range_max_list = np.array([game.all_card_num - 1, game.all_card_num - 1])
# 取值范围下界
range_min_list = np.array([0, 0])
# 实例化差分进化算法类
de_base = DE_Base(dim, size, iter_max, range_min_list, range_max_list)
def fit_function(**kwargs):
game.init_data()
game.set_card_tree_map(temp_card_tree_map)
params = kwargs['params']
if params is None:
params = []
return game.get_score(params)
de_base.fitfunction = fit_function
best_value = 0
update_time = 0
while best_value < 1:
de_base.run()
print(de_base.position_best.tolist())
best_value = de_base.value_best
id1 = int(de_base.position_best[0])
id2 = int(de_base.position_best[1])
key1 = game.card_key_list[id1]
key2 = game.card_key_list[id2]
image_1 = temp_card_tree_map[key1].image_id
image_2 = temp_card_tree_map[key2].image_id
# 交换选择的两个位置的图片
temp_card_tree_map[key1].image_id = image_2
temp_card_tree_map[key2].image_id = image_1
update_time = update_time + 1
print("更新次数", update_time)
game.init_data()
game.set_card_tree_map(temp_card_tree_map)
# 电脑自己玩
game.run_auto()
# 玩家玩
# game.run()
if __name__ == '__main__':
opt()
运行效果如下：
4.附，差分进化代码
同上一篇
实现基本与matlab版本结构一致：
| 文件名 | 文件描述 |
|---|---|
| Unit.py | 个体基类 |
| Algorithm_Impl.py | 算法基类 |
| DE_Unit.py | 差分进化算法个体 |
| DE_Base.py | 差分进化算法基础实现 |
| DE_Impl.py | 差分进化算法实现 |
# 个体基类
class Unit:
dim = 0
position = None
value = 0
def __init__(self, dim):
self.dim = dim
self.position = [0]*dim
# 优化算法基类
import sys
import numpy as np
class Algorithm_Impl:
# 当前最优位置
position_best = None
# 当前最优适应度
value_best = - sys.float_info.max
# 历史最优适应度
value_best_history = list()
# 是否为求最大值, 默认为是
is_cal_max = True
# 适应度函数，需要单独传入
fitfunction = None
# 调用适应度函数次数
cal_fit_num = 0
# 维度
dim = 1
# 种群中个体的数量
size = 1
# 最大迭代次数
iter_max = 1
# 解空间下界
range_min_list = list()
# 解空间上界
range_max_list = list()
# 种群列表
unit_list = list()
# 构造函数
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
# 默认为求最大值
self.is_cal_max = True
# 初始化算法中的个体
def init_unit(self):
self.position_best = np.zeros((1, self.dim))[0]
self.value_best_history = []
# 设置初始最优值，由于是求最大值，所以设置了最大浮点数的负值
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)
# 计算适应度函数
def cal_fitfunction(self, position=None):
if position is None:
return 0
if self.fitfunction is None:
return 0
return self.fitfunction(params=position)
# 设置适应度函数
def set_fitfunction(self, fit_function):
self.fitfunction = fit_function
# 运行入口
def run(self):
self.init_unit()
self.iteration()
return
# 循环迭代
def iteration(self):
for i in range(self.iter_max):
self.update(i)
return
# 更新一次迭代
def update(self, iter):
# 记录最优值
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('最优值=', self.value_best)
else:
self.value_best_history.append(-self.value_best)
print('最优值=', -self.value_best)
print('最优解=', 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
# 差分进化算法个体
from optimization_algorithm.frame.Unit import Unit
class DE_Unit(Unit):
# 个体的新位置(变异位置)
position_new = None
def __init__(self, dim):
super().__init__(dim)
# 差分进化算法
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
# 初始化算法中的个体
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个不重复的随机数
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
# 差分进化算法实现
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)
# 测试脚本
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
## 算法实例
# 维度
dim = 30
# 种群数量
size = 60
# 最大迭代次数
iter_max = 1000
# 取值范围上界
range_max_list = np.ones((1, dim))[0] * 100
# 取值范围下界
range_min_list = np.ones((1, dim))[0] * -100
# 实例化差分进化算法类
base = DE_Base(dim, size, iter_max, range_min_list, range_max_list)
base.is_cal_max = False
# 确定适应度函数
base.fitfunction = fit_function
# 运行
base.run()
print(base.value_best)
print(base.position_best)
五． 总结
虽然能够保证游戏有解，但是优化的过程是不可控的，有可能需要较长的时间才能得到一个有解的地图。同时由于自动程序运行时是已知全地图，而玩家玩儿的时候无法知道被完全遮挡的图片是什么，这也会在无形之间增加了游戏的难度。
在这一次的应用中，优化算法不止被应用了一次。每一次修改图片都会使用优化算法计算交换哪两张图片，同时为了缩减时间，每次优化算法的种群数和最大迭代次数都设置的比较小。因为仅交换两张图片就成功的概率不确定，所以这里进行了多次交换，每次交换两张，这样也更方便跳出循环进入游戏。
文件目录如下：
| \game\hooorse\GameHooorse.py |
| \game\hooorse\GameHooorseAuto.py |
| \game\hooorse\GameHooorseAutoOpt.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 |
