Python实现人工智能博弈树一字棋算法

发表于   |   分类于   |  

前言

虽然大三的时候人工智能课上就讲过一字棋算法，可是当时偷了个懒糊弄过去了，没想到到了研一还是要写。

正文

博弈树，它是一种特殊的与或图。节点代表博弈的格局（即棋局），相当于状态空间中的状态，反映了博弈的信息。 与节点、或节点隔层交替出现。
假设博弈双方为：MAX和MIN
在博弈过程中，规则是双方轮流走步。在博弈树中，相当于博弈双方轮流扩展其所属节点：

从MIN方的角度来看：所有MIN方节点都是与节点
因为MIN方必定选择最不利于MAX方的方式来扩展节点，只要MIN方节点的子节点中有一个对MAX方不利，则该节点就对MAX方不利，故为“与节点”

从MAX方的角度来看：所有属于MAX方的节点都是“或节点”
因为扩展MAX方节点时，MAX方可选择扩展最有利于自己的节点，只要可扩展的子节点中有一个对已有利， 则该节点就对已有利

核心算法解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ComputerMove(broad, computerLetter):     // 机器人走
    if(FreeList(broad) == []):               //如果没空格子，则说明平手
        print("tie !!!")
        return 'T'
    print("***in ComputerMove() ***")
    if(WillWin(broad,computerLetter)!=0):          //遍历所有空格，看走一步能不能直接获胜
        broad[WillWin(broad,computerLetter)]=computerLetter
        print("computer win")
        return computerLetter
    elif(WillWin(broad,NextPlay(computerLetter)!=0)):      //看对手走一步能不能直接赢，若能，则抢占这一格
        broad[WillWin(broad,NextPlay(computerLetter))]=computerLetter
    else:            //使用博弈的算法
        dic={}
        for i in FreeList(broad):              //遍历所有情况
            broadTemp=BoardTemp(broad)
            broadTemp[i]=computerLetter
            temp=getValue(broadTemp,NextPlay(computerLetter))    获取每一种情况估价函数的值
            dic[temp]=i 
        key=sorted(dic)
        index=dic[key[-1]]            //取估价函数最大的值，move
        broad[index]=computerLetter
    drawBroad(broad)

代码

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
# -*- coding: utf-8 -*-
"""
Created on Wed Nov  2 10:12:03 2016
@author: Fuck
"""
def drawBroad(broad):
    print('-----------')
    print(' '+broad[1]+' | '+broad[2]+' | '+broad[3])
    print('-----------')
    print(' '+broad[4]+' | '+broad[5]+' | '+broad[6])
    print('-----------')
    print(' '+broad[7]+' | '+broad[8]+' | '+broad[9])
    print('-----------')
    
 
def chooseLetter():
    print('before the game ,please choose the letter "X" or "O"("X will be first"): ')
    letter = input().strip().upper()[0]
    print("you choose :"+letter)
    if (letter == 'X'):
        return 'X'
    elif (letter == 'O'):
        return 'O'
    else:   
        chooseLetter()
 
//if has win return letter
//else return N
def checkWin(broad,letter):
    if ((broad[1] ==letter and broad[2] ==letter and broad[3] ==letter )
    or (broad[4] ==letter and broad[5] ==letter and broad[6] ==letter )
    or (broad[7] ==letter and broad[8] ==letter and broad[9] ==letter )
     
    or (broad[1] ==letter and broad[4] ==letter and broad[7] ==letter )
    or (broad[2] ==letter and broad[5] ==letter and broad[8] ==letter )
    or (broad[3] ==letter and broad[6] ==letter and broad[9] ==letter )
     
    or (broad[7] ==letter and broad[5] ==letter and broad[3] ==letter )
    or (broad[1] ==letter and broad[5] ==letter and broad[9] ==letter )
    ):
        return letter
    else:
        return 'N'
 
def hasLetter(broad,location):
    return broad[location] != ' '
 
//return freeList
def FreeList(broad):
    freeList=[]
    for i in range(1,10):
        if(not hasLetter(broad,i)):
            freeList.append(i)
    return freeList
def PlayerMove (broad,letter):
    if(FreeList(broad) == []):
        print("tie !!!")
        return 'T'
    playlocation = int(input("your turn:").strip()[0])
    print("***in PlayerMove() ***")
    #if (playlocation  in list(range(1,10))and not hasLetter(broad,playlocation)):
    if(playlocation in FreeList(broad)):
        broad[playlocation] = letter
        drawBroad(broad)
        if(checkWin(broad,letter)!= 'N'):
            print("you win")
            return letter
    else:
        PlayerMove(broad,letter)
        
def NextPlay(letter):
    if(letter == 'X'):
        return 'O'
    else:
        return 'X'
 
def ComputerMove(broad, computerLetter):
    if(FreeList(broad) == []):
        print("tie !!!")
        return 'T'
    print("***in ComputerMove() ***")
    if(WillWin(broad,computerLetter)!=0):
        broad[WillWin(broad,computerLetter)]=computerLetter
        print("computer win")
        return computerLetter
    elif(WillWin(broad,NextPlay(computerLetter)!=0)):
        broad[WillWin(broad,NextPlay(computerLetter))]=computerLetter
    else:
        dic={}
        for i in FreeList(broad):
            broadTemp=BoardTemp(broad)
            broadTemp[i]=computerLetter
            temp=getValue(broadTemp,NextPlay(computerLetter))
            dic[temp]=i 
        key=sorted(dic)
        index=dic[key[-1]]
        broad[index]=computerLetter
    drawBroad(broad)
    
def getValue(broad,letter):
    ls=[]
    for i in FreeList(broad):
        broadTemp=BoardTemp(broad) 
        broadTemp[i]=letter
        temp=countRowAndCol(broadTemp,NextPlay(letter))-countRowAndCol(broadTemp,letter)
        ls.append(temp)
    ls.sort()
    return ls[0]
    
def countRowAndCol(broad,letter):
    for i in FreeList(broad):
        broad[i]=letter
    count=0
    if (broad[1] ==letter and broad[2] ==letter and broad[3] ==letter ):
        count+=1
    if (broad[4] ==letter and broad[5] ==letter and broad[6] ==letter ):
        count+=1
    if (broad[7] ==letter and broad[8] ==letter and broad[9] ==letter ):
        count+=1
    if (broad[1] ==letter and broad[4] ==letter and broad[7] ==letter ):
        count+=1
    if (broad[2] ==letter and broad[5] ==letter and broad[8] ==letter ):
        count+=1
    if (broad[3] ==letter and broad[6] ==letter and broad[9] ==letter ):
        count+=1
    if (broad[7] ==letter and broad[5] ==letter and broad[3] ==letter ):
        count+=1
    if (broad[1] ==letter and broad[5] ==letter and broad[9] ==letter ):
        count+=1
    return count
   
 
//copy board
def BoardTemp(board):
    boardTemp = {}
    for i in range(1,10):
        boardTemp[i] = board[i]
    return boardTemp
 
def WillWin(board, Letter):
    boardTemp=BoardTemp(board)
    for i in FreeList(board):
        boardTemp[i]=Letter
        if(checkWin(boardTemp,Letter) != 'N'):
            #drawBroad(boardTemp)
            return i
        else:
            boardTemp[i]=" "
    return 0
 
def GameInit():
    broad = {}
    for i in range(1,10):
        broad[i]=' '
    drawBroad(broad)
    return broad 
 
def GameBody(board,letter):
    templetter=letter
    rs = ''
    while(True):
        rs = ComputerMove(board, templetter)
        if(rs is not None):
            break
        templetter = NextPlay(templetter)
        rs = PlayerMove(board,templetter)
        if(rs is not None):
            break
        templetter = NextPlay(templetter)
    return rs
     
def GameStart():
    broad = GameInit()
    playerletter = chooseLetter()
     
    if(playerletter == 'X'):
        PlayerMove(broad,playerletter)       
    rs = GameBody(broad,NextPlay(playerletter))
    print("the winner is:"+rs)
   
GameStart()

成果






后记

  1. 很遗憾还停留在命令行阶段，想实现界面的，最后没能成功。
  1. 写出来的电脑还是有点厉害的，如果让它先手，第一步总知道抢我中间5的位置，我就很被动。