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)$ for $i \in F$.
  43 $$next(i)=\left\{\begin{array}{lll}
  44         free & \text{if } & i=agent \wedge \delta(i)=free\\
  45                 & \vee & i = agent \wedge \delta(i)=target\\
  46         target & \text{if } & i=targetagent \wedge \delta(i)=free\\
  47                 & \vee & i = targetagent \wedge \delta(i)=target\\
  48         agent & \text{if } & i=free \wedge \delta(i)=agent\\
  49                 & \vee & i = free \wedge \delta(i)=targetagent\\
  50         targetagent & \text{if } & i=target \wedge \delta(i)=agent\\
  51                 & \vee & i = target \wedge \delta(i)=targetagent\\
  52 \end{array}\right.$$