1 \section{Implementation
}
2 \subsection{Screen encoding
}
3 When parsed the sokoban screen is stripped of all walls and unreachable empty
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
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
22 This means that the encoding of a screen takes $
3*|F|$ variables.
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\\
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\\
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\\