<commit_before>Within the field of game theory there exists games with state spaces so small, that the optimal strategy can be computed within seconds. 
In the other end we have games with state spaces so large that calculating the optimal strategy by exploring the state space is impossible to do within a reasonable amount of time. 
The focus of this project lies on the game \emph{Yahtzee} that in its Solitaire version has a state space belonging to the first category, but in its multi player version belongs to the second.

\begin{table}[h] %Den står et lidt underligt sted?
\centering
\begin{tabular}{|r|r|r|}
\hline
&\textbf{Solitaire} & \textbf{Multi player} 		\\ \hline
\textbf{Bits} 	& 22		&  49 					\\ \hline
\textbf{States} & 4,194,304	&  562,949,953,421,312	\\ \hline	

\end{tabular}
\caption{The required number of bits to represent a state and resulting state space size in \emph{Yahtzee}.}
\end{table}


An optimal solution for the game of Solitaire \emph{Yahtzee} has been discussed and calculated by <NAME>, and an AI based on this work has been implemented by <NAME>.
<NAME> proposes an optimal solution for the multi player game and mentions that the state space is of a size that makes it impossible to do - both in terms of space and time.
%TODO
The main goal of our project is not to calculate the optimal solution but instead to improve on the current state of the art sub-optimal multi player \emph{Yahtzee} AI. 
%TODO
The currently strongest strategy for implementing a \emph{Yahtzee} ai is called Single player AI. 
The strategy is to consider \emph{Yahtzee} a singleplayer game where the goal is to maximize your score. 
The state space for calculating this strategy is small enough that any modern computer will be able to perform the computations within a reasonable amount of time. 
We have described and implemented the single player AI algorithm using the work of <NAME>\cite{glenn2006optimal}, which gives a in depth explanation of the implementation, theory, and testing of the single player AI algorithm.

Our main goal of the project is therefore to prove that it is possible with current technology to implement a \emph{Yahtzee} AI with a better performance than the single player AI. 
This is widely believed to be true since there have already been made claims that this have been achieved jet how haven't been properly documented.
The work by <NAME> is, to our knowledge, the claim of how to make a better yahtzee AI with the strongest documentation to back it up. 
While the paper of <NAME>\citep{pawlewicz2011nearly} presents impressive results it doesn't actually test the single player AI versus a multiplayer AI.
We therefore seek to prove that their exists a better sub-optimal strategy for \emph{Yahtzee} by proving that our implementation defeats the single player \emph{Yahtzee} AI more than $50"\%" $ of the time by a significant amount. The AI described in this article will only be viable for two player \emph{Yahtzee}.

We have implemented a \emph{Yahtzee} AI following a strategy somewhat similar to the single player AI except that it switch between aggression based strategies depending on it's chance to beat the other players expected final score for a given state. 
We will represent the theory behind the single player ai, how we have extended it into our competing multiplayer AI and show test results of how the two implementations performs when playing each other. 
Finally we will test each AI against a restricted optimal \emph{Yahtzee} AI and calculate the average amount of mistake made by each of them.

%Introduction text
 %TODO Domæne (Yahtzee)
 %TODO SinglePlayer AI ref til Glenn
 %TODO Optimal MP AI (ikke vores impl) ref til Pawlewicz
 %TODO Idé (near optimal mp ai)!
<commit_msg>Work on introduction<commit_after>Within the field of game theory there exists games with state spaces so small, that the optimal strategy can be computed within seconds. 
In the other end we have games with state spaces so large that calculating the optimal strategy by exploring the state space is impossible to do within a reasonable amount of time. 
The focus of this project lies on the game \emph{Yahtzee} that in its Solitaire version has a state space belonging to the first category, but in its multi player version belongs to the second.

\begin{table}[h] %Den står et lidt underligt sted?
\centering
\begin{tabular}{|r|r|r|}
\hline
&\textbf{Solitaire} & \textbf{Multi player} 		\\ \hline
\textbf{Bits} 	& 22		&  49 					\\ \hline
\textbf{States} & 4,194,304	&  562,949,953,421,312	\\ \hline	

\end{tabular}
\caption{The required number of bits to represent a state and resulting state space size in \emph{Yahtzee}.}
\end{table}


An optimal solution for the game of Solitaire \emph{Yahtzee} has been discussed and calculated by <NAME>\cite{verhoeff2004optimal}, and an AI based on this work has been implemented by <NAME>\cite{glenn2006optimal}.
The strategy is to consider \emph{Yahtzee} a single player game where the goal is to maximize your score. 
The state space for calculating this strategy is small enough that any modern computer will be able to perform the computations within a few hours.
We have described and implemented the single player AI algorithm using the work of <NAME>, which gives a in depth explanation of the implementation, theory, and testing of the single player AI algorithm.

<NAME> proposes an optimal solution for the multi player game and mentions that the state space is of a size that makes it impossible to do - both in terms of space and time.
The aim of our project is not to calculate the optimal solution but instead to improve on the current state of the art sub-optimal multi player \emph{Yahtzee} AI. 
Our main goal of the project is to show how it is possible with current technology to implement a multi player \emph{Yahtzee} AI that has a better performance in a multi player game than the single player AI, that can be computed and run in a reasonable amount of time.\footnote{i.e. at most \emph{days} of computation for preparation and \emph{seconds} of computation when playing.}

Claims have been made, that such an algorithm already exists, but it has not been properly documented.
The work by <NAME> is, to our knowledge, the publication with the strongest documentation of how to make a well performing multi player \emph{Yahtzee} AI.
While the paper of <NAME>\citep{pawlewicz2011nearly} presents impressive results it doesn't actually test the single player AI against a multi player AI, and thus doesn't show that it plays better than the well known optimal Solitaire solution.

We seek to  prove that their exists a better sub-optimal strategy for \emph{Yahtzee} by proving that our implementation defeats the single player \emph{Yahtzee} AI more than $51"\%" $ of the time with at least $95\% $ confidence. The AI described in this article will only be viable for two player \emph{Yahtzee}.

We have implemented a \emph{Yahtzee} AI following a strategy somewhat similar to the single player AI except that it switch between aggression based strategies depending on it's chance to beat the other players expected final score for a given state. 
We will represent the theory behind the single player ai, how we have extended it into our competing multiplayer AI and show test results of how the two implementations performs when playing each other. 
Finally we will test each AI against a restricted optimal \emph{Yahtzee} AI and calculate the average amount of mistake made by each of them.

%Introduction text
 %TODO Domæne (Yahtzee)
 %TODO SinglePlayer AI ref til Glenn
 %TODO Optimal MP AI (ikke vores impl) ref til Pawlewicz
 %TODO Idé (near optimal mp ai)!

{'fraction_non_alphanumeric': 0.04735883424408015, 'fraction_numerical': 0.01014832162373146, 'mean_word_length': 4.455642299503194, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5865408', 'n_tokens_mistral': 2039, 'n_tokens_neox': 1914, 'n_words': 1199}