diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/closest_apple.py | 60 | ||||
| -rw-r--r-- | docs/closest_apple.tex | 13 | ||||
| -rw-r--r-- | docs/look_ahead.tex | 9 | ||||
| -rw-r--r-- | docs/random_avoid.py | 26 | ||||
| -rw-r--r-- | docs/random_avoid.tex | 120 | ||||
| -rw-r--r-- | docs/tutorial.tex | 13 |
6 files changed, 239 insertions, 2 deletions
diff --git a/docs/closest_apple.py b/docs/closest_apple.py new file mode 100644 index 0000000..8f8c560 --- /dev/null +++ b/docs/closest_apple.py @@ -0,0 +1,60 @@ +DIRECTIONS = { + 'L': (-1, 0), + 'U': (0, -1), + 'R': (1, 0), + 'D': (1, 0), +} + +def closest_apple_bot(board, position): + x, y = position + height = len(board) + width = len(board[0]) + + # todo contains the squares we need to explore + todo = [] + # done contains the squares we've already explored + done = set() + + # for each initial direction + for direction in DIRECTIONS: + dx, dy = DIRECTIONS[direction] + # find the new position + nx = (x + dx) % width + ny = (y + dy) % height + # add to todo and done + todo.append((nx, ny, direction)) + done.add((nx, ny)) + + while todo: + # take the first item in todo + x, y, direction = todo.pop(0) + + cell = board[y][x] + + # if we've reached an apple, we've found the shortest path + # and direction is the right way to go + if cell == '*': + return direction + + # if we can't move into this cell, go to the next square to explore + if cell != '.': + continue + + # at this square, we can go any direction, + # as long as it's not in our done set + for dx, dy in DIRECTIONS.values(): + nx = (x + dx) % width + ny = (y + dy) % height + + if (nx, ny) not in done: + # we haven't visited this square before, + # add it to our list of squares to visit + # note that the third item here is the direction we initially + # took to get to this square + todo.append((nx, ny, direction)) + done.add((nx, ny)) + + # if we get here, there are no apples on the board, + # so we'll just move up. + return 'U' + diff --git a/docs/closest_apple.tex b/docs/closest_apple.tex new file mode 100644 index 0000000..36b7382 --- /dev/null +++ b/docs/closest_apple.tex @@ -0,0 +1,13 @@ +\section{Closest apple} + +One interesting bot we can write is one which always moves towards the closest +apple. Both the idea and the coding are a little tricky, but see if you can +handle it. In order to find the closest apple, we actually want to know +the \emph{shortest path} to the apple, and when we know that, the first step in +that path is the direction we need to move in. + +To find the shortest path, we need to use an algorithm called +\emph{breadth first search} (BFS). +% TODO: description of the algorithm + +\pythonfile{closest_apple.py} diff --git a/docs/look_ahead.tex b/docs/look_ahead.tex new file mode 100644 index 0000000..d5c37c6 --- /dev/null +++ b/docs/look_ahead.tex @@ -0,0 +1,9 @@ +\section{Look ahead} + +By now you’re probably itching to try out some of your own ideas about how to +make a good bot. Now’s a great time to take a break from following my detailed +instructions and just play around with some ideas. +Here’s an idea to get you started: our \texttt{random\_avoid\_bot} only looked +one square ahead, try making a bot which looks two squares ahead and chooses the +direction with the most free space. + diff --git a/docs/random_avoid.py b/docs/random_avoid.py new file mode 100644 index 0000000..bf08eef --- /dev/null +++ b/docs/random_avoid.py @@ -0,0 +1,26 @@ +from random import choice + +def random_avoid_bot(board, position): + x, y = position + height = len(board) + width = len(board[0]) + + valid_moves = [] + + left = board[y][(x - 1) % width] + if left == '.' or left == '*': + valid_moves.append('L') + + right = board[y][(x + 1) % width] + if right == '.' or right == '*': + valid_moves.append('R') + + up = board[(y - 1) % height][x] + if up == '.' or up == '*': + valid_moves.append('U') + + down = board[(y + 1) % height][x] + if down == '.' or down == '*': + valid_moves.append('D') + + return choice(valid_moves) diff --git a/docs/random_avoid.tex b/docs/random_avoid.tex index 75d5a3a..042c947 100644 --- a/docs/random_avoid.tex +++ b/docs/random_avoid.tex @@ -1,3 +1,5 @@ +%%- 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.} @@ -45,3 +47,121 @@ 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: \pyinline|board[y]|. +Then we need to find the right cell in the row, using the x coordinate: +\pyinline|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} + diff --git a/docs/tutorial.tex b/docs/tutorial.tex index 951c7de..e67b824 100644 --- a/docs/tutorial.tex +++ b/docs/tutorial.tex @@ -14,12 +14,14 @@ \DeclareCaptionSubType{board} \usepackage{minted} +\usemintedstyle{tango} \newmint[pyinline]{python}{} +\newminted{python}{} \newmintedfile{python}{} -\usemintedstyle{tango} \setmainfont{Linux Libertine O} +\setmonofont[AutoFakeBold]{Inconsolata} \setlength\parskip{2ex} \setlength\parindent{0mm} @@ -37,11 +39,18 @@ \input{introduction.tex} -%\pagebreak \input{firstbot.tex} \input{random_simple.tex} +% this section is rather long, +% perhaps take an intermission to explain the board +% and getting width, height +% and modulo properly? \input{random_avoid.tex} +\input{look_ahead.tex} + +\input{closest_apple.tex} + \end{document} |