Fun little AI bot that plays TicTacToe.
In this fun project, the goal was to apply my understanding of Machine Learning to build a TicTacToe player. The learning problem was defined based on Tom Mitchell’s example learning problem of a checkers learning algorithm in his textbook.
Setup
Task T: playing TicTacToe
Performance Measure P: Percentage of games won against humans
Experience E: Indirect feedback via solution trace generated from games played against itself
Learning from Experience
The target function (V) was chosen to be a linear function that maps a given board state to a real value (score). We then use an approximation algorithm Least Mean Squares to learn the target function from the solution trace.
Learning
V(board_state) = R, (score for a given board state)
V_hat(board_state) = (w.T)*X (product of weights and corresponding feature values)
The score (R) for each non-final board state isi assigned with the estimated score of the successor board state:
V(board_state) = V_hat(successor(board_state))
V(final_board_state) = 100 (win)
0 (draw)
-100 (loss)
Sample Game
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
|
print("Let the game begin : ")
play(size)
Let the game begin :
Computer's turn :
--------------------
| - || - || - || X |
--------------------
| - || - || - || - |
--------------------
| - || - || - || - |
--------------------
| - || - || - || - |
--------------------
Human's move :
Enter x coordinate : 0
Enter y coordinate : 0
--------------------
| O || - || - || X |
--------------------
| - || - || - || - |
--------------------
| - || - || - || - |
--------------------
| - || - || - || - |
--------------------
Computer's turn :
--------------------
| O || - || - || X |
--------------------
| X || - || - || - |
--------------------
| - || - || - || - |
--------------------
| - || - || - || - |
--------------------
Human's move :
Enter x coordinate : 3
Enter y coordinate : 1
--------------------
| O || - || - || X |
--------------------
| X || - || - || - |
--------------------
| - || - || - || - |
--------------------
| - || O || - || - |
--------------------
Computer's turn :
--------------------
| O || - || - || X |
--------------------
| X || X || - || - |
--------------------
| - || - || - || - |
--------------------
| - || O || - || - |
--------------------
Human's move :
Enter x coordinate : 3
Enter y coordinate : 2
--------------------
| O || - || - || X |
--------------------
| X || X || - || - |
--------------------
| - || - || - || - |
--------------------
| - || O || O || - |
--------------------
Computer's turn :
--------------------
| O || - || - || X |
--------------------
| X || X || X || - |
--------------------
| - || - || - || - |
--------------------
| - || O || O || - |
--------------------
Human's move :
Enter x coordinate : 3
Enter y coordinate : 3
--------------------
| O || - || - || X |
--------------------
| X || X || X || - |
--------------------
| - || - || - || - |
--------------------
| - || O || O || O |
--------------------
Computer's turn :
--------------------
| O || - || - || X |
--------------------
| X || X || X || - |
--------------------
| - || - || - || - |
--------------------
| X || O || O || O |
--------------------
Human's move :
Enter x coordinate : 2
Enter y coordinate : 1
--------------------
| O || - || - || X |
--------------------
| X || X || X || - |
--------------------
| - || O || - || - |
--------------------
| X || O || O || O |
--------------------
Computer's turn :
--------------------
| O || - || - || X |
--------------------
| X || X || X || X |
--------------------
| - || O || - || - |
--------------------
| X || O || O || O |
--------------------
Computer Wins!
|
