summaryrefslogtreecommitdiff
path: root/docs/random_avoid.tex
blob: 90ac183b93bd819ddd4bc26321cfc0578766d6a1 (about) (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
%%- from "macros.tex" import make_board -%%

\section{Random Avoid Bot}
\fasttrack{Choose a direction at random, but not one which will lead to immediate death.}

The last bot we wrote had a big problem, it ran into its own tail.
We don’t want our next bot to be that stupid, so we need to teach it how to not
do that!

But before we can do that, we need to know few more things about our bots.
You might have noticed that our functions have two parameters,
\texttt{board} and \texttt{position}.
We haven’t had to use them so far, but we will now, so we need to know what they
are.
But rather than me just telling you what they are,
why not have a look yourself?

\pythonfile{print_bot.py}

You should see something like this (on a 4x3 board):
\begin{minted}{pytb}
(1, 2)
[['.', '.', '*', '.'], ['.', '.', '*', '.'], ['.', 'A', '.', '.']]
Exception in bot A (<'<'>function print_bot at 0x7f61165f2e60<'>'>):
------------------------------------------------------------
Traceback (most recent call last):
  File "…/snakegame/engine.py", line 132, in update_snakes
    "Return value should be a string."
AssertionError: Return value should be a string.
------------------------------------------------------------
\end{minted}

Ignore all the Exception stuff, that’s just because we didn’t return one of
\py|'L'|, \py|'U'|, \py|'D'| or \py|'R'|.
The first line is our position: it’s a \py|tuple| of the x and y
coordinates of our snake’s head.
The second line is the board: it’s a list of each row in the board,
and each row is a list of the cells in that row.

Notice that if we index the board first by the y coordinate and then by the x
coordinate, we can get the character in the board where our snake is:
\py|board[y][x] == board[2][1] == 'A'|.
The head of our snake is always an uppercase character in the board,
and the rest of our body (the tail) are always lowercase characters.

This is all very well, but how do we stop our bot from eating its tail?
Well, the answer is that we need to look at each of the squares surrounding our
snake’s head, to see if we’ll die if we move into them or not.

Let’s have a look at the square to the right of our snake’s head.
First, we need to know its coordinates: looking at
Board~\ref{brd:right-square:normal},
we see that if our snake is at position $(x, y)$,
then the square on the right will be at position $(x + 1, y)$.

But this isn’t the whole story: Board~\ref{brd:right-square:wrapping}
shows that if the snake is on the rightmost column, the square on the right
is going to wrap around to be on the leftmost column.

\begin{board}
\begin{subfigure}{.45\linewidth}
    \begin{tabular}{l|l|l|l|l}
      … & $x-1$ & $x$              & $x + 1$            & … \\\hline
  $y-1$ &       &                  &                    &   \\\hline
  $y$   &       & $\mathbf{(x,y)}$ & $\mathbf{(x+1,y)}$ &   \\\hline
  $y+1$ &       &                  &                    &   \\\hline
      … &       &                  &                    & … \\
    \end{tabular}
\caption{Coordinate of the square to the right (ignoring wrapping).}
\label{brd:right-square:normal}
\end{subfigure}
\hfill
%
\begin{subfigure}{.45\linewidth}
< make_board([
    '.....',
    '*...A',
    '.....',
]) >
\caption{%
    The board wraps around,
    so the square to the right of our snake $(4, 1)$
    is the apple $(0, 1)$.
}
\label{brd:right-square:wrapping}
\end{subfigure}

\caption{Finding the square to the right.}
\label{brd:right-square}
\end{board}

Fortunately for us, there’s an easy way of ‘wrapping’ around in Python,
which is the modulo operator (\%). The modulo operator returns the
\emph{remainder} when you divide two numbers.
\begin{minted}{pycon}
>>> 3 % 8
3
>>> 7 % 8
7
>>> 8 % 8
0
>>> 9 % 8
1
>>> for i in range(20):
...   print i % 8,
... 
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3
\end{minted}

\newcommand\mod{\,\%\,}

% TODO: how do we get the width and height of the board?

Looking back at Board~\ref{brd:right-square:wrapping}, we need to wrap the x
coordinate back to $0$ when $x + 1 = width$,
so we need $(x + 1) \mod width$.
Taking this to a more general level, imagine we need to get the cell where
the x coordinate is shifted by $dx$
and the y coordinate is shifted by $dy$.
For example, we might want to get the cell diagonally adjacent on the bottom
left: it’s one square to the left, $dx = -1$ and one square down $dy = 1$.
Don’t forget that moving right or down means adding
and moving left or upwards means subtracting!
Back to our general case, our new cell is going to be at the position
$((x + dx) \mod width, (y + dy) \mod height)$.

Don’t worry if you didn’t follow the general case there, you just need to
remember that the cell to the right is at $((x + 1) \mod width, y)$.
We then need to look \emph{in the board} at that position to see what’s in that
cell.
Remember that our board is a list of rows (stacked vertically),
and each row is a list of cells (stacked horizontally).
So we need to first find the right row, which we will do by using the y
coordinate: \py|board[y]|.
Then we need to find the right cell in the row, using the x coordinate:
\py|board[y][(x + 1) % width]|.

We’re almost at the end: all we need to do is build up a list of each cell we
can move into. We know that we can move into cells which are
empty (represented by a full stop)
or have an apple (represented by an asterisk) in them,
so we’ll test for that.
Take a moment to write out the code we’ve managed to build so far, hopefully
you’ll end up with something very close to what I’ve got below.
Then you just need to add the other directions (left, up and down), and you’re
done.

\begin{pythoncode}
from random import choice

def bot(board, position):
    x, y = position
    height = len(board)
    width = len(board[0])

    valid_moves = []

    right = board[y][(x + 1) % width]
    if right == '.' or right == '*':
        valid_moves.append('R')

    return choice(valid_moves)
\end{pythoncode}

If you’re really stuck, or want to check your solution, here’s my solution:
\pythonfile{random_avoid.py}