foo-1.0: fooDocu.tex

\documentclass[a4paper]{article}
\usepackage[cp1250]{inputenc}
\title{Foo Project Documentation}
\author{Bartosz Wójcik}
\date{08.04.2008}
\begin{document}
\maketitle
\begin{abstract}
Project {\tt Foo} is implementation of a playing machine for Paper Soccer, a pencil and paper game for two players, described in WIKIPEDIA. Written in Haskell, contains also simply user interface using HOpenGL library. The project is focused on the engine, more precisely --- on the theoretical side of the solution.
{\tt Foo} delivers two solutions: a game, where end user can play against machine, and stand alone playing machine that needs an interface to be used further.
\end {abstract}

\section{Objective}
This document contains game description, user guide and theoretical details of the implementation.

\section{Game description}
The game has been described in WIKIPEDIA under 'Paper Soccer'. Please refer to it in order to learn rules {\tt http://en.wikipedia.org/wiki/Paper\_Soccer}.

Rules of this game can be completed by simply odd-on. Player who does the move that finishes game due to no further available move left, loses only half a point.

Size of the court can be defined almost without limits. Although playing machine supports any field size, $8 \times 8$ one has been chosen for end user game.

\section{How can I install Foo on my PC?}
Follow below instructions.

\subsection{Install GHC}
First install Haskell compiler. I've used GHC only, so there is no guarantee that solution work under other Haskell impementations. GHC you can find here: {\tt http://www.haskell.org/ghc/}. Follow installing instructions there. The newest installation contains required GLUT and OpenGL Libraries.

\subsection{Compile sources}
Download sources to separate directory and compile them there using following command {\tt ghc --make -package GLUT PlayFoo.hs -cpp -o PlayFoo}. This works assuming you have direct acess to GHC compiler.

\subsection{Shortcut for Windows}
Widnows users can download binary package. It has to be decompressed in any place and used as it is.

\section {User guide}
Just run executable you've downloaded or compiled. Then choose who plays against whom in serie of questions. Then play or observe how two algorithms play one against another.
You play by selecting move with mouse.
Playing machine displays in console number of avaiable moves for each its turn.
Once current game has finished you have to click on the game window to get next one game or quit.

Because single game lasts relatively short, it is usual that one plays couple games in row. Results of single games are cumulated and total result is considered as match result.

\subsection {Playing Machines}

There are following algorithms available.
\begin{verbatim}
GoAhead - 0
GoBackWatchOpponent - 1
GoAheadWatchOpponent - 2
PreventingOpponent40 - 3
PreventingOpponent50 - 4
Watch2Ahead - 5
Watch3Ahead - 6
\end{verbatim}

They are presented in the ascending power order. More powerful algoritm, longer you need to wait for the response. I've tested all of them on PC Intel Core2 Duo 2,2GHz 2GB RAM and in this configuration I have to disrecommend you using the last, 6th one. On the other hand on the Intel Pentum 1,8Ghz 256MB RAM the 5th algorithm was still playable.


\section{User interface}
User interface is very simply. It renders filed, nodes of net (vertices), and done moves. It also highlights the possible passes during 
manipulating with mouse, and shows current result and names of players.

\section {Technical details regarding the game}

There are couple important details that make this game amazingly not easy to put into simply playing machine. I'll describe them in the next paragraphs.

\subsection {Space of Moves}
For Playing Machines the size of space of moves of the game is basic problem to cope with. Bigger space is, cannot algorithms process many plies and are weaker. Bigger space is, more advanced move prunes methods have to be implemented. What is space of the moves of {\tt Foo}?
It is very unstable. In first move it contains only $8$ possiblities. Usually it varies between $10$ to $100$ moves. Sometimes (once or twice times during the single game) it contains even to $1000$ possibilities. 
The biggest space of moves I've seen was about $5000$ moves. This all for field $8 \times 8$. Imagine then that you want to build powerfull playing machine scaning $5$ plies of moves. Such a machine will have to cope often with about than $100^5$ which is $10^{10}$ moves. Besides of some cases (once or twice in single game) where this number will be bigger.
There is also additional difficulty. If one ply contains many moves, lot of them (meaningfull percent) will lead to similar big or bigger next ply. One thing more --- more plyes are scaned, more moves will lead to huge next ply.
This is unpleasant point of {\tt Foo} --- space of moves sometimes explodes.

\subsection {Number of Moves}
Players play until game is over. How many moves will they do? The answer is easy: The initial field's size is limitation of number of moves. Each move finishes in one of not yet achieved nodes of field. So for field $8 \times 8$ we have limit of 50 moves. Not many -- easy for playing machine.

\subsection {Game's goal}
Easier is to describe the goal of the game, easier is to implement the move selection. {\tt Foo} has very easy to implement goal: score a goal, don't let you score a goal, do not finish move in vegetables. The easy algorithm "force ahead to opponent's goal" is also quite powerfull. Still there is a little difficulty. There are some situations where "brutal force" is not a good solution. This is easy noticably by human playes, but "brutal force" would need to scan 6 or more plies in order to find this out. Exists then better solution?
For sure, I'll desribe one attempt later.

\subsection {Game's rules}
Difficult, sophisticated rules lead usually to complex solutions and bring problems. {\tt Foo} doesn't bring here problems, besides one. In many situation it is possible to create same move in many different ways. This leads to increased number of moves. Percentage of such moves is bigger for plies where there are many moves already. Therefore this can kill your solution if you won't recognize and prune duplicates.

\section{Technical details regarding implementation}

I had pleasure to cope with problems I've described above. Eventually I managed to create hardly acceptable result, at least from expectations' point of view. I wanted to create playing machine that can beat myself. It is not the case.

\subsection{Recognition of duplicates}
In order to find duplicates I search space of moves using Breadth-First Search method. Each time new added edge to the current move constructs a cycle within the move, there is posibility to get same move in 2nd way, adding edges of cycle in opposite order. In this way duplicates are recognized and pruned.
What are consequences of using BFS? For example the Alpha-Beta pruning is not possible to use.

\subsection{Space of Moves}
Finally this problem became the most difficult one I had to fight against. Working in pure functional language I was able to define number of plies to be scaned, but not the number of moves I want my solution scans in total withing one turn. As number of moves vary from few to thousends, this difficulty is capital and therefore I find functional solution here not well fitting.

Finally I've found method to limit number of moves within each ply separatelly. This limitation is very drastic and still brings acceptable solution. In details I've limited algorithms as follows.

\begin{itemize}
\item {\tt GoAhead} --- $1$ ply, $1000$ moves.
\item {\tt GoBackWatchOpponent} --- $1 {1\over 2}$ plies, limit $1000$ moves a ply.
\item {\tt GoAheadWatchOpponent} --- $1 {1\over 2}$ plies, limit $1000$ moves a ply.
\item {\tt PreventingOpponent40} --- $2$ plies, limit $40$ moves a ply --- $p \times 1600$ scaned moves.
\item {\tt PreventingOpponent50} --- $2$ plies, limit $50$ moves a ply --- $p \times 2500$ scaned moves.
\item {\tt Watch2Ahead} --- $3$ plies, limit $30$ moves a ply --- $p \times 27000$ scaned moves.
\item {\tt Watch3Ahead} --- $4$ plies, limit $18$ moves a ply --- $p \times 105000$ scaned moves.
\end{itemize}

where $p$ is average number of moves really existed in the ply divide by ply limt of the algorithm. So for {\tt Watch3Ahead} assuming average $100$ moves a ply, we get ${100 \over 18} \times 105000 \approx 60*10^5$ scaned moves.
They are limits only! If you remember the number of moves per ply I've mentioned above, you'll notice that for last 2 algorithms limits are almost always reached.
Do you think that $60 \times 10^5$ scaned moves is not much? I think so too. Why then is the solution so slow? Bad implementation?
I've checked how are distributed costs of process. The most time cosuming process is graph update and manipulation on vertices within graph. Would this be done ineffectively?
The answer is: yes. And the explanation is: this is overhead of functional language.

Let me explain this. 
There are done two manipulations on graph: search and remove. How much they cost? Depending on data strucutre. Indexed arrays should give costs O(1). Binary trees --- O(log n), where n is number of elements in tree. But, there is a problem here --- in functional language arrays cannot be modified, therefore delete of element from array leads to copying the whole array --- costs O(n)! Because of this I had to use binary trees as a solution. The fast solution in descriptive language would need to contain fast graph manipulation functions.

And the last thing. How did I manage to limit number of evaluated moves within one ply? The solution is very easy but I don't spoil you pleasure of working on this. If you want to know, you can find this in the sources.

\subsection {Game's goal}

I've mentioned above, that "brutal force" solution brings some difficulties. Please notice that this solution prefers moves that finish close to the opponent's goal. "Close" in meaning of number of passes. But actually moves contain different number of passes, so the better idea would be to consider distance from goal in meaning of moves.

I've spent a lot of time implementing such solution but failed. My solutions worked too slow. Again the reason was functional language.

It's much more difficult to calculate distance from any two vertices in meaning of moves than in meaning of passes. Therefore it is necessary to store calculated values and update them only when necessary. This leads to sophisticated data model and complicated rules of modification of state of field.
Such a solution gives potentialy many possibilities of tuning of algoritms. There are five meaningful factors algorithm can base on.
\begin{itemize}
\item Distance from opponent's goal.
\item Distance from own goal (these two are not complementary!).
\item Number of vertices where next move can be finished and which are in distance $1$ from opponents goal.
\item Number of vertices where next move can be finished and which are in distance $1$ from own goal.
\item Goals can be not accessible.
\end{itemize}
\end{document}