algorithm - 2048 启发式，意想不到的结果

Question

我正在为 2048 开发一个 AI。到目前为止它非常简单，我基本上是在尝试制作一个由递减方 block 组成的“蛇”，所以完美的游戏应该是这样的: ，虽然这和这个一样好: .

我的启发式方法是使用一个简单的二维数组，将每个单元格乘以摇晃形状的递减幅度，例如:

---------------------
| 16 | 15 | 14 | 13 |
| 9  | 10 | 11 | 12 |
| 8  | 7  | 6  | 5  |
| 1  | 2  | 3  | 4  |
---------------------

这工作得很好，大约一半的时间达到 2048，但有时它会做出非常奇怪的决定，例如:

Suggests right, correct is left

Suggests right, correct is left

Suggests down, correct is left

Suggests down, correct is left/right

是否可以调整权重或添加某种惩罚来惩罚这种行为？其他一切工作正常，甚至在数学上其中一些没有任何意义。 F.ex. #3 显然向左比向下更好，最大的被乘数在角落，将 256 合并到角落应该会产生最好的结果？

编辑:

def getBestMove(node, depth):
    bestValue, bestAction = -1, None
    for direction in xrange(4):
        temp, score, moved = Board.move(node, direction)
        if not moved: continue
        val = minimax(temp, depth - 1, False)
        if val > bestValue:
            bestValue = val
            bestAction = direction
    return bestValue, bestAction


def minimax(node, depth, maximizingPlayer):
    if depth == 0:
        return heuristic(node)
    elif Board.isLost(node):
        return 0

    if maximizingPlayer:
        bestValue = -1
        for direction in xrange(4):
            temp, score, moved = Board.move(node, direction)
            if not moved: continue
            val = minimax(temp, depth - 1, False)
            if val > bestValue: bestValue = val
        return bestValue
    else:
        bestValue = 1<<20
        for cell in Board.getFreeCells(node):
            for cellValue in [2, 4]:
                temp = deepcopy(node)
                temp[cell[0]][cell[1]] = cellValue

                val = minimax(temp, depth - 1, True)
                if val < bestValue: bestValue = val
        return bestValue

是我使用的 minimax 的基本实现。所描述的启发式函数是二维数组的简单乘法。一个是棋盘本身，一个是面具，一共有4个面具，就是那条从四个不同角开始递减的“蛇”:

def heuristic(board):
    return max([mulArr(board, grid) for grid in grids])


def mulArr(arr1, arr2):
    return sum([arr1[i][j]*arr2[i][j] for i in xrange(len(arr1)) for j in xrange(len(arr1))])

Answer 1

对于您的启发式，您可以尝试:

| 32768 16384 8192 4096 |
|  256   512  1024 2048 |
|  128    64   32   16  |
|   1     2     4    8  |

然后找到最小值？