The most likely number of turns is 1, in my interpretation of the rules at least. It's a crowded board, but 1 and 2 are neck-and-neck.
Here's the distribution from a simulation with ten million runs:
1 turns: 4837276
2 turns: 4774137
3 turns: 336992
4 turns: 42760
5 turns: 6879
6 turns: 1488
7 turns: 334
8 turns: 101
9 turns: 10
10 turns: 17
11 turns: 4
12 turns: 1
13 turns: 1
And here's the code (in Scala), in case anyone wants to play with it.
object FiftyBots {
import scala.util.Random
import scala.math._
case class Bot(var x: Int, var y: Int) {
var alive = true
var backwards = 16
val ax = new Array[Int](4)
val ay = new Array[Int](4)
def out(xa: Int, ya: Int): Boolean = xa < 0 || xa > 7 || ya < 0 || ya > 7
def mv(n: Int, a: Array[Int], b: Array[Int], i: Int) {
val x = signum(n)
a(i+1) = a(i) + x
b(i+1) = b(i)
if (n-x != 0) mv(n-x, a, b, i+1)
}
def pick(r: Random) {
var choice = r.nextInt(16)
while (choice == backwards) choice = r.nextInt(16)
val (a1, a2) = if ((choice&1) != 0) (ax, ay) else (ay, ax)
val (d1, d2) = if ((choice&2) != 0) (2, 1) else (1, 2)
val s1 = if ((choice&4) != 0) 1 else -1
val s2 = if ((choice&8) != 0) 1 else -1
ax(0) = x
ay(0) = y
mv(d1*s1, a1, a2, 0)
mv(d2*s2, a2, a1, d1)
if (out(ax(3), ay(3))) pick(r)
else backwards = choice ^ 0xF
}
def step(i: Int) { if (alive) { x = ax(i); y = ay(i) } }
}
class Board(r: Random) {
val xs = Array.fill[Bot](8, 8)(null)
val ts = Array.fill[Bot](8, 8, 4)(null)
def wipe(a: Array[Bot]) { var i = 0; while (i < a.length) { a(i) = null; i += 1 } }
def ins(a: Array[Bot], b: Bot) { var i = 0; while (a(i) != null) i += 1; a(i) = b }
def every[A](f: (Int, Int) => A) {
for (x <- 0 until 8; y <- 0 until 8) f(x,y)
}
def everyBot[A](f: Bot => A) {
every{ (x,y) => if (xs(x)(y) != null) f(xs(x)(y)) }
}
def ready {
var n = 64
var m = 50
every{ (x,y) =>
xs(x)(y) = if (r.nextInt(n) < m) { m -= 1; Bot(x,y) } else null
n -= 1
}
}
def move: Int = {
everyBot( _.pick(r) )
for (i <- 1 to 3) {
var bump = true
while (bump) {
bump = false
every{ (x,y) => wipe(ts(x)(y)) }
everyBot{ b =>
b.step(i)
ins(ts(b.x)(b.y), b)
}
every{ (x,y) =>
if (ts(x)(y)(1) != null) {
var k = 0
while (k < 4 && ts(x)(y)(k) != null) {
ts(x)(y)(k).step(i-1)
ts(x)(y)(k).alive = false
bump = true
k += 1
}
}
}
}
}
var n = 0
everyBot{ b => if (b.alive) n += 1 }
n
}
override def toString = xs.map(y => y.map{_ match {
case null => '.'; case b if b.alive => '@'; case _ => 'X'
}}.mkString).mkString("\n")
}
def main(args: Array[String]) {
val n = args(0).toInt
val N = args(1).toInt
(0 until N).par.map{ _ =>
val b = new Board(new Random())
(0 until n).map{ _ => b.ready; var i = 1; while (b.move > 0) i += 1; i }
}.seq.reduce(_ ++ _).
groupBy(identity).mapValues(_.length).toList.sortBy(_._1).
map{ case (n,m) => f"$n%2d turns: $m%7d" }.
foreach(println)
}
}
Edit: the first argument is the number of boards to run per thread, and the second is the number of threads. So if you are on a 4-core system and want a million boards run as fast as possible:
scala FiftyBots 250000 4