Users:Yendor/Spiral Search Example

I follow Marvl's Spiral Search method for marble quarrying. It is a very efficient search strategy. Unfortunately, Marvl's guide combines the search method, an explanation of its efficiency, and a probabilistic analysis of the slate cost into one massive document.

This page gives a much simpler explanation of spiral search, and a few specific example searches from Tale 6.

Spiral Search (The basics)

We start with the two people (30, 30) units away from each other. For maximum efficiency, both can look for different types of marble, but the explanation here assumes that player 1 is the only one prospecting. Initially, players alternate moving 60 coordinates at a time (so each time player 1 and player 2 are (30, 30) coordinates away). Once there is an initial spot with a two-slate break, then the spiral search comes into play. The key idea is that player 2 moves only when there is a two-slate break; player 2 will move 1/2 way to player 1. Player 1 will move at a right angle to whichever direction player 2 moved and try again -- so if Player 2 moves SE, Player 1 should move NE. In this way, players alternate between being diagonally away from each other and being in a straight line from each other. The search ends when players are standing directly next to each other on a (1,1) coordinate boundary.

There is one small quirk: 32 coordinates is too far away to prospect. Players are initially 30 units away, and the first move is 14 coordinates instead of 15. This gives a nice power-of-2 distance.

The table below shows the correct distances between players at each step:

Start	Step 1	Step 2	Step 3	Step 4	Step 5	Step 6	Step 7	Step 8	Step 9	Step 10
(30, 30)	(0, 30)	(16, 16)	(0, 16)	(8, 8)	(0, 8)	(4, 4)	(0, 4)	(2, 2)	(0, 2)	(1, 1)

The explanation can be hard to see in abstract, so here are a few example prospecting runs. Note that if there is only one slate break, player 1 is the only person to move; if there is a two-slate break, player 2 moves 1/2 way to player 1, and player 1 then moves at right-angles to the next step size.

Example Quarry 1

Initial break happens with P1 at 1800, 3300, and P2 at 1770, 3330
P2 moves 1/2 way, to 1784, 3316 (SE). Player 1 moves NE to 1814, 3316
No break, so try 1784, 3346
P2 moves 1/2 way to 1784, 3330 (N). Player 1 moves E to 1800, 3346
No break, so try 1800, 3314. Then 1768, 3314
P2 moves 1/2 way to 1776, 3322 (SW). Player 1 moves NW to 1768, 3322
P2 moves 1/2 way to 1772, 3322 (W). Player 1 moves S to 1768, 3318
No break, so try 1768, 3326, then 1776, 3326.
P2 moves 1/2 way to 1774,2224 (NE). Player 1 moves SE to 1778, 3324 
P2 moves 1/2 way to 1776, 2224 (E). Player 1 moves S to 1778, 3322
P2 moves 1/2 way to 1777, 3323 (SE). Player 1 moves SW to 1777, 3321
P2 moves 1/2 way to 1777, 3322  (S). Player 1 moves W to 1776, 3321
No break so try 1776, 3323
Plant quarry! (24 slate used)

Example Quarry 2

 Initial two-break at 2030, 3340 & 2000, 3370
 P2 moves NW to 2016, 3354. P1 moves NE to 2016, 3384
 No break so try 2046, 3354, then 2016, 3324 and  1986, 3354
 P2 moves W to 2002, 3354. P1 moves N to 1986, 3370
 P2 moves NW to 1994, 3362. P1 moves NE to 1994, 3374
 P2 moves N to 1994, 3370. P1 moves E to 2002, 3378
 No break, so try 1986, 3378 then 1986, 3362 and 2002, 3362
 P2 moves SE to 1998, 3366. P1 moves SW to 1998, 3358
 No break so try 1990, 3366 then 1998, 3374
 P2 moves N to 1998, 3370. P1 moves E to 2002, 3374
 No break so try 2002, 3366
 P2 moves SE to 2000, 3368. P1 moves SW to 2000, 3364
 P2 moves S to 2000, 3366. P1 moves E to 2002, 3364
 No break so try 2002, 3368
 P2 moves to 2001, 3367 (NE). P1 moves SE to 2003, 3367
 No break so try 2001, 3365 then 1999, 3367
 P2 moves to 2000, 3367 (W). P1 moves N to 1999, 3368
 Plant Quarry!  (34 slate used)