优化算法应用（三）优化羊了个羊

作者: stronghorse | 来源:发表于2022-10-09 20:40 被阅读0次

　　羊了个羊是前段时间很火的一款广告，其玩法简单，但是通关困难。这里，我们将广告难度降一降，确保其有通关的可能。

一．目标描述

在玩儿的时候真的不知道这游戏是否有解，感觉就像一个迷宫一样，但是不知道起点和终点之间是否有一条通路。所以这里要确保游戏有解，同时保持游戏的难度不太低。
　　由于不便使用游戏源码，这里自行实现了一个类似的游戏，用于计算和判断，游戏就叫《马了个马》吧。
实现目标有三步：

实现《马了个马》。
为游戏编写自动模式，判断游戏是否有解。
使用优化算法确保游戏有解。

二．实现《马了个马》

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

优化算法应用（三）优化羊了个羊

一．目标描述

二．实现《马了个马》

1. 图片素材

2. 游戏的数据结构

3. 游戏实现

三．自动化《马了个马》

1. 规则

2. 代码实现

四．优化《马了个马》

1.测试通关率

2.优化方式

3.代码实现

4.附，差分进化代码

五．总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

优化算法应用（三）优化羊了个羊

一． 目标描述

二． 实现《马了个马》

1. 图片素材

2. 游戏的数据结构

3. 游戏实现

三． 自动化《马了个马》

1. 规则

2. 代码实现

四． 优化《马了个马》

1.测试通关率

2.优化方式

3.代码实现

4.附，差分进化代码

五． 总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一．目标描述

二．实现《马了个马》

三．自动化《马了个马》

四．优化《马了个马》

五．总结