2048游戏的最优算法探究

2048游戏的最优算法探究

技术背景

2048 是一款流行的数字合并游戏，玩家通过移动数字方块合并相同数字以得到更大数字，目标是得到 2048 这个数字。随着游戏发展，人们开始尝试用各种算法开发 AI 来玩这个游戏，以追求更高分数和更好的游戏表现。

实现步骤

期望最大化（Expectimax）算法

  1. 编码棋盘：将整个 4x4 的棋盘（16 个格子）编码为一个 64 位整数，每个格子用 4 位表示，便于在 64 位机器上高效处理。
  2. 位运算提取行列：使用位运算提取单个行或列，然后通过预计算的“移动效果表”实现移动操作。
  3. 计分表查找：使用表查找的方式进行计分，表中存储了所有可能行/列的启发式分数，棋盘的最终分数是每行和每列表值的总和。
  4. 期望最大化搜索：通过递归搜索交替进行“期望”步骤（测试所有可能的方块生成位置和值，并根据每种可能性的概率加权优化分数）和“最大化”步骤（测试所有可能的移动并选择得分最高的移动）。

蒙特卡罗树搜索算法

  1. 随机模拟：对于给定的棋盘状态，AI 在内存中使用随机移动玩游戏，直到游戏结束，并记录多次模拟的最终得分。
  2. 计算平均得分：计算每个起始移动的平均最终得分，选择平均得分最高的起始移动作为下一步的移动。

启发式算法

  1. 启发式评分：基于棋盘保持整洁和单调递减的假设，通过将棋盘上的线性化值与公比 r < 1 的几何序列的值相乘来计算得分。
  2. 决策规则：通过递归搜索，评估每个可能的移动，并选择得分最高的移动。

核心代码

期望最大化算法（JavaScript 示例）

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
var n = 4,
    M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
    var p;
    while ((p = predict(ai)) != null) {
        move(p, ai);
    }
    //console.log(ai.grid , maxValue(ai.grid))
    ai.maxValue = maxValue(ai.grid)
    console.log(ai)
}

function initialize(ai) {
    ai.grid = [];
    for (var i = 0; i < n; i++) {
        ai.grid[i] = []
        for (var j = 0; j < n; j++) {
            ai.grid[i][j] = 0;
        }
    }
    rand(ai.grid)
    rand(ai.grid)
    ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
    var newgrid = mv(p, ai.grid);
    if (!equal(newgrid, ai.grid)) {
        //console.log(stats(newgrid, ai.grid))
        ai.grid = newgrid;
        try {
            rand(ai.grid)
            ai.steps++;
        } catch (e) {
            console.log('no room', e)
        }
    }
}

function predict(ai) {
    var free = freeCells(ai.grid);
    ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
    var root = {path: [],prob: 1,grid: ai.grid,children: []};
    var x = expandMove(root, ai)
    //console.log("number of leaves", x)
    //console.log("number of leaves2", countLeaves(root))
    if (!root.children.length) return null
    var values = root.children.map(expectimax);
    var mx = max(values);
    return root.children[mx[1]].path[0]

}

function countLeaves(node) {
    var x = 0;
    if (!node.children.length) return 1;
    for (var n of node.children)
        x += countLeaves(n);
    return x;
}

function expectimax(node) {
    if (!node.children.length) {
        return node.score
    } else {
        var values = node.children.map(expectimax);
        if (node.prob) { //we are at a max node
            return Math.max.apply(null, values)
        } else { // we are at a random node
            var avg = 0;
            for (var i = 0; i < values.length; i++)
                avg += node.children[i].prob * values[i]
            return avg / (values.length / 2)
        }
    }
}

function expandRandom(node, ai) {
    var x = 0;
    for (var i = 0; i < node.grid.length; i++)
        for (var j = 0; j < node.grid.length; j++)
            if (!node.grid[i][j]) {
                var grid2 = M.copy(node.grid),
                    grid4 = M.copy(node.grid);
                grid2[i][j] = 2;
                grid4[i][j] = 4;
                var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
                var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
                node.children.push(child2)
                node.children.push(child4)
                x += expandMove(child2, ai)
                x += expandMove(child4, ai)
            }
    return x;
}

function expandMove(node, ai) { // node={grid,path,score}
    var isLeaf = true,
        x = 0;
    if (node.path.length < ai.depth) {
        for (var move of[0, 1, 2, 3]) {
            var grid = mv(move, node.grid);
            if (!equal(grid, node.grid)) {
                isLeaf = false;
                var child = {grid: grid,path: node.path.concat([move]),children: []}
                node.children.push(child)
                x += expandRandom(child, ai)
            }
        }
    }
    if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
    return isLeaf ? 1 : x;
}

// 其他辅助函数...

蒙特卡罗树搜索算法（简单示例）

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
function getNextMove(board) {
    const numRuns = 100;
    const scores = [0, 0, 0, 0]; // 分别对应上、右、下、左四个方向
    for (let move = 0; move < 4; move++) {
        if (isValidMove(board, move)) {
            for (let i = 0; i < numRuns; i++) {
                let newBoard = makeMove(board, move);
                while (!isGameOver(newBoard)) {
                    let randomMove = getRandomMove();
                    newBoard = makeMove(newBoard, randomMove);
                }
                scores[move] += getScore(newBoard);
            }
        }
    }
    let bestMove = 0;
    let maxScore = scores[0];
    for (let i = 1; i < 4; i++) {
        if (scores[i] > maxScore) {
            maxScore = scores[i];
            bestMove = i;
        }
    }
    return bestMove;
}

启发式算法（Python 示例）

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
import copy

class AI:
    @staticmethod
    def nextMove(board, recursion_depth=3):
        m, s = AI.nextMoveRecur(board, recursion_depth, recursion_depth)
        return m

    @staticmethod
    def nextMoveRecur(board, depth, maxDepth, base=0.9):
        bestScore = -1.
        bestMove = 0
        for m in range(1, 5):
            if board.validMove(m):
                newBoard = copy.deepcopy(board)
                newBoard.move(m, add_tile=True)

                score = AI.evaluate(newBoard)
                if depth != 0:
                    my_m, my_s = AI.nextMoveRecur(newBoard, depth - 1, maxDepth)
                    score += my_s * pow(base, maxDepth - depth + 1)

                if score > bestScore:
                    bestMove = m
                    bestScore = score
        return (bestMove, bestScore)

    @staticmethod
    def evaluate(board):
        # 实现启发式评分逻辑
        pass

最佳实践

期望最大化算法

  • 优化搜索深度：根据棋盘上的空闲格子数量动态调整搜索深度，如空闲格子大于 7 时搜索深度为 1，大于 4 时为 2，否则为 3。
  • 启发式函数优化：使用如单调性、平滑性、空闲格子数等启发式函数指导搜索，提高算法性能。

蒙特卡罗树搜索算法

  • 增加模拟次数：适当增加每次移动的模拟次数可以提高决策的准确性，但会增加计算时间。
  • 并行计算：可以使用并行计算来加速模拟过程。

启发式算法

  • 调整启发式函数权重：通过实验调整启发式函数的权重，以获得更好的性能。
  • 结合其他算法：可以将启发式算法与其他算法（如期望最大化算法）结合使用。

常见问题

计算资源消耗大

  • 原因：一些算法（如期望最大化算法）需要搜索大量的游戏状态，导致计算资源消耗大。
  • 解决方案：使用位运算、表查找等技术优化算法，减少计算量；动态调整搜索深度，避免不必要的搜索。

启发式函数选择不当

  • 原因：不同的启发式函数对算法性能有很大影响，如果选择不当，可能导致算法性能不佳。
  • 解决方案：通过实验和分析，选择合适的启发式函数，并调整其权重。

随机因素影响

  • 原因：2048 游戏中存在随机生成方块的因素，可能导致算法的表现不稳定。
  • 解决方案：增加模拟次数或使用多次实验的平均结果来评估算法性能。