【无聊系列】利用极大极小分析法玩2048
2024-04-22 23:00:45 #Boredom #Python

0. 引子

I suck at playing 2048.

所以我打算尝试一下，编写一个程序替我玩2048。2048完全可以抽象成为一个博弈问题，玩家可以进行上下左右的滑动操作，欲求分数最高；对手是游戏本身，在随机的地方生成方块，欲求让我们输掉游戏——计算机并没有什么欲求，我们假定其每次都将格子生成在最不利于我们的位置。

极小极大分析法常常用于博弈问题的求解，其优点是模型很简单，其缺点是需要细心地调参。

我曾用过这种方法求解井字棋问题，正确设置代价函数，效果蛮好；一旦修改参数，效果便会显著下降。

1. 代价/利益函数的设定

利于我们还是不利于我们，需要有判据，这个判据和地图上的局势息息相关，查阅相关资料，大概有如下的判据：

  1. 空格数量。越多越好，越多代表我们的自由度越高。
  2. 等值相邻格的对数。若有相邻的两格值相等，代表我们可以将之合并，增加分数，同时也能增加方格的个数。
  3. 平滑性是指每个方块与其直接相邻方块数值的差，其中差越小越平滑。例如2旁边是4就比2旁边是128平滑。一般认为越平滑的格局越好。第二点可以和这一条合并。
  4. 单调性。若行、列都按照递减、递增顺序排列，则能更加方便地合并格子。

我觉得还有几条判据也很重要：

  1. 最大值的格子应尽可能靠近角落，否则其必然会遮挡住某些格子，阻拦合并。
  2. 最大值越大越好，越大越有可能获得高分数。

我初步设定的利益函数为:

空格数+等值相邻格对数+单调性+最大值距离最近角落的距离+最大值的以2为底的对数。

其中不严谨的单调性计算的函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def GetRowMonotonicity(map):
    result = 0
    for i in range(map_size):
        for j in range(map_size - 1):
            if map[i][j] > map[i][j + 1]:
                result += 1
    return result

def GetColMonotonicity(map):
    result = 0
    for i in range(map_size - 1):
        for j in range(map_size):
            if map[i][j] > map[i + 1][j]:
                result += 1
    return result

def GetMonotonicity(map):
    result = 0
    row_result = GetRowMonotonicity(map)
    col_result = GetColMonotonicity(map)
    return abs(worst_monotonicity - row_result) + abs(worst_monotonicity - col_result)

对于一行来说，计算左比右大的个数，3表示该行严格递增，0表示严格递减。

2. 基本的极小极大分析法

这种方法的中心思想很简单。我们之前已经设立了利益函数，我方与对方交替下棋，我方会进行最利于我们的操作，而对方会进行最不利于我们的操作。部分代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys
import game

......

class TreeNode(object):
    def __init__(self, state, depth):
        self.state = state
        self.parent = None
        self.depth = depth
        self.score = utils.CalculateBenefit(self.state)
        self.children = []
        
......

def MiniMax(node):
    if game.GameFailed(node.state) or node.depth == max_depth:
        return node.score
    if GetNodeCategory(node) == min_node:
        node.GetOurChildren()
        temp_benefit = sys.maxsize
        for child in node.children:
            temp_benefit = min(temp_benefit, MiniMax(child))
        return temp_benefit
    else:
        node.GetOpponetsChildren()
        temp_benefit = -sys.maxsize
        for child in node.children:
            temp_benefit = max(temp_benefit, MiniMax(child))
        return temp_benefit
    
......

3. 测试

该算法的成绩大多稳定在400～500分之间，距离我最差分数600还有很明显的一段距离。最后的地图经常是这样的：

2 4 8 16
4 8 16 32
8 16 32 64
16 32 64 128

显然，我们的代价函数设置的不够精准。

对我而言，调参毫无意义，或许，我应该选用另外的模型。

参考资料

2048-AI程序算法分析

Prev
2024-04-22 23:00:45 #Boredom #Python
Next