井字棋

ZhKQYu

from copy import deepcopy

class Board:
    def __init__(self):
        self.state = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
        self.flag = 0

    def __str__(self):
        new_lst = deepcopy(self.state)
        for i in range(len(new_lst)):
            for j in range(len(new_lst[i])):
                if new_lst[i][j] == 0:
                    new_lst[i][j] = "-"
                elif new_lst[i][j] == 1:
                    new_lst[i][j] = "X"
                else:
                    new_lst[i][j] = "O"
        string = "{:^5}|{:^5}|{:^5}\n{:_^5}|{:_^5}|{:_^5}\n{:^5}|{:^5}|{:^5}\n{:^5}|{:^5}|{:^5}\n{:_^5}|{:_^5}|{:_^5}\n{:^5}|{:^5}|{:^5}\n{:^5}|{:^5}|{:^5}\n{:^5}|{:^5}|{:^5}\n"
        return string.format(*new_lst[0], "_", "_", "_", " ", " ", " ", *new_lst[1], "_", "_", "_", " ", " ", " ", *new_lst[2], " ", " ", " ")

    def reset(self):
        self.state = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
        self.flag = 0  # 采用法一的时候必须将flag置为0

    @property
    def is_valid(self):
        count_X = 0
        count_O = 0
        if len(self.state) != 3:
            return False
        for line in self.state:
            if len(line) != 3:
                return False
            if not(isinstance(line[0], int) and isinstance(line[1], int) and isinstance(line[2], int) and line[0] in [0, 1, 2] and line[1] in [0, 1, 2] and line[2] in [0, 1, 2]):
                return False
            for each in line:
                if each == 1:
                    count_X += 1
                elif each == 2:
                    count_O += 1
        if abs(count_X - count_O) > 1:
            return False
        return True

    @property
    def round(self):
        count = 0
        for line in self.state:
            for each in line:
                if each != 0:
                    count += 1

        return count

    def __getitem__(self, key):
        return self.state[key.row][key.col]

    def __setitem__(self, key, value):
        if self.state[key.row][key.col] != 0:
            raise ValueError
        # 交替添加就叫一致或者连续
        # 法一
        if value == 1 and self.flag != -1:
            self.state[key.row][key.col] = value
            self.flag = -1
        elif value == 2 and self.flag != 1:
            self.state[key.row][key.col] = value
            self.flag = 1
        else:
            raise ValueError
        # 法二
        # 如果在添加之后，棋盘不合法，则valueerror
         

    @property
    def winner(self):
        # 横竖
        for i in range(3):
            if self.state[i][0] == self.state[i][1] == self.state[i][2] and self.state[i][0] != 0:
                return self.state[i][0]
            elif self.state[0][i] == self.state[1][i] == self.state[2][i] and self.state[0][i] != 0:
                return self.state[0][i]
        # 对角线
        if self.state[0][0] == self.state[1][1] == self.state[2][2] and self.state[0][0] != 0:
            return self.state[0][0]
        # 副对角线
        elif self.state[0][2] == self.state[1][1] == self.state[2][0] and self.state[0][2] != 0:
            return self.state[0][2]
        return 0

    @property
    def is_finished(self):
        if self.winner == True or self.round == 9:
            return True
        
            

class Position:
    def __init__(self, row, col):
        if row in [0, 1, 2] and col in [0, 1, 2]:
            self.row = row
            self.col = col
        else:
            raise ValueError

import random
# 井字棋核心算法
class Agent:
    def make_move(self, board):
        iswin = self.get_win_or_lost(board, 1)
        # 如果自己能赢直接赢
        if iswin != None:
            return iswin
        islost = self.get_win_or_lost(board, 2)
        # 如果对方能赢则堵住
        if islost != None:
            return islost
        # 预判一下自己能否必胜
        will_win = self.I_will_win_or_lost(board, 1)
        if will_win != None:
            return will_win
        # 预判一下自己是否必输
        will_lost = self.I_will_win_or_lost(board, 2)
        if will_lost != None:
            return will_lost
        # 如果中间位置没有棋子则下在中间，因为放在中间赢得概率最大
        if board[Position(1, 1)] == 0:
            return Position(1, 1)
        if board.round == 1:
            # 当别人先手时，如果中间位置被占，那么就在(0, 0)下子
            if board[Position(1, 1)] != 0:
                return Position(0, 0)
        # 其他情况随机放子，基本不影响赢的概率
        row = random.randint(0, 2)
        col = random.randint(0, 2)
        while board[Position(row, col)] != 0:
            row = random.randint(0, 2)
            col = random.randint(0, 2)
        return Position(row, col)

    # 去试一试自己要赢还是要输
    def get_win_or_lost(self, board, player):
        empty_position = []
        for i in range(3):
            for j in range(3):
                if board[Position(i, j)] == 0:
                    empty_position.append(Position(i, j))
        for each in empty_position:
            board.state[each.row][each.col] = player
            if board.winner == player:
                board.state[each.row][each.col] = 0
                return each
            board.state[each.row][each.col] = 0

    def I_will_win_or_lost(self, board, player):
        empty_position = []
        for i in range(3):
            for j in range(3):
                if board[Position(i, j)] == 0:
                    empty_position.append(Position(i, j))
        for each in empty_position:
            board.state[each.row][each.col] = player
            if self.get_win_lost_count(board, player) > 1:
                board.state[each.row][each.col] = 0
                return each
            board.state[each.row][each.col] = 0

    def get_win_lost_count(self, board, player):
        empty_position = []
        for i in range(3):
            for j in range(3):
                if board[Position(i, j)] == 0:
                    empty_position.append(Position(i, j))
        count = 0
        for each in empty_position:
            board.state[each.row][each.col] = player
            if board.winner == player:
                board.state[each.row][each.col] = 0
                count += 1
            board.state[each.row][each.col] = 0
        return count



count_a = 0
count_b = 0

agent1 = Agent()
# agent2 = Agent()

# 完全随机下棋的玩家
class agent_random:
    def make_move(self, board):
        row = random.randint(0, 2)
        col = random.randint(0, 2)
        while board[Position(row, col)] != 0:
            row = random.randint(0, 2)
            col = random.randint(0, 2)
        return Position(row, col)

agent2 = agent_random()

board = Board()
# 先手一定不会输
# for i in range(5000):
#     while board.winner == 0:
#         board[agent1.make_move(board)] = 1
#         if board.winner != 0:
#             # print("agent1 win")
#             # print(board)
#             count_a += 1
#             break
#         if board.is_finished:
#             break
#         board[agent2.make_move(board)] = 2
#         if board.winner != 0:
#             print("agent2 win")
#             print(board)
#             count_b += 1
#             break
#         if board.is_finished:
#             break
#     board.reset()
#     board.flag = 0
#     # print("Finished %s times" % (i+1))

# 后手获胜概率很大
for j in range(5000):
    while board.winner == 0:
        board[agent2.make_move(board)] = 1
        if board.winner != 0:
            print("agent2 win")
            print(board)
            count_b += 1
            break
        if board.is_finished:
            break
        board[agent1.make_move(board)] = 2
        if board.winner != 0:
            # print("agent1 win")
            # print(board)
            count_a += 1
            break
        if board.is_finished:
            break
    board.reset()
    board.flag = 0

print(count_a, count_b)

代码太臃肿了
时间复杂度还是比较高的
不过好在还是可以跑起来
测试了5000次
先手的话应该是必胜
后手获胜概率也很大
记录一下

繁宇宙

好厉害的样子，good

ZhKQYu

人机对战，人类输入想要下子的位置，比如输入0 0，代表在左上角下子，其他情况类似

board = Board()

agent = Agent()
# 机器先手
# while True:
#     board[agent.make_move(board)] = 1
#     print(board)
#     if board.winner != 0:
#         break
#     if board.is_finished:
#         break
#     while True:
#         try:
#             board[Position(*[int(each) for each in input("Please input the position : ").split()])] = 2
#             break
#         except:
#             pass
#     print(board)
#     if board.winner != 0:
#         break
#     if board.is_finished:
#         break
# board.reset()
# board.flag = 0

# 玩家先手，有必胜的策略
# 玩家先放(0, 0)，机器会放在中间,玩家放在(2, 2),机器会放在(0, 2),玩家放在(2, 0)，人类获胜
while True:
    while True:
        try:
            board[Position(*[int(each) for each in input("Please input the position : ").split()])] = 2
            break
        except:
            pass
    
    print(board)
    if board.winner != 0:
        break
    if board.is_finished:
        break
    board[agent.make_move(board)] = 1
    print(board)
    if board.winner != 0:
        break
    if board.is_finished:
        break
board.reset()
board.flag = 0