• alpha-beta剪枝

    井字棋

    井字棋（tic-tac-toe）

    经过旋转，翻转操作进行去重后，
    有91个局面X赢
    有44个局面O赢
    有3个局面平局

    #!/usr/bin/env python
# _*_ coding:utf-8 _*_
from copy import deepcopy

HEIGHT = 3
WIDTH = 3
X_CHESS = 1
O_CHESS = -1
EMPTY_CHESS = 0

board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]


def print_board(board):
    print('*' * 20)
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if X_CHESS == board[i][j]:
                print('X', end='')
            elif O_CHESS == board[i][j]:
                print('O', end='')
            else:
                print('_', end='')
        print()
    print('*' * 20)


def check_win(board, player):
    # row
    for i in range(HEIGHT):
        cnt = 0
        for j in range(WIDTH):
            cnt += (player == board[i][j])
        if 3 == cnt:
            return True
    # col
    for j in range(WIDTH):
        cnt = 0
        for i in range(HEIGHT):
            cnt += (player == board[i][j])
        if 3 == cnt:
            return True
    main_diagonal_cnt, sub_diagonal_cnt = 0, 0
    for i in range(HEIGHT):
        main_diagonal_cnt += (player == board[i][i])
        sub_diagonal_cnt += (player == board[i][WIDTH - i - 1])
    return 3 == main_diagonal_cnt or 3 == sub_diagonal_cnt


def get_state(board):
    state = 0
    for i in range(HEIGHT):
        for j in range(WIDTH):
            cur = board[i][j]
            if O_CHESS == board[i][j]:
                cur = 2
            state += cur * (3 ** (i * WIDTH + j))
    return state


def transpose(board):
    temp = deepcopy(board)
    # transpose
    for i in range(HEIGHT):
        for j in range(i):
            temp[i][j], temp[j][i] = temp[j][i], temp[i][j]
    return temp


def horizontal_flip(board):
    temp = deepcopy(board)
    for i in range(HEIGHT):
        j, k = 0, WIDTH - 1
        while j < k:
            temp[i][j], temp[i][k] = temp[i][k], temp[i][j]
            j += 1
            k -= 1
    return temp


def vertical_flip(board):
    temp = deepcopy(board)
    for j in range(WIDTH):
        i, k = 0, HEIGHT - 1
        while i < k:
            temp[i][j], temp[k][j] = temp[k][j], temp[i][j]
            i += 1
            k -= 1
    return temp


def rotate90(board):
    temp = deepcopy(board)
    return horizontal_flip(transpose(temp))


states = set()

x_win_cnt = 0
o_win_cnt = 0
draw = 0
open_cnt = 0


def get_equivalent_state(board):
    cur_state = get_state(board)
    temp = deepcopy(board)
    result = {cur_state}
    for _ in range(3):
        temp = rotate90(temp)
        result.add(get_state(temp))
    temp = horizontal_flip(temp)
    result.add(get_state(temp))
    for _ in range(3):
        temp = rotate90(temp)
        result.add(get_state(temp))
    return result


def traverse(board, cur_player, depth, states):
    # x_win_cnt=626, o_win_cnt=316, draw=16, open_cnt=4536
    # x_win_cnt=91, o_win_cnt=44, draw=3, open_cnt=630
    global open_cnt
    open_cnt += 1

    moves = []
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if EMPTY_CHESS == board[i][j]:
                moves.append((i, j))
    if 0 == len(moves):
        print_board(board)
        global draw
        draw += 1
        return
    for i, j in moves:
        board[i][j] = cur_player
        cur_state = get_state(board)
        flag = cur_state not in states
        if flag:
            states.update(get_equivalent_state(board))
        else:
            board[i][j] = EMPTY_CHESS
            continue
        states.add(cur_state)
        if check_win(board, cur_player):
            print_board(board)
            board[i][j] = EMPTY_CHESS
            if cur_player == X_CHESS:
                global x_win_cnt
                x_win_cnt += 1
            else:
                global o_win_cnt
                o_win_cnt += 1
            continue
        traverse(board, -cur_player, depth + 1, states)

        board[i][j] = EMPTY_CHESS



if __name__ == '__main__':
    traverse(board, X_CHESS, 0, set())
    print(x_win_cnt, o_win_cnt, draw, open_cnt)


    • 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
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165

    Min-Max算法/Negamax算法

    假设这是一个零和博弈

    自己总是回选择最好的局面，但是对手总是会选择最不利于我们的局面
    然后利用回溯，找到下一步最好的局面
    如下图（来自wiki）
    在这里插入图片描述
    伪代码如下（来自wiki）

    function  minimax( node, depth, maximizingPlayer ) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min( value, minimax( child, depth − 1, TRUE ) )
        return value

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    当然这样比较麻烦，可以化简一下

    function  negamax( node, depth, maximizingPlayer ) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    value := −∞
    for each child of node do
        value := max(value, -minimax(child, depth − 1, not maximizingPlayer))
    return value

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    可以大概感受一下
    在这里插入图片描述
    这里胜利局面返回的 11 − d e p t h 11-depth 11−depth,简单来说，越快赢，分数越大，平局返回0，输了返回 − ( 11 − d e p t h ) -\left(11-depth\right) −(11−depth) (因为判断赢写在了下一层，所以 1 ≤ d e p t h ≤ 10 1\le depth\le 10 1≤depth≤10为了保证正数，所以写了 11 11 11)

    #!/usr/bin/env python
# _*_ coding:utf-8 _*_
from copy import deepcopy

HEIGHT = 3
WIDTH = 3
X_CHESS = 1
O_CHESS = -1
EMPTY_CHESS = 0
INF = 0x7fffffff


def print_board(board):
    print('*' * 20)
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if X_CHESS == board[i][j]:
                print('X', end='')
            elif O_CHESS == board[i][j]:
                print('O', end='')
            else:
                print('_', end='')
        print()
    print('*' * 20)


def check_win(board, player):
    # row
    for i in range(HEIGHT):
        cnt = 0
        for j in range(WIDTH):
            cnt += (player == board[i][j])
        if 3 == cnt:
            return True
    # col
    for j in range(WIDTH):
        cnt = 0
        for i in range(HEIGHT):
            cnt += (player == board[i][j])
        if 3 == cnt:
            return True
    main_diagonal_cnt, sub_diagonal_cnt = 0, 0
    for i in range(HEIGHT):
        main_diagonal_cnt += (player == board[i][i])
        sub_diagonal_cnt += (player == board[i][WIDTH - i - 1])
    return 3 == main_diagonal_cnt or 3 == sub_diagonal_cnt


def get_state(board):
    state = 0
    for i in range(HEIGHT):
        for j in range(WIDTH):
            cur = board[i][j]
            if O_CHESS == board[i][j]:
                cur = 2
            state += cur * (3 ** (i * WIDTH + j))
    return state


def transpose(board):
    temp = deepcopy(board)
    # transpose
    for i in range(HEIGHT):
        for j in range(i):
            temp[i][j], temp[j][i] = temp[j][i], temp[i][j]
    return temp


def horizontal_flip(board):
    temp = deepcopy(board)
    for i in range(HEIGHT):
        j, k = 0, WIDTH - 1
        while j < k:
            temp[i][j], temp[i][k] = temp[i][k], temp[i][j]
            j += 1
            k -= 1
    return temp


def vertical_flip(board):
    temp = deepcopy(board)
    for j in range(WIDTH):
        i, k = 0, HEIGHT - 1
        while i < k:
            temp[i][j], temp[k][j] = temp[k][j], temp[i][j]
            i += 1
            k -= 1
    return temp


def rotate90(board):
    temp = deepcopy(board)
    return horizontal_flip(transpose(temp))


x_win_cnt = 0
o_win_cnt = 0
draw = 0
open_cnt = 0


def get_equivalent_state(board):
    cur_state = get_state(board)
    temp = deepcopy(board)
    result = {cur_state}
    for _ in range(3):
        temp = rotate90(temp)
        result.add(get_state(temp))
    temp = horizontal_flip(temp)
    result.add(get_state(temp))
    for _ in range(3):
        temp = rotate90(temp)
        result.add(get_state(temp))
    return result


def traverse(board, cur_player, depth, states):
    # x_win_cnt=626, o_win_cnt=316, draw=16, open_cnt=4536
    # x_win_cnt=91, o_win_cnt=44, draw=3, open_cnt=630
    global open_cnt
    open_cnt += 1

    moves = []
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if EMPTY_CHESS == board[i][j]:
                moves.append((i, j))
    if 0 == len(moves):
        print_board(board)
        global draw
        draw += 1
        return
    for i, j in moves:
        board[i][j] = cur_player
        cur_state = get_state(board)
        flag = cur_state not in states
        if flag:
            states.update(get_equivalent_state(board))
        else:
            board[i][j] = EMPTY_CHESS
            continue
        states.add(cur_state)
        if check_win(board, cur_player):
            print_board(board)
            board[i][j] = EMPTY_CHESS
            if cur_player == X_CHESS:
                global x_win_cnt
                x_win_cnt += 1
            else:
                global o_win_cnt
                o_win_cnt += 1
            continue
        traverse(board, -cur_player, depth + 1, states)

        board[i][j] = EMPTY_CHESS


def min_max(board, cur_player, depth, states):
    if check_win(board, -cur_player):
        # return -INF + 1, None, None
        return -(HEIGHT * WIDTH + 2 - depth), None, None
    moves = []
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if EMPTY_CHESS == board[i][j]:
                moves.append((i, j))
    if 0 == len(moves):
        return 0, None, None
    best_val, best_i, best_j = -INF, -1, -1
    for i, j in moves:
        board[i][j] = cur_player
        cur_state = get_state(board)
        flag = cur_state not in states
        if flag:
            result = -min_max(board, -cur_player, depth + 1, states)[0]
            for equivalent_state in get_equivalent_state(board):
                states[equivalent_state] = -result
        else:
            result = -states[cur_state]
        board[i][j] = EMPTY_CHESS
        if result > best_val:
            best_val, best_i, best_j = result, i, j

    return best_val, best_i, best_j


def get_input(board):
    while True:
        try:
            i, j = map(int, input('position: (split by space)').strip().split())
            if 0 <= i < HEIGHT and 0 <= j < WIDTH and EMPTY_CHESS == board[i][j]:
                return i, j
            else:
                print('illegal input')
        except:
            print('illegal input')


def pvp():
    board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]
    cur_player = X_CHESS
    print_board(board)
    for _ in range(HEIGHT * WIDTH):
        print('*' * 20)
        if X_CHESS == cur_player:
            print('X turn')
        else:
            print('O turn')
        i, j = get_input(board)
        board[i][j] = cur_player
        print_board(board)
        if check_win(board, cur_player):
            if X_CHESS == cur_player:
                print('X win')
            else:
                print('O win')
            return
        else:
            cur_player = -cur_player
    print('draw')


def pve():
    a = input('choose X or O').strip()
    player = X_CHESS
    while True:
        if 'X' == a.upper():
            break
        elif 'O' == a.upper():
            player = O_CHESS
            break
        else:
            a = input('choose X or O').strip()
    board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]
    cur_player = X_CHESS
    print_board(board)
    for _ in range(HEIGHT * WIDTH):
        if X_CHESS == cur_player:
            print('X turn')
        else:
            print('O turn')
        if player == cur_player:
            i, j = get_input(board)
        else:
            _, i, j = min_max(board, cur_player, 0, {})
        board[i][j] = cur_player
        print_board(board)
        if check_win(board, cur_player):
            if X_CHESS == cur_player:
                print('X win')
            else:
                print('O win')
            return
        else:
            cur_player = -cur_player
    print('draw')


def traverse_ai(board, cur_player, ai_player, depth):
    moves = []
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if EMPTY_CHESS == board[i][j]:
                moves.append((i, j))
    if 0 == len(moves):
        print_board(board)
        global draw
        draw += 1
        return
    for i, j in moves:
        if cur_player == ai_player:
            _, i, j = min_max(board, cur_player, 0, {})
        board[i][j] = cur_player
        if check_win(board, cur_player):
            print_board(board)
            board[i][j] = EMPTY_CHESS
            if cur_player == X_CHESS:
                global x_win_cnt
                x_win_cnt += 1
            else:
                global o_win_cnt
                o_win_cnt += 1
            continue
        traverse_ai(board, -cur_player, ai_player, depth + 1)

        board[i][j] = EMPTY_CHESS


if __name__ == '__main__':
    # board = [
    #     [-1, 0, 1],
    #     [0, 1, 0],
    #     [0, 0, 0]
    # ]
    # print_board(board)
    # min_max(board, O_CHESS, 0, {})
    # print_board(board)
    # board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]
    # traverse_ai(board, X_CHESS, X_CHESS, 0)
    # print(f"x_win_cnt={x_win_cnt}, o_win_cnt={o_win_cnt}, draw={draw}")
    # traverse_ai(board, X_CHESS, O_CHESS, 0)
    # print(f"x_win_cnt={x_win_cnt}, o_win_cnt={o_win_cnt}, draw={draw}")
    # x_win_cnt=72765, o_win_cnt=0, draw=1890
    # x_win_cnt=41895, o_win_cnt=0, draw=1890
    # x_win_cnt = 0, o_win_cnt = 165888, draw = 70272
    # x_win_cnt = 0, o_win_cnt = 112128, draw = 70272

    a = input('pvp or pve').strip()
    pvp_flag = True
    while True:
        if 'pvp' == a:
            break
        elif 'pve' == a:
            pvp_flag = False
            break
        else:
            a = input('pvp or pve').strip()
    if pvp_flag:
        pvp()
    else:
        pve()


    • 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
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322

    alpha-beta剪枝

    alpha-beta剪枝（alpha-beta pruning）
    α \alpha α为max方（自己）能取到的最大值，初始值为 − ∞ -\infty −∞
    β \beta β为min方（对手）能取到最小值 + ∞ +\infty +∞
    在max的时候，是要更新 α \alpha α的，但是当 α ≥ β \alpha\ge\beta α≥β时，这个分支就可以剪掉了
    在min的时候，是要更新 β \beta β的，但是当 α ≥ β \alpha\ge\beta α≥β时，这个分支就可以剪掉了

    在这里插入图片描述
    比如这个图（来自wiki），第2层的第3个结点，从叶子返回了5，但是 5 ≤ 6 = α 5\le 6=\alpha 5≤6=α，第1层（max）有更好的选择（第2层第2个是6），他一定不会选择这个5；又因为第2层是min，后续的节点要想返回，只能比5小，但是同时也 ≤ α \le \alpha ≤α,所以后续的分支不用看了
    在这里插入图片描述
    同理（来自csdn），比如访问完K的时候，从叶子节点返回4，但是 4 ≥ 3 = β 4\ge 3=\beta 4≥3=β,而B有更好的选择(D），所以他一定不会选择这个4；又因为第3层是max，后续节点想返回，只能比4大，但是同时也 ≥ β \ge \beta ≥β,所以后续的分支不用看了

    伪代码（来自wiki）

    function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    也可以化简一下

    function negamax(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    value := −∞
    for each child of node do
        value := -max(value, alphabeta(child, depth − 1, -β, α, not maximizingPlayer))
        if value ≥ β then
            break (* β cutoff *)
        α := max(α, value)
    return value

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    这里与min-max不同，去重只去重一层，因为可能因为剪枝导致某个局面返回的值不对
    比如说有一个局面，有下一步就赢的策略，但是由于alpha-beta剪枝，导致返回了一个输了局面

    #!/usr/bin/env python
# _*_ coding:utf-8 _*_
from copy import deepcopy

HEIGHT = 3
WIDTH = 3
X_CHESS = 1
O_CHESS = -1
EMPTY_CHESS = 0
INF = 0x7fffffff


def print_board(board):
    print('*' * 20)
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if X_CHESS == board[i][j]:
                print('X', end='')
            elif O_CHESS == board[i][j]:
                print('O', end='')
            else:
                print('_', end='')
        print()
    print('*' * 20)


def check_win(board, player):
    # row
    for i in range(HEIGHT):
        cnt = 0
        for j in range(WIDTH):
            cnt += (player == board[i][j])
        if 3 == cnt:
            return True
    # col
    for j in range(WIDTH):
        cnt = 0
        for i in range(HEIGHT):
            cnt += (player == board[i][j])
        if 3 == cnt:
            return True
    main_diagonal_cnt, sub_diagonal_cnt = 0, 0
    for i in range(HEIGHT):
        main_diagonal_cnt += (player == board[i][i])
        sub_diagonal_cnt += (player == board[i][WIDTH - i - 1])
    return 3 == main_diagonal_cnt or 3 == sub_diagonal_cnt


def get_state(board):
    state = 0
    for i in range(HEIGHT):
        for j in range(WIDTH):
            cur = board[i][j]
            if O_CHESS == board[i][j]:
                cur = 2
            state += cur * (3 ** (i * WIDTH + j))
    return state


def state2board(state):
    board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]

    pos = HEIGHT * WIDTH - 1
    weight = 3 ** pos
    while weight > 0:
        i, j = pos // WIDTH, pos % WIDTH
        chess = state // weight
        if 2 == chess:
            board[i][j] = O_CHESS
        else:
            board[i][j] = chess
        pos -= 1
        weight //= 3
    return board


def transpose(board):
    temp = deepcopy(board)
    # transpose
    for i in range(HEIGHT):
        for j in range(i):
            temp[i][j], temp[j][i] = temp[j][i], temp[i][j]
    return temp


def horizontal_flip(board):
    temp = deepcopy(board)
    for i in range(HEIGHT):
        j, k = 0, WIDTH - 1
        while j < k:
            temp[i][j], temp[i][k] = temp[i][k], temp[i][j]
            j += 1
            k -= 1
    return temp


def vertical_flip(board):
    temp = deepcopy(board)
    for j in range(WIDTH):
        i, k = 0, HEIGHT - 1
        while i < k:
            temp[i][j], temp[k][j] = temp[k][j], temp[i][j]
            i += 1
            k -= 1
    return temp


def rotate90(board):
    temp = deepcopy(board)
    return horizontal_flip(transpose(temp))


x_win_cnt = 0
o_win_cnt = 0
draw = 0
open_cnt = 0


def get_equivalent_state(board):
    cur_state = get_state(board)
    temp = deepcopy(board)
    result = {cur_state}
    for _ in range(3):
        temp = rotate90(temp)
        result.add(get_state(temp))
    temp = horizontal_flip(temp)
    result.add(get_state(temp))
    for _ in range(3):
        temp = rotate90(temp)
        result.add(get_state(temp))
    return result


def traverse(board, cur_player, depth, states):
    # x_win_cnt=626, o_win_cnt=316, draw=16, open_cnt=4536
    # x_win_cnt=91, o_win_cnt=44, draw=3, open_cnt=630
    global open_cnt
    open_cnt += 1

    moves = []
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if EMPTY_CHESS == board[i][j]:
                moves.append((i, j))
    if 0 == len(moves):
        print_board(board)
        global draw
        draw += 1
        return
    for i, j in moves:
        board[i][j] = cur_player
        cur_state = get_state(board)
        flag = cur_state not in states
        if flag:
            states.update(get_equivalent_state(board))
        else:
            board[i][j] = EMPTY_CHESS
            continue
        states.add(cur_state)
        if check_win(board, cur_player):
            print_board(board)
            board[i][j] = EMPTY_CHESS
            if cur_player == X_CHESS:
                global x_win_cnt
                x_win_cnt += 1
            else:
                global o_win_cnt
                o_win_cnt += 1
            continue
        traverse(board, -cur_player, depth + 1, states)

        board[i][j] = EMPTY_CHESS


def alpha_beta_pruning(board, cur_player, depth, alpha, beta, states):
    if check_win(board, -cur_player):
        # return -INF + 1, None, None
        return -(HEIGHT * WIDTH + 2 - depth), None, None
    moves = []
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if EMPTY_CHESS == board[i][j]:
                moves.append((i, j))
    if 0 == len(moves):
        return 0, None, None
    best_val, best_i, best_j = -INF, -1, -1
    for i, j in moves:
        board[i][j] = cur_player
        cur_state = get_state(board)
        flag = cur_state not in states
        if flag:
            result = -alpha_beta_pruning(board, -cur_player, depth + 1, -beta, -alpha, {})[0]
            for equivalent_state in get_equivalent_state(board):
                states[equivalent_state] = -result
        else:
            result = -states[cur_state]
        if result > best_val:
            best_val, best_i, best_j = result, i, j
        board[i][j] = EMPTY_CHESS
        if result >= beta:
            break
        alpha = max(alpha, result)

    return best_val, best_i, best_j


def get_input(board):
    while True:
        try:
            i, j = map(int, input('position: (split by space)').strip().split())
            if 0 <= i < HEIGHT and 0 <= j < WIDTH and EMPTY_CHESS == board[i][j]:
                return i, j
            else:
                print('illegal input')
        except:
            print('illegal input')


def pvp():
    board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]
    cur_player = X_CHESS
    print_board(board)
    for _ in range(HEIGHT * WIDTH):
        print('*' * 20)
        if X_CHESS == cur_player:
            print('X turn')
        else:
            print('O turn')
        i, j = get_input(board)
        board[i][j] = cur_player
        print_board(board)
        if check_win(board, cur_player):
            if X_CHESS == cur_player:
                print('X win')
            else:
                print('O win')
            return
        else:
            cur_player = -cur_player
    print('draw')


def pve():
    a = input('choose X or O').strip()
    player = X_CHESS
    while True:
        if 'X' == a.upper():
            break
        elif 'O' == a.upper():
            player = O_CHESS
            break
        else:
            a = input('choose X or O').strip()
    board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]
    cur_player = X_CHESS
    print_board(board)
    for _ in range(HEIGHT * WIDTH):
        if X_CHESS == cur_player:
            print('X turn')
        else:
            print('O turn')
        if player == cur_player:
            i, j = get_input(board)
        else:
            _, i, j = alpha_beta_pruning(board, cur_player, 0, -INF, INF, {})
        board[i][j] = cur_player
        print_board(board)
        if check_win(board, cur_player):
            if X_CHESS == cur_player:
                print('X win')
            else:
                print('O win')
            return
        else:
            cur_player = -cur_player
    print('draw')


order = []


def traverse_ai(board, cur_player, ai_player, depth):
    moves = []
    for i in range(HEIGHT):
        for j in range(WIDTH):
            if EMPTY_CHESS == board[i][j]:
                moves.append((i, j))
    if 0 == len(moves):
        print_board(board)
        global draw
        draw += 1
        return
    for i, j in moves:
        if cur_player == ai_player:
            _, i, j = alpha_beta_pruning(board, cur_player, 0, -INF, INF, {})
        board[i][j] = cur_player
        order.append((i, j))
        if check_win(board, cur_player):
            print_board(board)
            board[i][j] = EMPTY_CHESS
            if cur_player == X_CHESS:
                global x_win_cnt
                x_win_cnt += 1
            else:
                global o_win_cnt
                o_win_cnt += 1
            if cur_player != ai_player:
                print(order)
                raise Exception('faQ')
            order.pop()
            continue
        traverse_ai(board, -cur_player, ai_player, depth + 1)

        board[i][j] = EMPTY_CHESS
        order.pop()


if __name__ == '__main__':
    # board = [
    #     [1, 0, 0],
    #     [0, 0, 0],
    #     [0, 0, 0]
    # ]
    # print_board(board)
    # _, i, j = alpha_beta_pruning(board, O_CHESS, 0, -INF, INF, {})
    # board[i][j] = O_CHESS
    # print_board(board)
    # board = [[EMPTY_CHESS for _ in range(WIDTH)] for _ in range(HEIGHT)]
    # traverse_ai(board, X_CHESS, X_CHESS, 0)
    # print(f"x_win_cnt={x_win_cnt}, o_win_cnt={o_win_cnt}, draw={draw}")
    # traverse_ai(board, X_CHESS, O_CHESS, 0)
    # print(f"x_win_cnt={x_win_cnt}, o_win_cnt={o_win_cnt}, draw={draw}")
    # x_win_cnt=72765, o_win_cnt=0, draw=1890
    # x_win_cnt=41895, o_win_cnt=0, draw=1890
    # x_win_cnt=41895, o_win_cnt=0, draw=1890
    # x_win_cnt=41895, o_win_cnt=0, draw=1890
    # x_win_cnt= 0, o_win_cnt=165888, draw=70272
    # x_win_cnt= 0, o_win_cnt=112128, draw=70272
    # x_win_cnt=0, o_win_cnt=112128, draw=70272

    a = input('pvp or pve').strip()
    pvp_flag = True
    while True:
        if 'pvp' == a:
            break
        elif 'pve' == a:
            pvp_flag = False
            break
        else:
            a = input('pvp or pve').strip()
    if pvp_flag:
        pvp()
    else:
        pve()


    • 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
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
  • 相关阅读:
    Hive基础（DML 数据操作）
    探索未来的视觉革命：卷积神经网络的崭新时代（一）
    Go并发：使用sync.Pool来性能优化
    学习python中的数据结构
    petite-vue源码剖析-逐行解读@vue-reactivity之Map和Set的reactive
    VMWare Ubuntu压缩虚拟磁盘
    【论文精读】The Missing Link: Finding label relations across datasets
    Java开发实习面试总结（49分钟）
    循序渐进介绍基于CommunityToolkit.Mvvm 和HandyControl的WPF应用端开发(1)
    Windows平台下将exe及其dll封包到新的exe
  • 原文地址：https://blog.csdn.net/qq_39942341/article/details/126452260