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. Moreover, a screen is rejected if either there are no
   5 boxes, there is no agent or the number of boxes is not equal to the number of
   6 targets.
   7
   8 Let $T=\{free,box,target,agent,targetagent,targetbox\}$ be the set of possible
   9 states of a tile. Tiles are numbered and thus a sokoban screen is the set $F$
  10 containing a $x_i\in T$ for every tile. We introduce a function $ord(x, y)$
  11 that returns the tile number for a given $x$ and $y$ coordinate and a function
  12 $iord(i)$ that does the reverse. To encode the state we introduce an encoding
  13 function that encodes each screen tile as a unique combination of boolean
  14 variables:
  15 $$encode(t)=\begin{cases}
  16         001 & \text{if }t=free\\
  17         010 & \text{if }t=box\\
  18         011 & \text{if }t=target\\
  19         100 & \text{if }t=targetbox\\
  20         101 & \text{if }t=agent\\
  21         110 & \text{if }t=agentbox
  22 \end{cases}$$
  23
  24 This means that the encoding of a screen takes $3*|F|$ variables.
  25
  26 \subsection{Transition encoding}
  27 We generate transition relations for four possible move directions of an agent,
  28 for all screen tiles. There are three type of transition relations, namely: a
  29 one-tile relation (changes only one tile), a two-tile relation (changes only
  30 two tiles) and a three-tile relation (transforms three tiles per transition
  31 simultaneously). In order to generate transition relations, we iterate through
  32 a screen and for each tile we check neighbouring space with the purpose of
  33 generating only the relevant relations. For example, if we consider a tile in
  34 the top-left corner, there is no need to generate one or two-tiled transition
  35 relations which can transform tiles to the left or to the right of that given
  36 tile. For each possible direction of agent movement, we define a $\delta$ and a
  37 $\gamma$ variables which represent the change in coordinate values respectively
  38 for the next position and the position next to the next position.
  39 $$\delta_{(x,y)}(m)=\begin{cases}
  40         (x-1, y) & \text{if } m = left\\
  41         (x+1, y) & \text{if } m = right\\
  42         (x, y+1) & \text{if } m = down\\
  43         (x, y-1) & \text{if } m = up\\
  44 \end{cases}\quad
  45 \gamma{(x,y)}(m)=\begin{cases}
  46         (x-2, y) & \text{if } m = left\\
  47         (x+2, y) & \text{if } m = right\\
  48         (x, y+2) & \text{if } m = down\\
  49         (x, y-2) & \text{if } m = up\\
  50 \end{cases}$$
  51
  52 We define the following tile update functions: $next(i_1)$, $next'(i_1,i_2)$
  53 $next''(i_1, i_2, i_3)$ where $i_1$ contains the agent and $i_2$ and $i_3$ are
  54 adjacent to it in some direction.
  55
  56 $$next(i_1)=\left\{\begin{array}{lp{2pt}l}
  57         (agent) & \text{if } & i_1=agent\\
  58         (targetagent) & \text{if } & i_1=targetagent\\
  59 \end{array}\right.$$
  60
  61 $$next'(i_1, i_2)=\left\{\begin{array}{lp{2pt}l}
  62         (agent, free) & \text{if } & i_1=free \wedge i_2=agent\\
  63         (agent, target) & \text{if } & i_1=free \wedge i_2=targagent\\
  64         (targagent, free) & \text{if } & i_1=target \wedge i_2=agent\\
  65     (targagent, target) & \text{if } & i_1=target \wedge i_2=targagent\\
  66         (agent, box) & \text{if } & i_1=agent \wedge i_2=box\\
  67         (agent, targbox) & \text{if } & i_1=agent \wedge i_2=targbox\\
  68         (targagent, box) & \text{if } & i_1=targagent \wedge i_2=box\\
  69         (targagent, targbox) & \text{if } & i_1=targagent \wedge i_2=targbox\\
  70 \end{array}\right.$$
  71
  72 $$next''(i_1, i_2, i_3)=\left\{\begin{array}{lp{2pt}l}
  73         (agent, box, box) & \text{if } &
  74                 i_1=agent \wedge i_2=box \wedge i_3=box\\
  75         (agent, box, targbox) & \text{if } &
  76                 i_1=agent \wedge i_2=box \wedge i_3=targbox\\
  77         (targagent, box, box) & \text{if } &
  78                 i_1=targetagent \wedge i_2=box \wedge i_3=box\\
  79         (targagent, box, targbox) & \text{if } &
  80                 i_1=targagent \wedge i_2=box \wedge i_3=targbox\\
  81         (agent, box, free) & \text{if } &
  82                 i_1=free \wedge i_2=agent \wedge i_3=box\\
  83         (agent, targbox, free) & \text{if } &
  84                 i_1=free \wedge i_2=targagent \wedge i_3=box\\
  85         (agent, box, target) & \text{if } &
  86                 i_1=free \wedge i_2=agent \wedge i_3=targbox\\
  87         (agent, targbox, target) & \text{if } &
  88                 i_1=free \wedge i_2=targagent \wedge i_3=targbox\\
  89         (targagent, box, free) & \text{if } &
  90                 i_1=targetagent \wedge i_2=targetbox \wedge i_3=target\\
  91         (targagent, targbox, free) & \text{if } &
  92                 i_1=target \wedge i_2=targagent \wedge i_3=box\\
  93         (targagent, box, target) & \text{if } &
  94                 i_1=target \wedge i_2=agent \wedge i_3=targbox\\
  95         (targagent, targbox, target) & \text{if } &
  96                 i_1=target \wedge i_2=targagent \wedge i_3=targbox\\
  97 \end{array}\right.$$
  98
  99 \subsection{Goal encoding}
 100 Encoding the goal state is very trivial. Just make sure all $target$ tiles are
 101 $targetbox$ tiles.
 102
 103 \subsection{Algorithm}
 104 We use the standard optimized reachability algorithm to solve a screen but
 105 added a goal condition that breaks the loop. When the loop breaks prematurely
 106 it means a solution is found. If the full loop continues until the entire state
 107 space is searched and the break condition is not met it means there is no
 108 solution.
 109
 110 \begin{algorithm}[H]
 111         \KwIn{I, Initial state BDD}
 112         \KwIn{$R_i$, List of transition BDDs}
 113         \KwIn{G, Goal BDD}
 114         $V_{old}\leftarrow BDDempty$\;
 115         $V_{new}\leftarrow I$\;
 116         \While{$V_{new}\neq V_{old}$}{
 117                 $V_{old}\leftarrow V_{new}$\;
 118                 \ForEach{$R_i$}{
 119                         $V_{new}\leftarrow BDDapply(\vee, V_{new}, BDDrelprod(V_{new}, R_i)$\;
 120                 }
 121                 \lIf{$BDDsatcount(BDDand(G, V_{new}))>0$}{$break$}
 122         }
 123 \end{algorithm}
 124
 125 \subsection{Example}
 126 For example, take the toy screen shown as the first representation in
 127 Listing~\ref{lst:toy}. When the screen is parsed the unreachable space is first
 128 removed by detecting reachable space with the flood fill algorithm. This
 129 results in the second representation in Listing~\ref{lst:toy}.
 130
 131 \lstinputlisting[label={lst:toy},caption={Example screen}]{toy.screen}
 132
 133 To encode the screen the tiles are numbered from left to right from top to
 134 bottom (in a convenient coordinate-like manner). In order to translate the
 135 initial screen into BDD representation, we iterate through a screen's tiles. We
 136 use even BDD variable identifiers to represent states (screens). For convenient
 137 BDD creation, we use sylvan cubes.As an example we can consider the following
 138 bdd shown in
 139 Figure~\ref{fig:toy}. Variables $0, 2, 4$ represent $i_1$, $6, 8, 10$ represent
 140 $i_2$ and lastly $12, 14, 16$ represents $i_3$.
 141 \begin{figure}[p]
 142         \centering
 143         \includegraphics[width=\textwidth]{toy.png}
 144         \caption{Initial state encoding of the example~\label{fig:toy}}
 145 \end{figure}
 146
 147 Encoding the goal state happens in a similar way. The algorithm basically
 148 states that all $target$ positions should be $boxtarget$. This is results in
 149 the BDD shown in Figure~\ref{fig:toy2}.
 150
 151 \begin{figure}[p]
 152         \centering
 153         \includegraphics[width=.5\textwidth]{toy2.png}
 154         \caption{Goal state encoding of the example~\label{fig:toy2}}
 155 \end{figure}
 156
 157 Finally encoding the transitions already results in a long list of complicated
 158 BDDs that each encode a possible move in all possible directions. In transition
 159 relations, even BDD variable identifiers act as state filters, whereas even
 160 variable identifiers act as new values. Each transition changes only a limited
 161 subset of the screen variables. In this example there is only one move possible
 162 in the first state, thus all moves except for the one move result in a relative
 163 product that is empty. For example the sub-BDD that encodes the first position
 164 only looks is visualized in Figure~\ref{fig:toy3}. The only satisfying
 165 assignment is that $0, 2, 4$ hold the values $1, 0, 1$ thus encoding man and
 166 the variables $1, 3, 5$ holding the values $0, 0, 1$ thus encoding free.
 167
 168 \begin{figure}[p]
 169         \centering
 170         \includegraphics[width=.8\textwidth]{toy3.png}
 171         \caption{Sub-BDD of a move~\label{fig:toy3}}
 172 \end{figure}