以井字棋为例的游戏机器人实现思路

TES286

背景

假如目前, 我们要做一个游戏, 可以让玩家和电脑下井字棋, 即在3x3的格子中画勾圈的游戏, 也就是这种:

那么我们要如何简单高效的去实现电脑的决策呢?

本文将以井字棋为例介绍如何写一个简单的游戏机器人, 介绍的思路经过扩展, 理论上是可以适用于各种复杂的情况的.

方法1: 内置所有情况

内置所有的情况无疑是个很好的办法.

但是, 在井字棋这看似很简单的游戏中, 却又有很多种情况.

理论上, 忽略重复和胜利判定, 井字棋有3^9=19683 ( 约2万 ) 种情况和9!=362880 ( 约36万 ) 种过程, 不仅内置的录入需要大量的时间, 而且对玩家来说, 每次操作游戏都会把游戏卡很久 ( 内部的遍历和对比 ), 用户体验无疑很差.

假设每一个格子内可以有 "O", "X", 空白 三种情况, 每两个格子互不干扰, 共 9 格, 那么总共就是 3^9 种情况

游戏有9个格子, 也就是9步下完, 第一步有9个空格, 第二步有8个空格, ..., 最后, 总共有 9x8x7x...x1=9!=362880种情况

那么, 这种方案需要改进

方法2: 只内置可能的情况

方法1中, 有很多在实际情况下不可能的情况, 我们可以去掉这些情况.

以玩家先手为例:

1. 玩家可能在9个格中任选一个下子, 此时机器人需应对这9种情况, 各下一子, 剩下7个格子
2. 玩家可能在7个格中任选一个下子, 此时机器人需应对这7种情况, 各下一子, 剩下5个格子
3. ......

最终, 有9x7x5x3x1=945种情况, 比上述少了很多种情况, 但这明显不是最优.

方法3: 让机器人自主思考

玩家在玩这个游戏中, 一般会遵循以下规则:

• 尽力使自己可以有3子在同一直线
• 尽力阻止对方有3子在同一直线

我们可以让机器人也如此思考.

我们可以给每个操作定一个系数, 计算每一个格子得分, 最终取分数最大的格子下子.

例如这样("X"为玩家, 数字代表分数, 假设系数全为1):

X	1	1
O	3	1
X	1	1

在这种情况下, 明显应选第二行第二列的格子.
然后, 经过微调系数, 可以造就一个优秀的电脑棋手

根据这个思想实现的"优秀"的棋手 (所有系数设置为1, 部分情况的逻辑未加入)

至于系数的选择, 本文不讨论, 可以自己测试. (可以让系数不同的机器人互相对抗, 选取最优)

示例代码

[Python] 纯文本查看 复制代码

from typing import List, Tuple, Union


winMaps = [
    [
        ['x', 'x', 'x'],
        ['*', '*', '*'],
        ['*', '*', '*'],
    ],
    [
        ['*', '*', '*'],
        ['x', 'x', 'x'],
        ['*', '*', '*'],
    ],
    [
        ['*', '*', '*'],
        ['*', '*', '*'],
        ['x', 'x', 'x'],
    ],
    [
        ['x', '*', '*'],
        ['x', '*', '*'],
        ['x', '*', '*'],
    ],
    [
        ['*', 'x', '*'],
        ['*', 'x', '*'],
        ['*', 'x', '*'],
    ],
    [
        ['*', '*', 'x'],
        ['*', '*', 'x'],
        ['*', '*', 'x'],
    ],
    [
        ['x', '*', '*'],
        ['*', 'x', '*'],
        ['*', '*', 'x'],
    ],
    [
        ['*', '*', 'x'],
        ['*', 'x', '*'],
        ['x', '*', '*'],
    ]
]


def compareMap(mask: List[List[str]], map: List[List[str]]) -> str:
    symbol = '-'
    for i in range(3):
        for j in range(3):
            if mask[i][j] == '*':
                continue
            elif mask[i][j] == 'x':
                if map[i][j] == ' ':
                    return ' '
                if symbol == '-':
                    symbol = map[i][j]
                if map[i][j] != symbol:
                    return ' '
                else:
                    continue
    return symbol if symbol != '-' else ' '


def ifWin(map: List[List[str]]) -> str:
    for winMap in winMaps:
        d = compareMap(winMap, map)
        if d != ' ':
            return d
    return ' '


def choiceTop(map: List[List[int]]) -> Tuple[int, int]:
    topX = 0
    topY = 0
    topVal = 0
    for i in range(3):
        for j in range(3):
            if map[i][j] > topVal:
                topX, topY = i, j
                topVal = map[i][j]
    return topX, topY


def mapAdd(map1: List[List[int]], map2: List[List[int]], *mapN: List[List[List[int]]]) -> List[List[int]]:
    newMap = [
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
    ]
    for i in range(3):
        for j in range(3):
            newMap[i][j] = map1[i][j] + map2[i][j]
    return newMap if len(mapN) == 0 else mapAdd(newMap, mapN[0], *mapN[1:])


def makeSelfWin(map: List[List[str]]):
    scoures = [
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
    ]
    for i in range(3):
        for j in range(3):
            if map[i][j] != ' ':
                scoures[i][j] = -10
            if map[i][j] == 'X':
                for a in range(3):
                    if map[i][a] == ' ':
                        scoures[i][a] += 1
                    if map[a][j] == ' ':
                        scoures[a][j] += 1
                if i == j:
                    for a in range(3):
                        if map[a][a] == ' ':
                            scoures[a][a] += 1
                elif i + j == 2:
                    for a in range(3):
                        if map[a][2-a] == ' ':
                            scoures[a][2-a] += 1
    return scoures


def breakOtherWin(map: List[List[str]]):
    scoures = [
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
    ]
    for i in range(3):
        for j in range(3):
            if map[i][j] != ' ':
                scoures[i][j] = -10
            if map[i][j] == 'O':
                for a in range(3):
                    if map[i][a] == ' ':
                        scoures[i][a] += 1
                    if map[a][j] == ' ':
                        scoures[a][j] += 1
                if i == j:
                    for a in range(3):
                        if map[a][a] == ' ':
                            scoures[a][a] += 1
                elif i + j == 2:
                    for a in range(3):
                        if map[a][2-a] == ' ':
                            scoures[a][2-a] += 1
    return scoures


def getPutSolt(map: List[List[str]]) -> Tuple[int, int]:
    return choiceTop(mapAdd(makeSelfWin(map), breakOtherWin(map)))


def doUpdate(map: List[List[str]]) -> Tuple[str, Union[List[List[str]], None]]:
    s = ifWin(map)
    if s != ' ':
        return s, map
    x, y = getPutSolt(map)
    map[x][y] = 'X'
    s = ifWin(map)
    if s != ' ':
        return s, map
    return ' ', map


def printMap(map: List[List[str]]):
    a, b, c = map[0]
    d, e, f = map[1]
    g, h, i = map[2]
    '''
    /-----1---2---3-\\
    | 1 |{a}|{b}|{c}|
    '''
    print(f'/----1-2-3\\')
    print(f'| 1 |{a}|{b}|{c}|')
    print(f'| 2 |{d}|{e}|{f}|')
    print(f'| 3 |{g}|{h}|{i}|')
    print(f'\\---------/')


def main():
    map = [
        [' ', ' ', ' '],
        [' ', ' ', ' '],
        [' ', ' ', ' '],
    ]
    printMap(map)
    while True:
        x, y = [int(i)-1 for i in input('输入位置(空格分隔): ').split(' ')]
        map[x][y] = 'O'
        win, newMap = doUpdate(map)
        printMap(newMap)
        if win != ' ':
            print(f'"{win}" 胜利!')
            break
        map = newMap

main()

rui3464784

厉害了，到时候试下

CreatorHusky

感谢分享

Sealsclerk

这是告诉机器人两方所有获胜的可能性然后让机器人来找到最优解的模式吗，感觉很有意思，要试一试

heigeer

大佬你好，我下载你的编解码url失效了，能重新发一个吗？