RPCFN: Broadsides (#7)

by Satish Talim on February 23, 2010

Ruby Programming Challenge For Newbies

RPCFN: Broadsides (#7)

By James Edward Gray II

About James Edward Gray II

James Edward Gray IIJames Edward Gray II was called into the principal’s office in high school for writing a black jack program on his calculator and beaming it to all the math students almost 20 years ago. He’s been tinkering with little code challenges ever since. After discovering Ruby, he formalized this process by creating the Ruby Quiz. Though he no longer runs those challenges, he’s glad to see that the spirit lives on in projects like the RPCFN.

James has this to say about the challenge:

The only way to learn to program is to have about 5,000 arguments with a compiler, in my opinion. How you get your time in is up to you, but I would rather do it with fun little exercises like the RPCFN than under more stressful circumstances. Given that, I tend to favor the game problems as they distract me from the learning I am really trying to accomplish and allow me to have more fun.

Our Awesome Sponsors

This monthly programming challenge is co-sponsored by 1st Easy Limited and Backup My App.

UK based Passenger Hosting

1st Easy Limited are delighted to have been given the opportunity to support the work of Satish Talim and his team at RubyLearning.

Taking part in the Ruby Programming Challenge? You’re welcome to take advantage of the free Ruby on Rails hosting trials that 1st Easy offer: simply register your details, and a full-featured account is yours to do with as you please for one month. Once the trial is over, you can transfer your work to a paid account, or walk away with no questions asked!

Backup My App

Backup My App is an automatic backup service for Ruby on Rails applications. You simply install the plugin to your Rails application and they handle the rest of the process. They store backup history for several weeks and you can restore any of them automatically. Try out their 1 GB plan for free. Backup My App has co-sponsored this challenge and is proud to make this contribution to the Ruby community.

Prizes

  • The participant with the best Ruby solution (if there is a tie between answers, then the one who posted first will be the winner) will be awarded any one of PeepCode’s Ruby on Rails screencasts and a free 10 GB account for a year from Backup My App.
  • From the remaining working Ruby solutions, three participants would be selected randomly and each one would be awarded any one of Pragmatic’s The Ruby Object Model and Metaprogramming screencasts.
  • All the participants in this challenge (except the participant with the best Ruby solution) will get a free 5 GB account for 6 months from Backup My App.

The four persons who win, can’t win again in the next immediate challenge but can still participate.

The Ruby Challenge

RPCFN

The Challenge

The entire challenge details are available at: http://github.com/JEG2/broadsides.

How to Enter the Challenge

Read the Challenge Rules. By participating in this challenge, you agree to be bound by these Challenge Rules. It’s free and registration is optional. You can enter the challenge just by posting the following as a comment to this blog post:

  1. Your name:
  2. Country of Residence:
  3. GIST URL of your Solution (i.e. Ruby code) with explanation and / or test cases:
  4. Code works with Ruby 1.8 / 1.9 / Both:
  5. Email address (will not be published):
  6. Brief description of what you do (will not be published):

Note:

  • As soon as we receive your GIST URL, we will fork your submission. This means that your solution is frozen and accepted. Please be sure that is the solution you want, as it is now recorded in time and is the version that will be evaluated.
  • All solutions posted would be hidden to allow participants to come up with their own solutions.
  • You should post your entries before midnight of 31st Mar. 2010 (Indian Standard Time). No new solutions will be accepted from 1st Apr. onwards.
  • On 3rd Apr. 2010 all the solutions will be thrown open for everyone to see and comment upon.
  • The winning entries will be announced on this blog before 10th Apr. 2010. The winners will be sent their prizes by email.

More details on the RPCFN?

Please refer to the RPCFN FAQ for answers to the following questions:

Donations

RPCFN is entirely financed by RubyLearning and sometimes sponsors, so if you enjoy solving Ruby problems and would like to give something back by helping with the running costs then any donations are gratefully received.

Click here to lend your support to: Support RubyLearning With Some Love and make a donation at www.pledgie.com !

Acknowledgements

Special thanks to:

  • James Edward Gray II.
  • Sponsors 1st Easy Limited and Backup My App.
  • GitHub, for giving us access to a private repository on GitHub to store all the submitted solutions.
  • The RubyLearning team, namely Jeff Savin (Canada), Peter Crawford (Italy), Satoshi Asakawa (Japan) and Victor Goff III (USA).

Questions?

Contact Satish Talim at satish [dot] talim [at] gmail.com OR if you have any doubts / questions about the challenge (the current problem statement), please post them as comments to this post and the author will reply asap.

The Participants

There are two categories of participants. Some are vying for the prizes and some are participating for the fun of it.

In the competition

  1. Dmitriy Nagirnyak, Australia – declared winner (best solution)
  2. Nithin Bekal, India – declared winner (randomly selected)
  3. Antonio Trogi, Canada – declared winner (randomly selected)
  4. Phillip Curry, China – declared winner (randomly selected)
  5. Benoit Daloze, Belgium – declared winner (randomly selected)

Just for Fun

  1. Satoshi Asakawa, Japan

The Winners

Winners

Congratulations to the winners of this Ruby Challenge. They are:

Previous Challenge

RPCFN: Fair Distribution (#6) by John Trupiano.

Note: All the previous challenges, sponsors and winners can be seen on the Ruby Programming Challenge for Newbies page.

Update

  • This challenge is now closed.
  • The (#8) challenge by Jamie van Dyke, UK is scheduled for 9th Apr. 2010.

Technorati Tags: , , , , ,

Posted by Satish Talim

{ 50 comments… read them below or add one }

Rusty February 23, 2010 at 11:04 am

Any reason an “INFO SUNK 3:A1:H” type message is not included? Most versions I have seen include this information.

Reply

James Edward Gray II February 23, 2010 at 7:36 pm

Yes. I gave you a way to tell if a ship has been sunk. It’s just not quite that easy.

Reply

Rusty February 24, 2010 at 6:48 am

It is possible to determine when and if one or more enemy ships have been sunk, but in nearly all cases it is not possible to determine the length or precise locations of the sunken ships thus making that information of little use. :-/

Reply

James Edward Gray II February 24, 2010 at 8:56 am

My opinion is that adds to the strategy aspect of the game. Hiding ships next to each other to fool a player into thinking they sunk a bigger target is definitely an option, right? Then they need to do their due diligence to be sure.

Reply

Dmitriy Nagirnyak February 25, 2010 at 3:05 pm

Can the ships touch boards of each other, either vertically/horizontally or on the diagonal?

In the classical game I used to play it was not allowed.
But the example provided on the GitHub allows this:
`SHIPS 5:A1:H 4:A2:H 3:A3:H 3:A4:H 2:A5:V`

Which means that the whole left top corner is occupied and it is not possible to determine which ship is sunk as there are number of possibilities.

Reply

James Edward Gray II February 26, 2010 at 11:10 am

Ships are allowed to touch on the edges. I didn’t say telling which ships was sunk is easy, just possible. :) You may refine your view of what has been sunk as play continues.

Reply

Dmitriy Nagirnyak February 27, 2010 at 7:25 am

“just possible”
It is not always possible. Look at this:

is this 2 + 3, or just 5?
XXXXX

is this 3 + 3 + 2; 4 + 3/2 + [other part] and there are even more possibilities.
XXXX
XXXX

I just cannot mathematically prove the ability to determine which ships has been sunk.

Refining the the results later in the game is the only one possibility, which will result in the correct figures only when with the last hit.

As a result you cannot always rely on the results of such statistics if there are ships touching each other.

Reply

James Edward Gray II February 27, 2010 at 10:48 am

When you find the length 5, you know it was the length 2 plus the length 3. :)

I’m pretty much joking of course, but I seriously doubt this wrecks our ability to build strategic players. Perhaps I am wrong though.

Reply

Aldric Giacomoni February 25, 2010 at 11:55 pm

Thanks, James – I’ve been wanting to try and build an AI for a while but never had a good reason to. You even provided us with a sandbox! Now, let’s see… Class Skynet; def initialize; take_over_world; end; end;

.. Uh-oh.

Reply

James Edward Gray II February 26, 2010 at 11:11 am

I’m glad you like it. I played with a Python server and liked it, so I ported it to Ruby and lightened the dependencies.

Reply

Satish Talim February 27, 2010 at 6:48 am

Internally, there has been some discussion on the difficultly of the recent Ruby Challenges and that the last three months’ challenges presented a problem that was difficult to grasp or was highly elaborate.

JEG II selected this problem because he feels that the problem holds a lot of educational value for beginners:

  • It works with basic I/O practices, reading and writing in Ruby.
  • It shows a dirt simple form of process communication.
  • It furthers the understanding of concepts like what CGI is.
  • It requires you to implement a documented protocol.
  • It needs some basic parsing techniques (focusing on String manipulation).
  • It allows you to work with simple data structures (tracking the game).

That plus the immediate visual feedback combine to make it a strong teaching tool, in his opinion.

HINT: Also, JEG II has been kind enough to give some hints on how to write the solution to the given problem:

  • While it’s definitely possible to write complex AI’s for this problem, it’s far easier to make simple incremental progress and I would recommend that approach.
  • For example, start by copying the included random player. It already has at least half of the parser and it should be easy to expand on the same strategy to handle the rest of the inputs.
  • Keep the random firing with one small change: after you hit, fire into the surrounding areas to find the rest of the ship. Just this much will make your player better and it only takes a few lines of code.
  • From there, a good improvement is to stop firing randomly to locate ships. Instead, it’s better to rate a square on the likelihood that it holds a ship and fire at the more likely squares. The middle is more likely in the beginning than the edges, for example, because there is more room and more ways to layout the various ship sizes.
  • If you keep track of your hits and misses, it’s pretty easy to section of the rest of the board along similar lines. By this point, you will notice a dramatic improvement in your player, and we’re still not even worrying about the opponent yet.

Reply

Dennis Sutch February 28, 2010 at 10:04 pm

Interesting challenge! Can entrants post multiple solutions?

Reply

James Edward Gray II March 1, 2010 at 6:37 am

Please do.

Reply

Dmitriy Nagirnyak March 2, 2010 at 12:21 pm

How to submit a player that consists of multiple files?

Reply

James Edward Gray II March 2, 2010 at 9:35 pm

I think I would rather that we keep individual players in a single file, if at all possible. (See the file naming rules in the task description.)

If you want to submit multiple players, just make separate submissions for each one.

Reply

suraj dhakankar March 4, 2010 at 4:09 pm

Following is my observation
1 There are total 5 ships
2 Total chances for hitting for the first player is 5+1=6
3 When ANY ONE ship out of 5 is sunk, total number of chances reduce by 2 i.e. it becomes 4
4 For subsequent loss of a ship, a chance is reduced.

Am I correct?
Any comment on 3rd point.

Reply

James Edward Gray II March 4, 2010 at 10:02 pm

Wouldn’t the chance of hitting ships be related to the board size and amount of that space they take up?

Reply

Dmitriy Nagirnyak March 5, 2010 at 6:31 am

…and the number of shots taken too (to be precise number of unique shots).

Reply

Suraj Dhakankar March 5, 2010 at 4:31 pm

I think I was not clear on my observation.
Let me rephrase the sentences

1. There are total 5 ships
2. Number of shots that the first player gets to hit opponent is 6
3. When ANY ONE ship out of 5 is sunk of a player, the player would get 6-2=4 shots to hit the opponent on his turn
4. For a subsequent loss of a ship one shot for the player is reduced
i.e. if the player has 3 ships on the board he would get only 3 shots to hit opponent.

Is this correct?

Reply

James Edward Gray II March 5, 2010 at 8:12 pm

Not quite. You only lose 2 shots if the length 5 ship is sunk. All other ships subtract 1 shot as they are sunk.

Reply

Dmitriy Nagirnyak March 6, 2010 at 2:14 pm

Solution (#1):

Dmitriy Nagirnyak, Australia
Solution: https://gist.github.com/97a9a2dc128b96a1e448 now forked
Code works with Ruby 1.8.7. Not 1.8.6. Possibly with 1.9.

Reply

James Edward Gray II April 5, 2010 at 3:09 pm

This is a very strategic player. It first places ships using some simple randomization. It looks like this process is designed to favor more strategic positions, though I am just guessing about that.

Shooting is where this player really excels though. It begins by using a pre-calculated shot grid to locate ships in the shortest possible amount of shots. It does randomize even this though, with non-damaging changes like rotations and transpositions, so opponent players can’t easily adapt to the shot patterns.

Anytime the player sees that its shot has hit, it prioritizes some more shots near the hit. It tries to do even this strategically, concluding that if it has already seen another hit to the right for example, shooting to the left of the new hit should be a high priority. I do think there may be a minor bug in this logic somewhere though as it will occasionally skip a square near a hit for some reason. You can see this issue in this movie, where it goes hunting for ships again before getting back to making the final shot.

Still, it’s a strong player. Well done Dmitriy.

Reply

Benoit Daloze April 5, 2010 at 8:43 pm

I’m impressed by the result and the lines of codes.
I think the monkey patching in String is not very elegant, (I prefer a Coord class like I did), but it’s clearly quicker to write.

I ran the tournament several times and we clearly get almost the same results (ere/dn): 6/4, 4/6, 5/5, 7/3, 8/2, 6/4, 6/4, 8/2, 10/0, 8/2 => 6.8/3.2
On the full tournament(5 times):
dn_strategic: 50.8
players_ere_x: 49.4
at_basic: 43.2
pc_player: 30
jeg2_sequential: 19.4
jeg2_random: 10
nithinbekal: 5.2

Most of the time, I have the impression the winner is relative to luck, as for searching the last ship it can be quite long, or a player begin to hit first.

Reply

Dmitriy Nagirnyak April 6, 2010 at 6:25 am

Hi Benoit,

I agree that extending a String does not look like being a “clean way” but it just allows to Keep It Simple. If the player would have to expose its interface I wouldn’t do that.

“I have the impression the winner is relative to luck, as for searching the last ship it can be quite long”

I think it IS about the luck, but involves a bit of probability theory. I believe my “ship discovery” strategy allows to quicker find all the ships with minimal shots, at least according to probability theory :)

Though, my player lacks a “professional” strategy to finish off the ships.

Cheers,
Dmitriy.

Reply

Dmitriy Nagirnyak April 6, 2010 at 5:42 am

Hi James,

You have described and understood my solution absolutely correctly. Hope it means my code is easy to understand.

I should also mention that the original code consists of number of files which I just concatenated as it was a requirement to have a single-file player.

I have just pushed the repo with player to git:
http://github.com/jameskayn/broadsides_players

Anyway,
For this particular task I decided not to do any AI and just stick with a KISS principle.

I rather calculated:
- most likely positions to hit at and related variants;
- location of ships I consider to be safer for the player + a bit of variations for the smallest ship to decrease possibility of tracking it by other players (no random generation);
- more common ways of finishing off a ship.

Though, the “finish off” strategy is not the perfect one as you noticed, it represents (what I think is) a more common pattern of locating the ships. It was trade-off between “make sure everything around is dead” and “intelligent guessing of correct ship location”. Anyway, I agree that the strategy has to be improved to assemble the situation you showed in the movie.

Also I have to mention the Challenge was very interesting and required a bit of brain cells to start working :)
Especially, when you don’t know your opponents :)

Cheers,
Dmitriy.

Reply

Nithin Bekal March 13, 2010 at 8:04 pm

Solution (#2):

I’ve posted my solution on gist. The code works with Ruby 1.8, but I haven’t tested it with 1.9.
https://gist.github.com/719275d69f4c6689121d

Reply

James Edward Gray II April 5, 2010 at 3:12 pm

This is a good start on a player that can be iteratively improved. I believe it has a bug in it’s shot logic though that sometimes causes it to shoot at squares it has already targeted. You can see this issue in the movie. I bet this player would improve a lot after that bug is found and fixed.

Reply

Nithin Bekal April 5, 2010 at 3:38 pm

I noticed one problem with it just this morning. The shot logic won’t work unless the player file is called nithin.rb and I accidentally named the gist file nithinbekal.rb. Stupid, stupid me! :(

It was great fun doing this challenge. I couldn’t figure out it shoots already targeted squares. That’s the next challenge for me today. :)

Reply

Nithin Bekal April 5, 2010 at 4:07 pm

Just ran the tournament on my computer and my score went up from 3 to 42 when I used the correct file name. That would have moved me up to 3rd in the tournament. ;-) Another lesson learned on why you shouldn’t hard code stuff into your programs. *sigh*

Reply

Benoit Daloze April 5, 2010 at 8:54 pm

Sure that was a bad idea to hard code:
when /\AINFO SHOTS nithin\b/
=>
when /\AINFO SHOTS #{File.basename(__FILE__,’.rb’)}\b/

Yeah, you got at 2nd-3rd place with this little change.
Nice small entry too.

Reply

phil March 15, 2010 at 4:21 pm

Hey, so I think I’m going to give this round a go. Bit of a ruby newby here but this seems like something my coding can handle.
A few questions though:
Do we get multiple rounds with the same opponent? Or is it one match, winner proceeds?
Also, the server seems set up to allow for variable ship numbers/sizes. Is that going to happen or is it always going to be the same

Thanks
phil

Reply

James Edward Gray II March 15, 2010 at 7:25 pm

The included tournament script makes sure every player plays every other player exactly 10 times. So yes, you face an opponent more than once.

We will not vary the number or size of the ships for this challenge, no.

Reply

Aldric Giacomoni March 16, 2010 at 12:31 am

I’m amazed that no one has posted a solution yet. I’m working on one.. With difficulty because my home machine is down, and it seems the only proper way to work on a netbook is with Vim, so I’m teaching myself that :-)

Reply

James Edward Gray II March 16, 2010 at 6:17 am

We have had a couple of solutions, but we definitely need more. Do send in what you come up with.

Reply

kainage March 17, 2010 at 7:36 am

Solution (#3):

Antonio Trogi, Canada
Original: git://gist.github.com/334815.git
Code works with Ruby 1.8.7
First submission, called at_basic. I may attempt another if time permits.

Reply

James Edward Gray II April 5, 2010 at 3:12 pm

This is another player that uses random shot firing until a ship is located, and then hunts the surrounding squares to sink them. It was average strength for the submissions.

Reply

Aldric Giacomoni March 22, 2010 at 11:47 pm

So.. I’m building a kind of neural-network-type-thingy (it’s the technical term). Once I am done, how on earth do I teach it ? I mean.. Having it play against itself is pretty much the blind leading the blind, isn’t it?
And yet I want to automate it because I sure as heck am not going to sit there and play 100,000 games against my program ;)

Reply

James Edward Gray II March 23, 2010 at 7:28 am

Techniques like evolutionary programming aside, you could build it to play games, score it self (faster wins are better, right?), adjust weights/parameters, and see if it is improving.

I think you could start by having it play a random player. It should at least be able to improve shooting strategies against that. They make a few copies of your AI and hand tune the settings to anything you think sounds like a good idea. That will give it some fresh tactics to learn against.

I hope that gives you some fresh ideas.

Reply

Aldric Giacomoni March 29, 2010 at 10:24 pm

Gives me plenty of ideas. I’m just feeling sad that I’ve been so busy lately, I may have to submit unfinished code (as in, the actual AI is not implemented, but I think just about everything else is).
Maybe we can ask people to finish my code for another RPCFN — that’ll surely be a great example of how to pick up someone else’s code ;-)

Reply

Aldric Giacomoni March 31, 2010 at 5:54 pm

Well, here’s my very very incomplete entry.. More of a skeleton than an entry, but maybe I can receive some suggestions on coding practices based on what I did write.
http://gist.github.com/313809

Written with 1.8, but probably should work with 1.9 as well.. Er.. If it were complete ;)

Reply

phillipscurry March 31, 2010 at 7:24 pm

Solution (#4):

Phillip Curry, China
Original: https://gist.github.com/86c8f1955ca551bd6ae7
I believe it was written in 1.9. Too new at this to know for sure.
Thanks! This was a great exercise for me.

Reply

James Edward Gray II April 5, 2010 at 3:13 pm

Like many of the submitted players, this player hunts for ships and then queues surrounding shots near known hits to finish them off. It was about average strength for the submissions, with a hunting algorithm not quite as strong as the top-teir entries.

Reply

Benoit Daloze April 1, 2010 at 3:02 am

Solution (#5):

Benoit Daloze, Belgium
Original: https://gist.github.com/d59af62165414688a248
Code works with Ruby 1.8 and 1.9

Reply

James Edward Gray II April 5, 2010 at 3:14 pm

This code was a little work to get running on Ruby 1.8.6. You can see the changes I had to make in this branch:

http://github.com/JEG2/broadsides/tree/rpcfn7_players

This is probably the strongest player submitted, but it does need quite a bit more thinking time than the dn_strategic player that yields nearly as good results. It’s quite a bit of code and though it has some tests, it’s not well commented. This made it hard for me to figure out how it makes some decisions.

Reply

Benoit Daloze April 5, 2010 at 7:52 pm

Hi James Edward Gray II,

Sorry for the not-reviewed code I proposed (this is why it looks dirty, and not documented). I did made it 1.8.7 compatible, but yeah I thought 1.8.6 was out of date. Mainly syntax and enumerators issues I see.

Sadly, I didn’t give enough of my time to make it better.
I tried to name methods in a funny and comprehensive way to try to understand easier how my player shots.

Tests was the only barrier to not get bad because of too much code. It’s far more long to write than I thought for what I wanted.

Anyway, I enjoyed this quiz and I’m impatient to run the tournament :)

Reply

Benoit Daloze April 5, 2010 at 9:00 pm

The best part I coded is (for me), about placing randomly ships. The code is in the loop:
begin

end until (@ships_cells & current_ship_cells).empty?

Which just looks awesome thanks to Ruby’s syntax :D

Reply

Dmitriy Nagirnyak April 6, 2010 at 6:11 am

Hi Benoit,

I must admin, your “finish off” strategy looks a bit better than mine (dn_strategic).
Also your ships placements implementation is quite interesting.

Definitely interesting solution, though out of 5 tournaments I have run locally my player seem to be winning with the scores like this:

Final Scores
============
dn_strategic: 54
players_ere_x: 48
at_basic: 41
pc_player: 32
jeg2_sequential: 21
jeg2_random: 10
nithinbekal: 4

I was a bit impatient to wait for your player while it thinks :)
Anyway, it was my pleasure to challenge our bots :)
Thanks for your interesting solution.

Cheers,
Dmitriy.

Reply

Benoit Daloze April 7, 2010 at 8:29 pm

“I was a bit impatient to wait for your player while it thinks”
Yeah that makes more suspense … :)

Hum this was a bit annoying in fact, and due to the strategy for next shot, taking every free Coord and look for the one which has the maximum free space around. I wanted to reduce that, but my player became too bad, so I kept it.

Cheers,
B.D.

Reply

James Edward Gray II April 5, 2010 at 3:20 pm

I’ve normalized all of the submissions to run on Ruby 1.8.6 (the players with my changes are checked into this branch: http://github.com/JEG2/broadsides/tree/rpcfn7_players) and run a tournament. The results were:

Final Scores
============
players_ere_x: 51
dn_strategic: 50
at_basic: 45
pc_player: 31
jeg2_sequential: 20
jeg2_random: 10
nithinbekal: 3

I believe the top player is ineligible, because he won last time. That’s what he said in his submission anyway. That leaves these players as the top winners:

dn_strategic: 50
at_basic: 45
pc_player: 31

That work’s out well, because I did think Dimitry had the best code.

Thanks for letting me run the challenge Satish. It was a good time. I’m sorry it wasn’t more popular.

Reply

ashbb April 5, 2010 at 9:16 pm

I’d like to thank you all for sharing great solutions.
Watch the battles with Shoes! :-D

jeg2_sequential vs dn_strategic_1 (Dmitriy Nagirnyak)
http://www.rin-shun.com/rubylearning/RPCFN7/jeg2_sequential_vs_dn_strategic_1.swf.html

nithinbekal vs jeg2_random (Nithin Bekal)
http://www.rin-shun.com/rubylearning/RPCFN7/nithinbekal_vs_jeg2_random.swf.html

jeg2_sequential vs at_basic_1 (Antonio Trogi)
http://www.rin-shun.com/rubylearning/RPCFN7/jeg2_sequential_vs_at_basic_1.swf.html

jeg2_sequential vs pc_player (Phillip Curry)
http://www.rin-shun.com/rubylearning/RPCFN7/jeg2_sequential_vs_pc_player.swf.html

jeg2_sequential vs players_ere_x (Benoit Daloze)
http://www.rin-shun.com/rubylearning/RPCFN7/jeg2_sequential_vs_players_ere_x.swf.html

Cheers,
ashbb

Reply

Leave a Comment

{ 34 trackbacks }

Previous post:

Next post: