<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/the-knight-on-an-infinite-chessboard-puzzle-efficient-simulation-in-r/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://varianceexplained.org/r/knight-chess/"> Variance Explained</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><strong>Previously in this series</strong>:</p>
<ul>
<li><a rel="nofollow" href="http://varianceexplained.org/r/boarding-pass-simulation/" target="_blank">The “lost boarding pass” puzzle</a></li>
<li><a rel="nofollow" href="http://varianceexplained.org/r/board-game-simulation/" target="_blank">The “deadly board game” puzzle</a></li>
</ul>
<p>I’ve recently been enjoying <a rel="nofollow" href="https://www.amazon.com/Riddler-Fantastic-Puzzles-FiveThirtyEight/dp/039360991X" target="_blank">The Riddler: Fantastic Puzzles from FiveThirtyEight</a>, a wonderful book from 538’s Oliver Roeder. Many of the probability puzzles can be productively solved through Monte Carlo simulations in R.</p>
<p>Here’s one that caught my attention:</p>
<blockquote>
<p>Suppose that a knight makes a “random walk” on an infinite chessboard. Specifically, every turn the knight follows standard chess rules and moves to one of its eight accessible squares, each with probability 1/8.</p>
</blockquote>
<blockquote>
<p>What is the probability that after the twentieth move the knight is back on its starting square?</p>
</blockquote>
<p>In this post I’ll show how I’d answer this question through simulation in R, with an eye on keeping the simulation fast and interpretable. As in many of my posts, we’ll take a “tidy approach” that focuses on the dplyr, tidyr, and ggplot2 packages.</p>
<h3>Simulating a knight’s moves</h3>
<p>The first question is how we can simulate a knight’s move randomly. There are eight positions that a knight can move to, following the rule of “two spaces in one direction, one in the other”.</p>
<p><img alt="center" src="https://i0.wp.com/varianceexplained.org/figs/2018-12-10-knight-chess/unnamed-chunk-1-1.png?w=456" data-recalc-dims="1"></p>
<p>It helps to break each possible move into its X and Y components:</p>
<ul>
<li>X = 2, Y = 1</li>
<li>X = 2, Y = -1</li>
<li>X = 1, Y = 2</li>
<li>X = 1, Y = -2</li>
<li>X = -1, Y = 2</li>
<li>X = -1, Y = -2</li>
<li>X = -2, Y = 1</li>
<li>X = -2, Y = -1</li>
</ul>
<p>Notice that the moves are always made up of <em>one 2 and one 1</em>, and that either, both, or neither can be negative.</p>
<p>The first step of the simulation (getting a 1 and a 2) can be done as follows for a single simulation:</p>
<figure>
<pre><code data-lang="r"><span># Random number between 1 and 2</span><span>
</span><span>move_x</span><span> </span><span>&lt;-</span><span> </span><span>sample</span><span>(</span><span>2</span><span>,</span><span> </span><span>1</span><span>)</span><span>
</span><span># If x is 2, y is 1, and vice versa</span><span>
</span><span>move_y</span><span> </span><span>&lt;-</span><span> </span><span>3</span><span> </span><span>-</span><span> </span><span>move_x</span><span>
</span><span>c</span><span>(</span><span>move_x</span><span>,</span><span> </span><span>move_y</span><span>)</span></code></pre>
</figure>
<figure>
<pre><code data-lang="text">## [1] 1 2</code></pre>
</figure>
<p>How about letting either number be negative? Well, <code>sample(c(1, -1))</code> can get us a value that’s either 1 or -1, so we can multiply that by each.</p>
<figure>
<pre><code data-lang="r"><span>move_x</span><span> </span><span>&lt;-</span><span> </span><span>sample</span><span>(</span><span>2</span><span>,</span><span> </span><span>1</span><span>)</span><span> </span><span>*</span><span> </span><span>sample</span><span>(</span><span>c</span><span>(</span><span>1</span><span>,</span><span> </span><span>-1</span><span>),</span><span> </span><span>1</span><span>)</span><span>
</span><span>move_y</span><span> </span><span>&lt;-</span><span> </span><span>(</span><span>3</span><span> </span><span>-</span><span> </span><span>abs</span><span>(</span><span>move_x</span><span>))</span><span> </span><span>*</span><span> </span><span>sample</span><span>(</span><span>c</span><span>(</span><span>1</span><span>,</span><span> </span><span>-1</span><span>),</span><span> </span><span>1</span><span>)</span><span>
</span><span>c</span><span>(</span><span>move_x</span><span>,</span><span> </span><span>move_y</span><span>)</span></code></pre>
</figure>
<figure>
<pre><code data-lang="text">## [1]  2 -1</code></pre>
</figure>
<p>Now that we can sample a single move, we can try sampling many moves (say, 20) by adding <code>20, replace = TRUE</code> to each.</p>
<figure>
<pre><code data-lang="r"><span>move_x</span><span> </span><span>&lt;-</span><span> </span><span>sample</span><span>(</span><span>2</span><span>,</span><span> </span><span>20</span><span>,</span><span> </span><span>replace</span><span> </span><span>=</span><span> </span><span>TRUE</span><span>)</span><span> </span><span>*</span><span> </span><span>sample</span><span>(</span><span>c</span><span>(</span><span>1</span><span>,</span><span> </span><span>-1</span><span>),</span><span> </span><span>20</span><span>,</span><span> </span><span>replace</span><span> </span><span>=</span><span> </span><span>TRUE</span><span>)</span><span>
</span><span>move_y</span><span> </span><span>&lt;-</span><span> </span><span>(</span><span>3</span><span> </span><span>-</span><span> </span><span>abs</span><span>(</span><span>move_x</span><span>))</span><span> </span><span>*</span><span> </span><span>sample</span><span>(</span><span>c</span><span>(</span><span>1</span><span>,</span><span> </span><span>-1</span><span>),</span><span> </span><span>20</span><span>,</span><span> </span><span>replace</span><span> </span><span>=</span><span> </span><span>TRUE</span><span>)</span><span>
</span><span>move_x</span></code></pre>
</figure>
<figure>
<pre><code data-lang="text">##  [1]  2  1  1  1 -2  2 -2  1  2 -2 -1  1 -2 -2  2 -2  1 -2 -2 -2</code></pre>
</figure>
<figure>
<pre><code data-lang="r"><span>move_y</span></code></pre>
</figure>
<figure>
<pre><code data-lang="text">##  [1]  1 -2 -2 -2  1  1  1 -2 -1 -1  2 -2 -1 -1 -1 -1 -2 -1  1 -1</code></pre>
</figure>
<p>Now that we’ve figured out how to simulate chess moves, we can go ahead with our simulation of positions.</p>
<h3>Tidy simulation</h3>
<p>The <code>crossing()</code> function from tidyr is wonderful for setting up Monte Carlo simulations. It creates a <code>tbl_df</code> with every combination of the inputs (it’s similar to the built-in <code>expand.grid</code>).</p>
<p>In this simulation we’ll want some number of trials and some number of turns. If we wanted to generate 3 trials that each included 3 chess turns, we could do:</p>
<figure>
<pre><code data-lang="r"><span>crossing</span><span>(</span><span>trial</span><span> </span><span>=</span><span> </span><span>1</span><span>:</span><span>3</span><span>,</span><span>
</span><span>turn</span><span> </span><span>=</span><span> </span><span>1</span><span>:</span><span>3</span><span>)</span></code></pre>
</figure>
<figure>
<pre><code data-lang="text">## # A tibble: 9 x 2
##   trial  turn
##   </code></pre></figure>