report2/implementation.tex

   1 \section{Implementation}
   2 \subsection{Screen encoding}
   3 When parsed the sokoban screen is stripped of all walls and unreachable empty
   4 spaces are removed.
   5
   6 Let $T=\{free,box,target,agent,targetagent,targetbox\}$ be the set of possible
   7 states of a tile. Tiles are numbered and thus a sokoban screen is the set $F$
   8 containing a $x_i\in T$ for every tile. We introduce a function $ord(x, y)$
   9 that returns the tile number for a given $x$ and $y$ coordinate and a function
  10 $iord(i)$ that does the reverse. To encode the
  11 state we introduce an encoding function that encodes a state in three boolean
  12 variables:
  13 $$encode(t)=\begin{cases}
  14         001 & \text{if }t=free\\
  15         010 & \text{if }t=box\\
  16         011 & \text{if }t=target\\
  17         100 & \text{if }t=targetbox\\
  18         101 & \text{if }t=agent\\
  19         110 & \text{if }t=agentbox
  20 \end{cases}$$
  21
  22 This means that the encoding of a screen takes $3*|F|$ variables.
  23
  24 \subsection{Transition encoding}
  25 We introduce a variable denoting the intended direction of movement $m \in
  26 \{\text{up}, \text{down}, \text{left}, \text{right}\}$. Per move we define a
  27 $\delta$ and $\gamma$ variable which represent the change in coordinate value
  28 respectively for the next position and the position next to the next postition.
  29 $$\delta_{(x,y)}(m)=\begin{cases}
  30         (x-1, y) & \text{if } m = left\\
  31         (x+1, y) & \text{if } m = right\\
  32         (x, y+1) & \text{if } m = down\\
  33         (x, y-1) & \text{if } m = up\\
  34 \end{cases}\quad
  35 \gamma{(x,y)}(m)=\begin{cases}
  36         (x-2, y) & \text{if } m = left\\
  37         (x+2, y) & \text{if } m = right\\
  38         (x, y+2) & \text{if } m = down\\
  39         (x, y-2) & \text{if } m = up\\
  40 \end{cases}$$
  41
  42 We define the tile update function $next(i_1, i_2, i_3)$ where $i_1$ contains
  43 the agent and $i_2$ and $i_3$ are adjacent to it in some direction.
  44 $$next(i_1, i_2, i_3)=\left\{\begin{array}{lll}
  45 % Three state transitions
  46         (free, agent, box) & \text{if } &
  47                 i_1=agent \wedge i_2=box \wedge i_3=free\\
  48         (target, agent, box) & \text{if } &
  49                 i_1=targetagent \wedge i_2=box \wedge i_3=free\\
  50         (free, targetagent, box) & \text{if } &
  51                 i_1=agent \wedge i_2=targetbox \wedge i_3=free\\
  52         (free, agent, targetbox) & \text{if } &
  53                 i_1=agent \wedge i_2=box \wedge i_3=targetbox\\
  54         (target, targetagent, box) & \text{if } &
  55                 i_1=targetagent \wedge i_2=targetbox \wedge i_3=free\\
  56         (target, agent, targetbox) & \text{if } &
  57                 i_1=targetagent \wedge i_2=box \wedge i_3=target\\
  58         (free, targetagent, targetbox) & \text{if } &
  59                 i_1=agent \wedge i_2=targetbox \wedge i_3=target\\
  60         (target, targetagent, targetbox) & \text{if } &
  61                 i_1=targetagent \wedge i_2=targetbox \wedge i_3=target\\
  62 % Two state transitions
  63         (free, agent, i_3) & \text{if } & i_1=agent \wedge i_2=free\\
  64         (free, targetagent, i_3) & \text{if } & i_1=agent \wedge i_2=target\\
  65         (target, agent, i_3) & \text{if } & i_1=targetagent \wedge i_2=free\\
  66         (target, targetagent, i_3) & \text{if } & i_1=targetagent \wedge i_2=target\\
  67 % One state transitions
  68         (agent, i_2, i_3) & \text{if } & i_1=agent\\
  69         (targetagent, i_2, i_3) & \text{if } & i_1=targetagent\\
  70 \end{array}\right.$$
  71
  72 \subsection{Example}
  73 For example, take the toy screen shown in Listing~\ref{lst:toy}. When the
  74 screen is parsed the unreachable space is first removed by detecting reachable
  75 space with the flood fill algorithm. This results in the minimized screen
  76 listed in Listing~\ref{lst:toy2}.
  77
  78 \lstinputlisting[label={lst:toy},caption={Example screen}]{toy.screen}
  79 \lstinputlisting[label={lst:toy2},caption={Example screen}]{toy2.screen}
  80
  81 \subsubsection{Encoding}
  82 To encode the screen the tiles are numbered from left to right from top to
  83 bottom. Thus resulting in $i_1=agent, i_2=box, i_3=target$. When we translate
  84 these numbers to sylvan-sane variables we get the following bdd shown in
  85 Figure~\ref{fig:toy}. Variables $0, 2, 4$ represent $i_1$, $6, 8, 10$ represent
  86 $i_2$ and lastly $12, 14, 16$ represents $i_3$.
  87 \begin{figure}[p]
  88         \centering
  89         \includegraphics[scale=0.1]{toy.eps}
  90         \caption{Initial state encoding of the example~\label{fig:toy}}
  91 \end{figure}
  92
  93 Encoding the goal state happens in a similar way. The algorithm basically
  94 states that all $target$ positions should be $boxtarget$. This is results in
  95 the BDD shown in Figure~\ref{fig:toy2}.
  96
  97 \begin{figure}[p]
  98         \centering
  99         \includegraphics[scale=0.1]{toy2.eps}
 100         \caption{Goal state encoding of the example~\label{fig:toy2}}
 101 \end{figure}
 102
 103 Finally encoding the transitions already results in a long list of complicated
 104 BDDs that each encode a possible move in all possible directions. In this
 105 example there is only one move possible in the first state, thus all moves
 106 except for the one move result in a relative product that is empty. For example
 107 the sub-BDD that encodes the first position only looks is visualized in
 108 Figure~\ref{fig:toy3}. The only satisfying assignment is that $0, 2, 4$ hold
 109 the values $1, 0, 1$ thus encoding man and the variables $1, 3, 5$ holding the
 110 values $0, 0, 1$ thus encoding free.
 111
 112 \begin{figure}[p]
 113         \centering
 114         \includegraphics[scale=0.1]{toy3.eps}
 115         \caption{Sub-BDD of a move~\label{fig:toy3}}
 116 \end{figure}
 117
 118 \subsubsection{Results}