heuristic_analysis.tex

\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amssymb,amsfonts,longtable}
\pagestyle{empty}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\setlength{\topmargin}{-2.0cm}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{24.5cm}
\setlength{\parindent}{0cm}
\setlength{\parskip}{0.1cm}

\begin{document}
\begin{center}
{\bf Analysis of three different evaluation heuristics }\\
\end{center}
In this project, three custom evaluation functions were implemented. The details of implementation and performance of each custom evaluation function are decribed 
below.\\

{\bf Evalation function one}\\
The first evaluation function is implemented as \texttt{custom\_score1} in \texttt{game\_agent.py}. For any board state it returns the difference in the weighted sum of the number of moves available to the first player (max player) and the weighted sum of the number of moves available to the second player (min player). For each player and each move, the weight of each move is defined to be the number of ``legal" moves the player has after making that move.\\

Table~\ref{eval_fun1_overall} shows the overall performance, over 100 tournaments, using this custom evaluation function. Evaluation function one has a higher win percentage compared to Id\_improved 71\% of the time. Table~\ref{eval_fun1} shows the performance against the seven pre-implemented evaluation functions. 

\begin{longtable}[c]{| c | c |c |}
 \caption{Overall Performance Using Evaluation Function One\label{eval_fun1_overall}}\\
 \hline
 %\multicolumn{2}{| c |}{Begin of Table}\\
 \hline
 Tournament Number & Id\_Improved win \% & Agent using evaluation function one win \% \\
 \hline
 \endfirsthead
 
 \hline
 \multicolumn{2}{|c|}{Continuation of Table \ref{eval_fun1_overall}}\\ 
 \hline
 Tournament Number & Id\_Improved win \% & Agent using evaluation function one win \% \\
 \hline
 \endhead
 
 \hline
 \endfoot
 
 \hline
 %\multicolumn{2}{| c |}{End of Table}\\
 \hline\hline
 \endlastfoot
1 & 62.14 & 65.00 \\ \hline
2 & 67.14 & 65.00 \\ \hline
3 & 63.57 & 60.00 \\ \hline
4 & 66.43 & 73.57 \\ \hline
5 & 62.14 & 67.86 \\ \hline
6 & 60.00 & 63.57 \\ \hline
7 & 64.29 & 63.57 \\ \hline
8 & 63.57 & 65.71 \\ \hline
9 & 65.71 & 67.14 \\ \hline
10 & 61.43 & 60.71 \\ \hline
11 & 58.57 & 75.00 \\ \hline
12 & 70.00 & 65.71 \\ \hline
13 & 63.57 & 70.00 \\ \hline
14 & 67.86 & 67.14 \\ \hline
15 & 61.43 & 65.71 \\ \hline
16 & 66.43 & 65.00 \\ \hline
17 & 65.71 & 70.71 \\ \hline
18 & 61.43 & 64.29 \\ \hline
19 & 68.57 & 65.00 \\ \hline
20 & 59.29 & 64.29 \\ \hline
21 & 67.14 & 68.57 \\ \hline
22 & 65.71 & 67.14 \\ \hline
23 & 64.29 & 63.57 \\ \hline
24 & 62.86 & 65.00 \\ \hline
25 & 64.29 & 67.14 \\ \hline
26 & 70.71 & 59.29 \\ \hline
27 & 67.14 & 65.00 \\ \hline
28 & 64.29 & 72.14 \\ \hline
29 & 61.43 & 67.14 \\ \hline
30 & 65.00 & 68.57 \\ \hline
31 & 60.71 & 64.29 \\ \hline
32 & 63.57 & 72.86 \\ \hline
33 & 64.29 & 70.71 \\ \hline
34 & 65.00 & 64.29 \\ \hline
35 & 60.00 & 66.43 \\ \hline
36 & 67.86 & 69.29 \\ \hline
37 & 60.71 & 65.71 \\ \hline
38 & 65.00 & 67.86 \\ \hline
39 & 62.86 & 63.57 \\ \hline
40 & 60.71 & 67.86 \\ \hline
41 & 64.29 & 72.14 \\ \hline
42 & 69.29 & 60.71 \\ \hline
43 & 60.71 & 62.14 \\ \hline
44 & 67.14 & 70.00 \\ \hline
45 & 60.71 & 69.29 \\ \hline
46 & 64.29 & 67.14 \\ \hline
47 & 62.14 & 65.00 \\ \hline
48 & 58.57 & 66.43 \\ \hline
49 & 65.00 & 72.14 \\ \hline
50 & 67.14 & 65.71 \\ \hline
51 & 60.00 & 68.57 \\ \hline
52 & 66.43 & 68.57 \\ \hline
53 & 63.57 & 67.86 \\ \hline
54 & 61.43 & 65.00 \\ \hline
55 & 60.71 & 65.71 \\ \hline
56 & 65.00 & 67.14 \\ \hline
57 & 62.86 & 65.71 \\ \hline
58 & 60.71 & 63.57 \\ \hline
59 & 64.29 & 70.00 \\ \hline
60 & 61.43 & 64.29 \\ \hline
61 & 63.57 & 64.29 \\ \hline
62 & 61.43 & 70.00 \\ \hline
63 & 65.00 & 71.43 \\ \hline
64 & 62.86 & 68.57 \\ \hline
65 & 66.43 & 67.86 \\ \hline
66 & 67.14 & 64.29 \\ \hline
67 & 63.57 & 71.43 \\ \hline
68 & 64.29 & 70.00 \\ \hline
69 & 65.00 & 70.71 \\ \hline
70 & 65.71 & 70.71 \\ \hline
71 & 63.57 & 63.57 \\ \hline
72 & 62.86 & 62.86 \\ \hline
73 & 68.57 & 61.43 \\ \hline
74 & 66.43 & 65.00 \\ \hline
75 & 66.43 & 68.57 \\ \hline
76 & 65.71 & 67.14 \\ \hline
77 & 63.57 & 63.57 \\ \hline
78 & 67.86 & 68.57 \\ \hline
79 & 59.29 & 67.14 \\ \hline
80 & 67.14 & 72.86 \\ \hline
81 & 61.43 & 64.29 \\ \hline
82 & 66.43 & 63.57 \\ \hline
83 & 65.00 & 62.86 \\ \hline
84 & 63.57 & 64.29 \\ \hline
85 & 63.57 & 62.86 \\ \hline
86 & 64.29 & 70.00 \\ \hline
87 & 59.29 & 74.29 \\ \hline
88 & 64.29 & 62.14 \\ \hline
89 & 60.00 & 67.14 \\ \hline
90 & 62.86 & 63.57 \\ \hline
91 & 68.57 & 67.86 \\ \hline
92 & 62.86 & 62.86 \\ \hline
93 & 62.86 & 65.00 \\ \hline
94 & 59.29 & 67.14 \\ \hline
95 & 62.86 & 62.14 \\ \hline
96 & 64.29 & 65.00 \\ \hline
97 & 62.86 & 70.00 \\ \hline
98 & 67.86 & 66.43 \\ \hline
99 & 65.71 & 62.14 \\ \hline
100 & 69.29 & 70.71 \\ \hline
\end{longtable}

\begin{table}[h!]
\caption{Performance of Evaluation function one Against the 7 Pre-Implemented Evaluation Functions}
\centering
\begin{tabular}{||c | c| c||} 
 \hline
Agent Eval Function & ID\_improved win \% & Agent with Custom Score Eval Function \\ \hline
Random & 85.8 & 87.9 \\ \hline
MM\_Null & 71.65 & 72.0 \\ \hline
MM\_open & 54.15 & 57.85 \\ \hline
MM\_improved & 50.0 & 55.7 \\ \hline
AB\_Null & 66.65 & 68.55 \\ \hline
AB\_open & 61.05 & 62.6 \\ \hline
AB\_improved & 58.85 & 61.8 \\ \hline
\end{tabular}
\label{eval_fun1}
\end{table}

{\bf Evalation function two}\\
The second evaluation function is implemented as \texttt{custom\_score2} in \texttt{game\_agent.py}. For any board state it returns the difference in the weighted sum of the number of moves available to the first player (max player) and the weighted sum of the number of moves available to the second player (min player). For each player and each move, the weight of each move is defined to be the number of moves (not discarding moves into spots that were previously occupied) the player has after making that move.\\

Table~\ref{eval_fun2_overall} shows shows the overall performance, over 100 tournaments, using this custom evaluation function. Evaluation function two has a higher win percentage compared to Id\_improved 75\% of the time. Table~\ref{eval_fun2} shows the performance against the seven pre-implemented evaluation functions. 

 \begin{longtable}[c]{| c | c |c |}
 \caption{Overall Performance Using Evaluation Function Two\label{eval_fun2_overall}}\\
 \hline
 %\multicolumn{2}{| c |}{Begin of Table}\\
 \hline
 Tournament Number & Id\_Improved win \% & Agent using evaluation function two win \% \\
 \hline
 \endfirsthead
 
 \hline
 \multicolumn{2}{|c|}{Continuation of Table \ref{eval_fun2_overall}}\\ 
 \hline
 Tournament Number & Id\_Improved win \% & Agent using evaluation function two win \% \\
 \hline
 \endhead
 
 \hline
 \endfoot
 
 \hline
 %\multicolumn{2}{| c |}{End of Table}\\
 \hline\hline
 \endlastfoot
1 & 64.29 & 65.71 \\ \hline
2 & 69.29 & 67.14 \\ \hline
3 & 65.00 & 65.00 \\ \hline
4 & 67.86 & 70.71 \\ \hline
5 & 59.29 & 73.57 \\ \hline
6 & 63.57 & 68.57 \\ \hline
7 & 66.43 & 69.29 \\ \hline
8 & 62.14 & 75.71 \\ \hline
9 & 68.57 & 70.00 \\ \hline
10 & 65.71 & 65.71 \\ \hline
11 & 66.43 & 65.71 \\ \hline
12 & 65.00 & 68.57 \\ \hline
13 & 61.43 & 72.14 \\ \hline
14 & 65.00 & 71.43 \\ \hline
15 & 57.86 & 68.57 \\ \hline
16 & 61.43 & 66.43 \\ \hline
17 & 68.57 & 70.00 \\ \hline
18 & 61.43 & 72.86 \\ \hline
19 & 60.00 & 63.57 \\ \hline
20 & 60.71 & 71.43 \\ \hline
21 & 65.00 & 65.00 \\ \hline
22 & 67.14 & 68.57 \\ \hline
23 & 70.71 & 69.29 \\ \hline
24 & 60.71 & 62.14 \\ \hline
25 & 59.29 & 72.14 \\ \hline
26 & 65.00 & 67.14 \\ \hline
27 & 60.00 & 68.57 \\ \hline
28 & 63.57 & 69.29 \\ \hline
29 & 55.00 & 69.29 \\ \hline
30 & 68.57 & 74.29 \\ \hline
31 & 60.71 & 66.43 \\ \hline
32 & 62.14 & 62.86 \\ \hline
33 & 67.86 & 69.29 \\ \hline
34 & 61.43 & 62.86 \\ \hline
35 & 60.71 & 68.57 \\ \hline
36 & 62.14 & 72.86 \\ \hline
37 & 65.71 & 71.43 \\ \hline
38 & 62.86 & 71.43 \\ \hline
39 & 63.57 & 70.71 \\ \hline
40 & 64.29 & 68.57 \\ \hline
41 & 57.86 & 67.86 \\ \hline
42 & 61.43 & 75.00 \\ \hline
43 & 69.29 & 72.86 \\ \hline
44 & 65.00 & 60.71 \\ \hline
45 & 64.29 & 72.86 \\ \hline
46 & 64.29 & 70.71 \\ \hline
47 & 67.86 & 68.57 \\ \hline
48 & 62.14 & 73.57 \\ \hline
49 & 66.43 & 68.57 \\ \hline
50 & 64.29 & 68.57 \\ \hline
51 & 64.29 & 67.14 \\ \hline
52 & 65.71 & 63.57 \\ \hline
53 & 66.43 & 72.86 \\ \hline
54 & 68.57 & 64.29 \\ \hline
55 & 65.00 & 70.00 \\ \hline
56 & 65.71 & 67.14 \\ \hline
57 & 62.86 & 60.71 \\ \hline
58 & 62.86 & 70.71 \\ \hline
59 & 67.14 & 63.57 \\ \hline
60 & 60.71 & 70.71 \\ \hline
61 & 65.00 & 65.71 \\ \hline
62 & 65.71 & 61.43 \\ \hline
63 & 65.71 & 72.86 \\ \hline
64 & 65.00 & 71.43 \\ \hline
65 & 67.86 & 63.57 \\ \hline
66 & 69.29 & 62.14 \\ \hline
67 & 63.57 & 62.86 \\ \hline
68 & 54.29 & 67.14 \\ \hline
69 & 65.71 & 66.43 \\ \hline
70 & 68.57 & 63.57 \\ \hline
71 & 62.86 & 64.29 \\ \hline
72 & 65.71 & 66.43 \\ \hline
73 & 63.57 & 69.29 \\ \hline
74 & 62.14 & 59.29 \\ \hline
75 & 65.00 & 62.86 \\ \hline
76 & 61.43 & 67.14 \\ \hline
77 & 60.00 & 66.43 \\ \hline
78 & 63.57 & 65.00 \\ \hline
79 & 58.57 & 67.86 \\ \hline
80 & 65.00 & 68.57 \\ \hline
81 & 60.00 & 70.71 \\ \hline
82 & 68.57 & 66.43 \\ \hline
83 & 62.14 & 67.86 \\ \hline
84 & 66.43 & 65.71 \\ \hline
85 & 64.29 & 70.71 \\ \hline
86 & 62.86 & 70.71 \\ \hline
87 & 69.29 & 63.57 \\ \hline
88 & 63.57 & 66.43 \\ \hline
89 & 66.43 & 63.57 \\ \hline
90 & 63.57 & 69.29 \\ \hline
91 & 60.71 & 63.57 \\ \hline
92 & 64.29 & 67.14 \\ \hline
93 & 63.57 & 68.57 \\ \hline
94 & 68.57 & 67.14 \\ \hline
95 & 69.29 & 70.00 \\ \hline
96 & 66.43 & 67.14 \\ \hline
97 & 62.14 & 68.57 \\ \hline
98 & 63.57 & 71.43 \\ \hline
99 & 66.43 & 64.29 \\ \hline
100 & 67.86 & 62.14 \\ \hline
\end{longtable}

\begin{table}[h!]
\caption{Performance of Evaluation function two Against the 7 Pre-Implemented Evaluation Functions}
\centering
\begin{tabular}{||c | c| c||} 
 \hline
Agent Eval Function & ID\_improved win \% & Agent using evaluation function two win \% \\ \hline
Random & 85.65 & 89.55 \\ \hline
MM\_Null & 71.3 & 74.1 \\ \hline
MM\_open & 54.35 & 57.85 \\ \hline
MM\_improved & 49.5 & 55.95 \\ \hline
AB\_Null & 67.35 & 73.0 \\ \hline
AB\_open & 62.8 & 62.95 \\ \hline
AB\_improved & 58.25 & 61.35 \\ \hline
\end{tabular}
\label{eval_fun2}
\end{table}

{\bf Evalation function three}\\
The third evaluation function is implemented as \texttt{custom\_score} in \texttt{game\_agent.py}. It is a modified version of evaluation function two. We note that the weighted sum computed in evaluation function two would usually contain some double counting of moves. Evaluation function three eliminates double counting by only taking unique subsequent moves.\\

Table~\ref{eval_fun3_overall} shows shows the overall performance, over 100 tournaments, using this custom evaluation function. Evaluation function one has a higher win percentage compared to Id\_improved 83\% of the time. Table~\ref{eval_fun3} shows the performance against the seven pre-implemented evaluation functions. 

 \begin{longtable}[c]{| c | c |c |}
 \caption{Overall Performance Using Evaluation Function Three\label{eval_fun3_overall}}\\
 \hline
 %\multicolumn{2}{| c |}{Begin of Table}\\
 \hline
 Tournament Number & Id\_Improved win \% & Agent using evaluation function three win \% \\
 \hline
 \endfirsthead
 
 \hline
 \multicolumn{2}{|c|}{Continuation of Table \ref{eval_fun3_overall}}\\ 
 \hline
 Tournament Number & Id\_Improved win \% & Agent using evaluation function three win \% \\
 \hline
 \endhead
 
 \hline
 \endfoot
 
 \hline
 %\multicolumn{2}{| c |}{End of Table}\\
 \hline\hline
 \endlastfoot 
1 & 62.86 & 63.57 \\ \hline
2 & 65.71 & 72.14 \\ \hline
3 & 67.86 & 74.29 \\ \hline
4 & 63.57 & 71.43 \\ \hline
5 & 60.00 & 63.57 \\ \hline
6 & 67.14 & 72.14 \\ \hline
7 & 60.00 & 70.71 \\ \hline
8 & 65.00 & 69.29 \\ \hline
9 & 62.14 & 65.00 \\ \hline
10 & 62.14 & 70.00 \\ \hline
11 & 70.71 & 67.14 \\ \hline
12 & 63.57 & 72.14 \\ \hline
13 & 62.14 & 63.57 \\ \hline
14 & 65.71 & 71.43 \\ \hline
15 & 63.57 & 76.43 \\ \hline
16 & 64.29 & 72.86 \\ \hline
17 & 62.86 & 69.29 \\ \hline
18 & 62.86 & 71.43 \\ \hline
19 & 67.86 & 70.71 \\ \hline
20 & 65.00 & 71.43 \\ \hline
21 & 67.14 & 65.00 \\ \hline
22 & 62.86 & 72.14 \\ \hline
23 & 64.29 & 70.71 \\ \hline
24 & 66.43 & 71.43 \\ \hline
25 & 60.00 & 63.57 \\ \hline
26 & 67.86 & 70.00 \\ \hline
27 & 57.14 & 67.86 \\ \hline
28 & 62.14 & 65.71 \\ \hline
29 & 65.71 & 70.71 \\ \hline
30 & 67.86 & 72.14 \\ \hline
31 & 70.71 & 65.00 \\ \hline
32 & 57.86 & 63.57 \\ \hline
33 & 62.86 & 64.29 \\ \hline
34 & 62.14 & 69.29 \\ \hline
35 & 69.29 & 65.00 \\ \hline
36 & 58.57 & 71.43 \\ \hline
37 & 65.71 & 67.14 \\ \hline
38 & 67.14 & 64.29 \\ \hline
39 & 64.29 & 71.43 \\ \hline
40 & 63.57 & 66.43 \\ \hline
41 & 65.71 & 67.14 \\ \hline
42 & 67.14 & 68.57 \\ \hline
43 & 68.57 & 67.14 \\ \hline
44 & 62.14 & 69.29 \\ \hline
45 & 65.00 & 70.00 \\ \hline
46 & 60.71 & 63.57 \\ \hline
47 & 67.86 & 70.00 \\ \hline
48 & 68.57 & 65.71 \\ \hline
49 & 60.00 & 71.43 \\ \hline
50 & 64.29 & 71.43 \\ \hline
51 & 64.29 & 66.43 \\ \hline
52 & 67.14 & 71.43 \\ \hline
53 & 59.29 & 68.57 \\ \hline
54 & 60.71 & 65.71 \\ \hline
55 & 69.29 & 67.86 \\ \hline
56 & 69.29 & 64.29 \\ \hline
57 & 69.29 & 64.29 \\ \hline
58 & 65.00 & 66.43 \\ \hline
59 & 62.86 & 65.71 \\ \hline
60 & 60.71 & 66.43 \\ \hline
61 & 66.43 & 70.00 \\ \hline
62 & 63.57 & 64.29 \\ \hline
63 & 63.57 & 67.14 \\ \hline
64 & 61.43 & 69.29 \\ \hline
65 & 65.00 & 68.57 \\ \hline
66 & 66.43 & 65.71 \\ \hline
67 & 67.86 & 65.71 \\ \hline
68 & 62.86 & 68.57 \\ \hline
69 & 70.00 & 68.57 \\ \hline
70 & 62.86 & 67.14 \\ \hline
71 & 64.29 & 66.43 \\ \hline
72 & 59.29 & 68.57 \\ \hline
73 & 67.86 & 71.43 \\ \hline
74 & 63.57 & 72.14 \\ \hline
75 & 65.00 & 63.57 \\ \hline
76 & 64.29 & 67.86 \\ \hline
77 & 65.71 & 65.00 \\ \hline
78 & 59.29 & 71.43 \\ \hline
79 & 65.00 & 67.14 \\ \hline
80 & 60.71 & 65.00 \\ \hline
81 & 61.43 & 75.71 \\ \hline
82 & 70.71 & 61.43 \\ \hline
83 & 60.71 & 65.71 \\ \hline
84 & 63.57 & 70.00 \\ \hline
85 & 62.14 & 62.86 \\ \hline
86 & 61.43 & 75.00 \\ \hline
87 & 67.14 & 72.86 \\ \hline
88 & 63.57 & 67.86 \\ \hline
89 & 62.14 & 66.43 \\ \hline
90 & 65.71 & 62.86 \\ \hline
91 & 65.00 & 70.71 \\ \hline
92 & 61.43 & 64.29 \\ \hline
93 & 64.29 & 67.86 \\ \hline
94 & 65.00 & 72.14 \\ \hline
95 & 67.14 & 70.71 \\ \hline
96 & 62.86 & 70.00 \\ \hline
97 & 65.00 & 67.86 \\ \hline
98 & 64.29 & 67.86 \\ \hline
99 & 69.29 & 70.00 \\ \hline
100 & 66.43 & 71.43 \\ \hline
\end{longtable}

\begin{table}[h!]
\caption{Performance of Evaluation function three Against the 7 Pre-Implemented Evaluation Functions}
\centering
\begin{tabular}{||c | c| c||} 
 \hline
Agent Eval Function & ID\_improved win \% & Agent using evaluation function three win \% \\ \hline
Random & 85.85 & 89.1 \\ \hline
MM\_Null & 72.55 & 76.35 \\ \hline
MM\_open & 54.55 & 59.15 \\ \hline
MM\_improved & 50.05 & 56.65 \\ \hline
AB\_Null & 68.7 & 72.6 \\ \hline
AB\_open & 60.4 & 62.15 \\ \hline
AB\_improved & 58.75 & 62.4 \\ \hline
\end{tabular}
\label{eval_fun3}
\end{table}

In the code submission, evaluation function three was used as the custom evaluation function based on:

\begin{itemize}
\item The fact that it considers how many independent moves are available after making a move.
\item It weights positions in the center of the board higher than positions further away.
\item Its slightly superior performance as shown by its percentage of wins over 100 games.
\end{itemize}
\end{document}