diff options
Diffstat (limited to 'docs/random_avoid.tex')
| -rw-r--r-- | docs/random_avoid.tex | 167 |
1 files changed, 167 insertions, 0 deletions
diff --git a/docs/random_avoid.tex b/docs/random_avoid.tex new file mode 100644 index 0000000..90ac183 --- /dev/null +++ b/docs/random_avoid.tex @@ -0,0 +1,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} + |