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 \texttt{\_\@\$} will be encoded as follows: