As luck would have it I won the Cubido C# Pirates Programming Competition for the best Battleship Game Algorithm last week, and took home an XBox 360 Premium Edition as first prize.
In general my algorithm pretty much stayed the same since I last blogged about it a while ago, but some fine-tuning brought the average winning shot count down to about 38 (compared to 39 shots achieved by the initial version) - that is the number of shots to sink five ships of size 2, 3 (2 times), 4 and 5 on a 10x10 battlefield.
Tuning was absolutely necessary as 17 algorithms scored under 39 shots at the end (around 80 players took part over all). I had submitted several slightly different versions, hence the victory was manifold. My best algorithm variation attained 38.19 shots, with the closest competitor finishing at 38.33.
The final competition was a public event (a big thank you goes to the kind folks at Cubido), and many contestants dropped by at the Cubido Headquarters and watched the progress on a large scoreboard (which was also available online). The battle lasted nearly four hours. 10,000 games had been played eventually (each algorithm was required to finish 10,000 identical battlefields). With results so close this large number was a must to avoid any "accidental winner", a winner that would have benefited by certain random number distributions (as a matter of fact during the preliminary rounds, which only consisted of 50 games each, my algorithms scored at between 34.5 and 40.5 shots, so that's quite a spread - a spread that was caused both by the random distribution of ships on the battlefield, as well as the algorithm's internal randomizer, which is applied when choices are evaluated as being equal otherwise).
As I have promised before, I am going to talk about the ideas behind the algorithm and post the complete sourcecode over the next few days.
Posts
