Send to KindleRuby Programming Challenge For Newbies
RPCFN: Broadsides (#7)
By James Edward Gray II
About James Edward Gray II
James 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.
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 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
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:
- Your name:
- Country of Residence:
- GIST URL of your Solution (i.e. Ruby code) with explanation and / or test cases:
- Code works with Ruby 1.8 / 1.9 / Both:
- Email address (will not be published):
- 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:
- What Is The Ruby Programming Challenge For Newbies (RPCFN)?
- How does RPCFN benefit you?
- Challenge Rules
- Best Solution
- Can I Submit A Ruby Programming Challenge Topic?
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.
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
- Dmitriy Nagirnyak, Australia – declared winner (best solution)
- Nithin Bekal, India – declared winner (randomly selected)
- Antonio Trogi, Canada – declared winner (randomly selected)
- Phillip Curry, China – declared winner (randomly selected)
- Benoit Daloze, Belgium – declared winner (randomly selected)
Just for Fun
- Satoshi Asakawa, Japan
The Winners
Congratulations to the winners of this Ruby Challenge. They are:
- Dmitriy Nagirnyak from Australia (his Ruby Challenge solution) – the person with the best and most creative Ruby solution. He wins any one of PeepCode’s Ruby on Rails screencasts and a free 10 GB account for a year from Backup My App.
- Antonio Trogi from Canada, Benoit Daloze from Belgium, Nithin Bekal from India and Phillip Curry from China win any one of Pragmatic’s The Ruby Object Model and Metaprogramming screencasts.
- All the participants in this challenge (except Dmitriy Nagirnyak who gets a free 10 GB account for a year) will get a free 5 GB account for 6 months from Backup My App.
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.
- This challenge is now closed.
- The (#8) challenge by Jamie van Dyke, UK is scheduled for 9th Apr. 2010.
Technorati Tags: Ruby, The Ruby Programming Language, Ruby Programming Challenge For Newbies, Programming, RPCFN, James Edward Gray II
Posted by Satish Talim
- US$ $0.91
- US$ 4.60
- US$ 6.44
{ 50 comments… read them below or add one }
Next Comments →
Any reason an “INFO SUNK 3:A1:H” type message is not included? Most versions I have seen include this information.
Yes. I gave you a way to tell if a ship has been sunk. It’s just not quite that easy.
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. :-/
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.
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.
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.
“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.
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.
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.
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.
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:
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:
Interesting challenge! Can entrants post multiple solutions?
Please do.
How to submit a player that consists of multiple files?
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.
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.
Wouldn’t the chance of hitting ships be related to the board size and amount of that space they take up?
…and the number of shots taken too (to be precise number of unique shots).
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?
Not quite. You only lose 2 shots if the length 5 ship is sunk. All other ships subtract 1 shot as they are sunk.
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.
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.
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.
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.
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.
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
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.
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.
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*
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.
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
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.
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
We have had a couple of solutions, but we definitely need more. Do send in what you come up with.
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.
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.
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
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.
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
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
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.
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.
Solution (#5):
Benoit Daloze, Belgium
Original: https://gist.github.com/d59af62165414688a248
Code works with Ruby 1.8 and 1.9
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.
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
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
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.
“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.
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.
I’d like to thank you all for sharing great solutions.
Watch the battles with Shoes!
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
{ 34 trackbacks }