Yay, it's WebM!
In other news, the creators (esp. Laura Shigihara and George Fan) behind Plants vs. Zombies are awesome!
26 August 2010
WebM Live on YouTube!
So apparently I am really, really, really late on this one (three months is a very long time in the technology world). WebM supported in YouTube has been reported since 19 May 2010. Anyway, this means that YouTube now supports three different video playback formats: flash, H.264, and the aforementioned WebM. As for initial thoughts, I have yet to notice any major differences in playback between H.264 and WebM (flash is just out of the question) on my Quadbox.
22 August 2010
I CAN HAZ MONO
To partially cure my boredom, I downloaded the Mono framework, a piece of software that allows cross platform programs to be written in Microsoft's C#. Installation was decently straightforward; install the program from an installer in a disk image and you are ready to code. For some reason, the GUI toolkits did not install correctly (but they are on my hard disk), and because I did not look into the problem, I was not able to play with GUI-based applications. Maybe everything will install correctly on my Linux box. I will finally get to use it tomorrow when I go to Massachusetts!
Here is the basic Hello World program:
using System;
public class HelloWorld
{
static public void Main()
{
Console.WriteLine("Hello MonoWorld!");
}
}
But the WinForms and GTK# based GUI applications failed to compile, sadly.
WinForms:
using System;
using System.Windows.Forms;
public class HelloWorld : Form
{
static public void Main()
{
Application.Run(new HelloWorld());
}
public HelloWorld()
{
Text = "Hello MonoWorld";
}
}
GTK#:
using Gtk;
using System;
class Hello
{
static void Main()
{
Application.Init();
Window window = new Window("hi");
window.Show();
Application.Run();
}
}
Feedback on my first C# post: Interestingly, I received quite a bit of feedback on my journey with C# all on Buzz. It evolved into quite an interesting thread. [Link]
And finally, here is a bit of programming/compsci humor:
Here is the basic Hello World program:
using System;
public class HelloWorld
{
static public void Main()
{
Console.WriteLine("Hello MonoWorld!");
}
}
But the WinForms and GTK# based GUI applications failed to compile, sadly.
WinForms:
using System;
using System.Windows.Forms;
public class HelloWorld : Form
{
static public void Main()
{
Application.Run(new HelloWorld());
}
public HelloWorld()
{
Text = "Hello MonoWorld";
}
}
GTK#:
using Gtk;
using System;
class Hello
{
static void Main()
{
Application.Init();
Window window = new Window("hi");
window.Show();
Application.Run();
}
}
Feedback on my first C# post: Interestingly, I received quite a bit of feedback on my journey with C# all on Buzz. It evolved into quite an interesting thread. [Link]
And finally, here is a bit of programming/compsci humor:
Nope, I do not have mono(nucleosis). :P
11 August 2010
Adventures of a Music Note: C#
For the past two days or so, I began my adventures learning a Microsoft-centric programming language called C#. (Yes, this means I have to use Windows 7 instead of Linux on my QuadBox.) It seems relatively useful to know, and it's always nice to know more programming languages. Right now I'm still working through the basics and getting to know the language. Without further ado I shall present two niceties.
Append an @ before a keyword to use it as a variable name:
int @new = 5;
Console.WriteLine(@new); // outputs 5
Create nullable booleans! The book just put this in the beginning to show that such a feature exists, but goes into more detail later. It's useful if a trinary boolean system is required.
Boolean? married = null;
if (married == true)
{
Console.WriteLine("married = true");
}
else if (married == false)
{
Console.WriteLine("married = false");
}
else
{
Console.WriteLine("married = null");
}
The code above outputs married = null
That's all for now. Tune in again!
Append an @ before a keyword to use it as a variable name:
int @new = 5;
Console.WriteLine(@new); // outputs 5
Create nullable booleans! The book just put this in the beginning to show that such a feature exists, but goes into more detail later. It's useful if a trinary boolean system is required.
Boolean? married = null;
if (married == true)
{
Console.WriteLine("married = true");
}
else if (married == false)
{
Console.WriteLine("married = false");
}
else
{
Console.WriteLine("married = null");
}
The code above outputs married = null
That's all for now. Tune in again!
06 August 2010
Bridge in the south!
Yippee!
This summer, I had the pleasure of attending the 2010 North American Bridge Championships in New Orleans, Louisiana. I was more than thrilled after competing at last year's Youth NABC in Washington DC with my temporary partner Brian Hamrick, so I decided to bring Sam, my now-regular partner, to play. Brian would be playing with Lenny. The four of us had learned precision in the past year, but had slightly different systems. Perhaps the biggest difference was that Brian and Lenny have used their system against real people (they go to a local club), whereas Sam and I would be test-driving our system at the NABC. Like every other eager bridge player, we made all housing arrangements in February and planned out daily activities as soon as ACBL released the game schedule. I also took the opportunity to apply for a $500 subsidy by my local bridge section for going to the NABC, which I received, and am grateful for their support.
On the mild Saturday night on which Sam and I arrived, the four of us played a one session 299er Swiss. It went pretty well. On the hand that I held a decent 15 point hand with AKQJ seventh of spades, Sam raised me to game with a spade void after I made a jump rebid. It made! We were happy that Precision is working. I can't say I was surprised that the guys wanted to dive into bridge, but I was surprised that I did not collapse or deteriorate in the middle of the session, contrary to last year.
Sunday was a day full of bridge. After losing the first round of the Morning Compact KO, we entered a two-session Bracketed Swiss. Unfortunately, on one board, the opponents called the director on us because we had a miscommunication while bidding. Later that night we signed up for the Mini Spingold 0-1500 just for fun.
Monday was another day full of bridge, but thankfully it was the last three-session day. In the morning, we handily won the Compact KO Consolation. Then at 1PM we played a session of the Mini Spingold. We did surprisingly well in the first quarter, but not as well the second quarter. We lost more in the last two quarters, but did better than the second quarter. Sam and I did well, unfortunately at the expense of our opponents (at the end of 56 boards we seemed to have destroyed our opps' marriage. oops.) I psyched on a board by accident, having miscounted the point cards, so I opened 1D with 9 points but with AQ sixth of diamonds. Sam, thinking I had a decent hand, bid 3NT after a pesky opps' overcall. Guess what? It made! :D
Taking a break from Swiss teams, we played the Gold Rush pairs event on Tuesday. Like the name suggests, this event awards Gold masterpoints! Sam and I did OK in the morning, but were ultimately hampered by our poor defense.
Wednesday was another two-session pairs game, the National 199ers. Again, due to our subpar defense, Sam and I were massacred in the morning, finishing third to last in our direction. The opponents played nearly all the contracts. However, we made our epic comeback in the afternoon. We played as many contracts as possible, and stole contracts as much as we could. Our efforts launched us into 4th place overall!
Thursday begins the Youth NABC. The morning pairs went okay, but not as well as it could have. I had the pleasure of playing a 7NT, courtesy of Sam, and it made! Apparently it was supposed to involve a double squeeze because clubs split 5-0, but as I finessed the person with the clubs, he didn't cover high enough so I got an easy 13th trick ^_^ Sam and I finished third in our direction. The swiss match in the afternoon went pretty well. We tied for second place, with first place finishing just one victory point ahead.
Friday was the National Youth Pairs, sponsored by Baron Barclay's bridge supplies. To our dismay, the cards treated us poorly; the opps had most of the contracts and our sacrifices got doubled. Simply put, we got massacred. Finishing a dismal third to last in our direction, we had no chance of qualifying for the actual event, but we did get 0.20 pity (master)points. The same thing happened to Brian and Lenny. We decided not to play in the consolation game, but went for a session in the Midnight Zip KO just for fun. It went very fast; the opps that Sam and I faced had a very convoluted system and played very quickly. We were done with three boards in approximately ten minutes and the remaining three soon after. Unfortunately, we got knocked out. Still, that doesn't change the fact that it was fun!
Also, midnight knockouts redefine a popular phrase. The phrase no longer goes ``you snooze, you lose'', but ``you lose, you snooze''. Losers get to sleep first while winners have to keep playing. Who would have known?
Saturday was our last game day and the last day of YNABC. We participated in the National Youth Swiss Teams, a two session long swiss game. We ended up doing well (finishing first in C, fourth in B, and 7th overall), but not as well as we had hoped because of unfortunately placed cards. On one of the 3NT contracts the opps played, the dummy, sitting south, had AQT fourth of hearts, east held KJ third of hearts, and west had three low ones. Oh well, at least we blitzed C. In another hand in which I had the pleasure of 3D with a 4-3 trump fit, one of the opps showed out of diamonds on the first round of drawing trumps. Oh dear, a 6-0 trump split. *sobs* At least we didn't get doubled! 3D-4 vul is pretty bad enough. On yet another board, I overcalled a 15-17 1NT with 1 point, holding 5 hearts to the jack and effectively preempted the opponents out of a slam.
On *yet* yet another board, LHO opened 1S and Sam overcalled 2H. Looking at my 23 point hand with heart support, I was so excited and immediately launched into RKC. Sam showed no keycards so we stopped at 5H, which went down. Little did I know that Sam overcalled with 3 points. Oh well.
In sum, the week was very exciting. I have to say that I was actually looking forward to playing, but didn't expect to play this much (~400 boards). Unfortunately, this came at a cost of not being able to explore the culture-filled area. At least we had plenty of seafood for dinner!
Random discoveries
- Precision works! Apparently some people haven't heard of it. Asking bids clear up everything and make slam bidding very easy and not nerve wracking.
- Takeout 1NT scares people away. 1NT direct overcall is 4-14 points with two or fewer cards in the opponent's bid suit and at least three cards in the other suits.
- Aggressive overcalls and preempts are fun! Going down four (doubled) is another story hahaha
- Playing 7NT is nervewracking when you can't count 13 (or more) top tricks. Then you breathe a sigh of relief when opps set up tricks for you.
Recap:
- Saturday
- 299er Swiss: 24 boards - 1.70MP (0.0708 MP/bd)
- Sunday
- Morning Compact KO: 24 bds - 0.00MP (0.0000 MP/bd)
- Bracketed Swiss: 49 bds - 1.78MP (0.0363 MP/bd)
- Monday
- Compact KO Consolation: 24 bds - 1.60MP (0.0667 MP/bd)
- Mini Spingold 0-1500: 56 bds - 0.00MP (0.0000 MP/bd)
- Tuesday
- Gold Rush Pairs: 48 bds - 0.89MP (0.0185 MP/bd)
- Wednesday
- National 199er Pairs: 48 bds - 4.06MP (0.0846 MP/bd)
- Thursday
- Youth NABC Pairs: 21 bds - 0.91MP (0.0433 MP/bd)
- Youth NABC Swiss: 24 bds - 1.65MP (0.0688 MP/bd)
- Friday
- Youth NABC National Pairs: 24 bds - 0.20MP (0.0083 MP/bd)
- Midnight Zip KO: 6 bds - 0.00MP (0.0000 MP/bd)
- Saturday
- Youth NABC National Swiss: 48 bds - 5.02MP (0.1046 MP/bd)
Total: 396 bds - 17.81MP (0.0450 MP/bd)
03 August 2010
End of Senior Year
This post will detail events happening in June, mostly.
5 May: Yay, birthday! Hannah gave me a plateful of brownies, which I distributed to my colleagues and Dr. Nevard during internship. By this time, Mr. Vidal was banned from entering BCA (long story; I'll probably cover this later in much more detail), so we decided to go to a nearby restaurant to have lunch. Because we were all tired of Boston Market and did not want to go to the Coach House diner, we decided to meet at Brooklyn Pizza. Little did we know that we were not allowed to cross the street, despite being at internship (I'm pretty sure that everyone who works off campus is allowed to do so). We found out, while walking to the restaurant, when we encountered a teacher, who lectured us on campus policies and subsequently reported us to the vice principal. Thankfully, none of us received detention; he just lectured me when he saw me in the hall.
2 Jun: Senior experience presentations. Unfortunately, I had the privilege of presenting to Ms. Anderson, one of BCA's incompetent and arrogant technology teachers (I say technology because it's really that; she thinks that she's teaching computer science). I was also quite surprised that we had a full house, considering that the internship wouldn't exist next year. To finish this with a blast, I decided to troll the slideshow (including trollface and playing Always on the last slide). On one of my slides where I had to describe Monte Carlo integrations, I was able to refer to the Riemann-Zeta function (it was so relevant and fitting!) while explaining the canonical pi calculation example. The handouts, in particular, were awesome: we made two versions, one with a legitimate overview of the internship for the teachers, and one with a hilarious description filled with puns and memes for the students. At the end, several students commended us on our successful troll attempt. Regardless of our mischief, I received an A for the trimester and the year. Win!
3 Jun: CompSci Day. This was actually another of Mr. Vidal's brilliant ideas, but was run by some CompSci Families parents instead (for obvious reasons). It was a luncheon for all students interested in computer science and featured some students who wanted to present their projects. Of course, I took the opportunity to present Battleship visualizer, the [formerly] ongoing Computer Team activity. As the first one to go, I presented for ten minutes on the various aspects of the Visualizer, such as Java being annoying, running external processes, how game designing is not trivial (contrary to another student's assertion that Java makes game development easy), and how two [skilled] programmers were able to put together a ~1000 line program in two weeks, with about an hour's worth of work each day. Everyone seemed thoroughly impressed (and amused -- the most important part!) by the presentation, especially the demos. :)
4-5 Jun: ARML. This was covered in a previous post. To recap, AAST Mu A finished 9th, the best in the recent four years.
9 Jun: Senior Luncheon. The class parents and teachers took us to a fancy restaurant, where we had lunch, took pictures, and signed yearbooks. The lunch was so fancy that everyone had four forks and two knives.
10 Jun: Prom. Again, this has been detailed in a previous post. This was the first of three events in which Troll, inc. (Patrick, Julia, me, and perhaps Sam, though he's always too shy to make a public move) tried to get the DJ to play Troll Music®.
11 Jun: Our hypothetical afterprom dissolved in thin air, so I stayed home for the day. Later that night I went with Dan and Sam to the mall for the night. We got dinner (teryaki for Dan, hamburger for Sam, and sushi for me), played around in the Apple store for an hour (yay Python and iOS games!), and then watched the Prince of Persia: The Sands of Time. Sam didn't mind seeing the movie twice in two weeks.
13 Jun: Joe Holbrook Memorial. It has already been almost five months since the old geezer passed away. The ceremony began at 4:30 when close friends of his and two BCA alums gave speeches, followed by dinner. At 6:30, Mark and I interviewed two candidates for the five Math Team Captain positions. They lasted until 8:00. Finally I went home.
16 Jun: Six Flags! This was my first time going to a theme park in two years. I was so excited to go on Superman, the only large roller coaster that I could withstand, but it was closed. Julia and I went on Rolling Thunder three times and screamed `CARD GAMES ON ROLLER COASTERS' pretty much on every decently-sized drop. Here is her post about it.
17 Jun: Our first graduation rehearsal. We get our caps, gowns, tickets, and picture taken. Luckily, we had no classes, but we just spent the entire day sitting in the gymnasium waiting to rehearse (we did it by academies). I spent a good amount of time watching some AEDT guys play Half Life (or whatever FPS it was) on Xbox 360.
18 Jun: Field day. Mark, Pavel, and I did final Math Team interviews and made our decision soon after. For the rest of the day we camped out in a classroom and played on our laptops. Somewhere right after lunch we played a bridge hand with Dr. Abramson.
19 Jun: Math Team Party. Mark and I passed down math team leadership to the five chosen candidates. We ate pizza.
20 Jun: Mr. Vidal's family and my family went to a local Thai restaurant to have lunch for Father's day. We talked mainly about the slew of unfortunate events that has happened at the school and I finally returned his GPU Gems book. Also Thai food is good when not very spicy.
21 Jun: Second of three graduation rehearsals. We ended up finishing approximately three hours before schedule, so we were dismissed at 11:00! Sam graciously drove me home and we played bridge.
22 Jun: Last day of school! The entire day was devoted to graduation rehearsal, but we managed to finish two hours earlier, so Sam and I hung out in Dr. Nevard's room. Unfortunately, not many people showed up to Computer Team. Oh well. At the end of the half day, I took home the ACSL prize printer that the ACSLers graciously gave to me for being their coach. I must have looked pretty weird carrying a printer out of the school XD
23 Jun: Graduation! It was a pretty basic graduation: walk on stage, listen to speeches while trying not to fiddle with hair or scratch face, get diploma, and walk (and jump) off stage, all while being filmed by over 9000 cameras. Because BCA teachers are cool, the director asked us to submit music suggestions for the song played at the end of graduation. Of course, I emailed her:
To which she replied:
What a great response XD Unfortunately, none of the songs were played. Oh well, I tried.
However, our trolling efforts were finally fruitful during Project Graduation. We were fortunate that Patrick's mom was the co-director of the event, so Patrick was able to insert the Rickroll and Always in the mix CD. To our amusement, the Rickroll did play! Pretty much everyone groaned except for the nerds, who laughed. Julia, Patrick, and I bursted in excitement that our efforts finally paid off. What a great ending to four years at BCA.
5 May: Yay, birthday! Hannah gave me a plateful of brownies, which I distributed to my colleagues and Dr. Nevard during internship. By this time, Mr. Vidal was banned from entering BCA (long story; I'll probably cover this later in much more detail), so we decided to go to a nearby restaurant to have lunch. Because we were all tired of Boston Market and did not want to go to the Coach House diner, we decided to meet at Brooklyn Pizza. Little did we know that we were not allowed to cross the street, despite being at internship (I'm pretty sure that everyone who works off campus is allowed to do so). We found out, while walking to the restaurant, when we encountered a teacher, who lectured us on campus policies and subsequently reported us to the vice principal. Thankfully, none of us received detention; he just lectured me when he saw me in the hall.
2 Jun: Senior experience presentations. Unfortunately, I had the privilege of presenting to Ms. Anderson, one of BCA's incompetent and arrogant technology teachers (I say technology because it's really that; she thinks that she's teaching computer science). I was also quite surprised that we had a full house, considering that the internship wouldn't exist next year. To finish this with a blast, I decided to troll the slideshow (including trollface and playing Always on the last slide). On one of my slides where I had to describe Monte Carlo integrations, I was able to refer to the Riemann-Zeta function (it was so relevant and fitting!) while explaining the canonical pi calculation example. The handouts, in particular, were awesome: we made two versions, one with a legitimate overview of the internship for the teachers, and one with a hilarious description filled with puns and memes for the students. At the end, several students commended us on our successful troll attempt. Regardless of our mischief, I received an A for the trimester and the year. Win!
3 Jun: CompSci Day. This was actually another of Mr. Vidal's brilliant ideas, but was run by some CompSci Families parents instead (for obvious reasons). It was a luncheon for all students interested in computer science and featured some students who wanted to present their projects. Of course, I took the opportunity to present Battleship visualizer, the [formerly] ongoing Computer Team activity. As the first one to go, I presented for ten minutes on the various aspects of the Visualizer, such as Java being annoying, running external processes, how game designing is not trivial (contrary to another student's assertion that Java makes game development easy), and how two [skilled] programmers were able to put together a ~1000 line program in two weeks, with about an hour's worth of work each day. Everyone seemed thoroughly impressed (and amused -- the most important part!) by the presentation, especially the demos. :)
4-5 Jun: ARML. This was covered in a previous post. To recap, AAST Mu A finished 9th, the best in the recent four years.
9 Jun: Senior Luncheon. The class parents and teachers took us to a fancy restaurant, where we had lunch, took pictures, and signed yearbooks. The lunch was so fancy that everyone had four forks and two knives.
10 Jun: Prom. Again, this has been detailed in a previous post. This was the first of three events in which Troll, inc. (Patrick, Julia, me, and perhaps Sam, though he's always too shy to make a public move) tried to get the DJ to play Troll Music®.
11 Jun: Our hypothetical afterprom dissolved in thin air, so I stayed home for the day. Later that night I went with Dan and Sam to the mall for the night. We got dinner (teryaki for Dan, hamburger for Sam, and sushi for me), played around in the Apple store for an hour (yay Python and iOS games!), and then watched the Prince of Persia: The Sands of Time. Sam didn't mind seeing the movie twice in two weeks.
13 Jun: Joe Holbrook Memorial. It has already been almost five months since the old geezer passed away. The ceremony began at 4:30 when close friends of his and two BCA alums gave speeches, followed by dinner. At 6:30, Mark and I interviewed two candidates for the five Math Team Captain positions. They lasted until 8:00. Finally I went home.
16 Jun: Six Flags! This was my first time going to a theme park in two years. I was so excited to go on Superman, the only large roller coaster that I could withstand, but it was closed. Julia and I went on Rolling Thunder three times and screamed `CARD GAMES ON ROLLER COASTERS' pretty much on every decently-sized drop. Here is her post about it.
17 Jun: Our first graduation rehearsal. We get our caps, gowns, tickets, and picture taken. Luckily, we had no classes, but we just spent the entire day sitting in the gymnasium waiting to rehearse (we did it by academies). I spent a good amount of time watching some AEDT guys play Half Life (or whatever FPS it was) on Xbox 360.
18 Jun: Field day. Mark, Pavel, and I did final Math Team interviews and made our decision soon after. For the rest of the day we camped out in a classroom and played on our laptops. Somewhere right after lunch we played a bridge hand with Dr. Abramson.
19 Jun: Math Team Party. Mark and I passed down math team leadership to the five chosen candidates. We ate pizza.
20 Jun: Mr. Vidal's family and my family went to a local Thai restaurant to have lunch for Father's day. We talked mainly about the slew of unfortunate events that has happened at the school and I finally returned his GPU Gems book. Also Thai food is good when not very spicy.
21 Jun: Second of three graduation rehearsals. We ended up finishing approximately three hours before schedule, so we were dismissed at 11:00! Sam graciously drove me home and we played bridge.
22 Jun: Last day of school! The entire day was devoted to graduation rehearsal, but we managed to finish two hours earlier, so Sam and I hung out in Dr. Nevard's room. Unfortunately, not many people showed up to Computer Team. Oh well. At the end of the half day, I took home the ACSL prize printer that the ACSLers graciously gave to me for being their coach. I must have looked pretty weird carrying a printer out of the school XD
23 Jun: Graduation! It was a pretty basic graduation: walk on stage, listen to speeches while trying not to fiddle with hair or scratch face, get diploma, and walk (and jump) off stage, all while being filmed by over 9000 cameras. Because BCA teachers are cool, the director asked us to submit music suggestions for the song played at the end of graduation. Of course, I emailed her:
Here are some songs I would like:
1. Rick Astley - Never Gonna Give You Up
2. Erasure - Always
Thanks!
Sherry Wu
1. Rick Astley - Never Gonna Give You Up
2. Erasure - Always
Thanks!
Sherry Wu
To which she replied:
Great songs. Thanks!
What a great response XD Unfortunately, none of the songs were played. Oh well, I tried.
However, our trolling efforts were finally fruitful during Project Graduation. We were fortunate that Patrick's mom was the co-director of the event, so Patrick was able to insert the Rickroll and Always in the mix CD. To our amusement, the Rickroll did play! Pretty much everyone groaned except for the nerds, who laughed. Julia, Patrick, and I bursted in excitement that our efforts finally paid off. What a great ending to four years at BCA.
16 July 2010
Jet Lag
causes in an interesting sleep schedule.
Tuesday, 1 am: Get back from airport, finally. Slept at 2am, woke up at 11am. Awesome.
Traveled to MA later that day and slept for half an hour in the car. Something like that.
Wednesday morning: Sleep at 12am, wake up at 5-ish am. Lay in bed for maybe an hour?
Later that day, I fell asleep at 2pm on the couch while reading a book on stock options and differential equations. Woke up at 6pm when Dad got back. Missed chance to cook dinner. Oops.
Slept on Thursday morning at 12am. Woke up around 5-ish am. Again. Napped in the afternoon from 4-8.
Decided to sleep earlier, at 11pm, and woke up at 6am. Progress? What will happen next…
This doesn't seem to deviate from normal that much (if you can call it normal); I slept well the first night at Beijing (9pm to 7am), but the next few days from 11am to 6am and a decent nap later in the day.
23 June 2010
Battleship Chronicles, Part IV: Over 9000
The basic idea for Over 9000 was inspired by a TopCoder marathon match, except that in their variation multiple shots were fired in a single turn and you were only told which ships were hit without knowing which shots were the hits, and board sizes could be much larger. I was curious to see how it would do and decided to implement it with a few modifications described below. For those who are interested, the problem statement can be found here and the editorial can be found here.
Over 9000 essentially uses a brute force strategy to choose the next place to fire. For each possible ship, try to place it on every possible location. If you can place it, increment a counter of every square the ship is on by 1. Thus, if we assume all layouts of a particular ship are equally likely, we can compute the probability that a given ship will be on a given square simply by dividing by the total number of possible layouts. Consider the example grid below, where 0 represents a known miss, a number from 1 to 5 represents a known hit, and x represents an unknown square (we will consider a smaller grid for simplicity):
xxx0x
4440x
xx0xx
x5xxx
xxx0x
Suppose we are considering ship number 3, with length 3. Here are the 7 possible locations:
3330x xxx03 xxx0x xxx0x xxx0x xxx0x xxx0x
4440x 44403 44403 4440x 4440x 4440x 4440x
xx0xx xx0x3 xx0x3 xx0x3 3x0xx xx0xx xx0xx
x5xxx x5xxx x5xx3 x5xx3 35xxx x5xxx x5333
xxx0x xxx0x xxx0x xxx03 3xx0x 3330x xxx0x
If we look at the top left corner, there is only one configuration, so the probability is 1/7. However, the middle of the right column has probability 3/7 and will thus be more likely to contain this ship, so if we were only trying to find this ship then it would be the best place to fire. However, we have five ships to consider, not only one, and we would like to find the probability of a given square containing any ship using our probabilities for each ship. We will have to make one more assumption to do this and assume that the ship locations are independent of each other. Of course, this is not true due to the constraint that no two ships can overlap, but it does give a good approximation. If you look at the example grid, you will notice that there is a hit on ship 5, making the surrounding locations less likely to contain ship 3.
To compute this probability, we cannot simply add the probabilities of each ship, as this will count some cases twice. Instead, we can compute easily the probability that there is no ship on a given square, as we can simply multiply the probabilities for each ship of that ship not being on a square due to our independence assumption. Since p(not X) = 1 - p(X), then if we define p(n) to be the probability of ship n being on a given square, then the probability of finding any ship on a given square is equal to
1 - (1 - p(1)) * (1 - p(2)) * ... * (1 - p(5)). Once we get the probability for each square, then we can simply pick the square with highest probability that we have not already tried and fire there.
Over 9000 also includes some modifications to this strategy to account for the assumption that all locations are equally likely. This is of course not the case, especially since many people kept the original layouts sent with BruteForce or created their own. To counter this, every square was weighted and when the probabilities were computed, they were multiplied by the weights before determining the maximum. Over 9000's weight grid was based on the observation that human players preferred to place ships on the sides, and thus it gave the squares on the sides a higher weight than the others. In addition, Over 9000 added a small random number to the final probabilities, which had the effects of breaking ties and creating more interesting games, though it likely decreased performance slightly due to non-optimal behavior, as only one shot is fired at a time. However, this did have the positive effect of having no definite worst-case enemy ship placement, as Over 9000 would no longer be deterministic.
There are still some improvements which can be made, however. One simple improvement is to keep track of the games you play and increase the values in your weight grid as you get hits in squares, giving better results against people who play a small set of layouts. Another improvement which can be made is to consider multiple ships at a time instead of one ship, which will help offset the independence assumption. Ideally, we would consider layouts of all ships at once instead of placing single ships, but this would of course take up too much time in the early stages of the game when there is little known information.
Bob uses the same strategy, except that Bob uses only the information that a square was a hit or a miss. Also, Bob does not use either of the modifications described two paragraphs ago.
With regard to ship placement, it would usually make little difference how your ships were placed as a whole, though it was often possible to look at other programs and determine the worst case placement against their program.
Over 9000 essentially uses a brute force strategy to choose the next place to fire. For each possible ship, try to place it on every possible location. If you can place it, increment a counter of every square the ship is on by 1. Thus, if we assume all layouts of a particular ship are equally likely, we can compute the probability that a given ship will be on a given square simply by dividing by the total number of possible layouts. Consider the example grid below, where 0 represents a known miss, a number from 1 to 5 represents a known hit, and x represents an unknown square (we will consider a smaller grid for simplicity):
xxx0x
4440x
xx0xx
x5xxx
xxx0x
Suppose we are considering ship number 3, with length 3. Here are the 7 possible locations:
3330x xxx03 xxx0x xxx0x xxx0x xxx0x xxx0x
4440x 44403 44403 4440x 4440x 4440x 4440x
xx0xx xx0x3 xx0x3 xx0x3 3x0xx xx0xx xx0xx
x5xxx x5xxx x5xx3 x5xx3 35xxx x5xxx x5333
xxx0x xxx0x xxx0x xxx03 3xx0x 3330x xxx0x
If we look at the top left corner, there is only one configuration, so the probability is 1/7. However, the middle of the right column has probability 3/7 and will thus be more likely to contain this ship, so if we were only trying to find this ship then it would be the best place to fire. However, we have five ships to consider, not only one, and we would like to find the probability of a given square containing any ship using our probabilities for each ship. We will have to make one more assumption to do this and assume that the ship locations are independent of each other. Of course, this is not true due to the constraint that no two ships can overlap, but it does give a good approximation. If you look at the example grid, you will notice that there is a hit on ship 5, making the surrounding locations less likely to contain ship 3.
To compute this probability, we cannot simply add the probabilities of each ship, as this will count some cases twice. Instead, we can compute easily the probability that there is no ship on a given square, as we can simply multiply the probabilities for each ship of that ship not being on a square due to our independence assumption. Since p(not X) = 1 - p(X), then if we define p(n) to be the probability of ship n being on a given square, then the probability of finding any ship on a given square is equal to
1 - (1 - p(1)) * (1 - p(2)) * ... * (1 - p(5)). Once we get the probability for each square, then we can simply pick the square with highest probability that we have not already tried and fire there.
Over 9000 also includes some modifications to this strategy to account for the assumption that all locations are equally likely. This is of course not the case, especially since many people kept the original layouts sent with BruteForce or created their own. To counter this, every square was weighted and when the probabilities were computed, they were multiplied by the weights before determining the maximum. Over 9000's weight grid was based on the observation that human players preferred to place ships on the sides, and thus it gave the squares on the sides a higher weight than the others. In addition, Over 9000 added a small random number to the final probabilities, which had the effects of breaking ties and creating more interesting games, though it likely decreased performance slightly due to non-optimal behavior, as only one shot is fired at a time. However, this did have the positive effect of having no definite worst-case enemy ship placement, as Over 9000 would no longer be deterministic.
There are still some improvements which can be made, however. One simple improvement is to keep track of the games you play and increase the values in your weight grid as you get hits in squares, giving better results against people who play a small set of layouts. Another improvement which can be made is to consider multiple ships at a time instead of one ship, which will help offset the independence assumption. Ideally, we would consider layouts of all ships at once instead of placing single ships, but this would of course take up too much time in the early stages of the game when there is little known information.
Bob uses the same strategy, except that Bob uses only the information that a square was a hit or a miss. Also, Bob does not use either of the modifications described two paragraphs ago.
With regard to ship placement, it would usually make little difference how your ships were placed as a whole, though it was often possible to look at other programs and determine the worst case placement against their program.
22 June 2010
Battleship Chronicles, Part III
Original email sent to CompTeam members:
Thank you for showing interest in computer science and participating in the Computer Team elective or joining the mailing list for the past trimester. I hope you learned something new, interesting, and worthwhile from the elective, whether it be a new algorithm, that USACO is not trivial, that Battleship is fun, but even more so when visualized with fitting sound effects, that student-run electives work, or that Dr. Nevard loves dark chocolate. Most importantly, I hope you all had fun. I know that working on USACO training or listening to lectures can get quite boring; this is why we decided to do a project for the end of the year.
Thank you for showing interest in computer science and participating in the Computer Team elective or joining the mailing list for the past trimester. I hope you learned something new, interesting, and worthwhile from the elective, whether it be a new algorithm, that USACO is not trivial, that Battleship is fun, but even more so when visualized with fitting sound effects, that student-run electives work, or that Dr. Nevard loves dark chocolate. Most importantly, I hope you all had fun. I know that working on USACO training or listening to lectures can get quite boring; this is why we decided to do a project for the end of the year.
After about a month of work on the final project, Battleship, we finally get to see the skills of each and every one of you as problem solvers and computer scientists. From reading your code to watching your programs battle each other on screen, we have gotten a fairly good estimate of your skills in a real-life task. My expectations were in line with the tournament results.
The tournament was run on a homebuilt machine with the following specs: Intel Core 2 Quad Q9550, 8GB memory, 100GB disk, NVidia 8800GTS 320MB running Ubuntu 10.04 LTS. Each program played every other program 399 times. The following programs were included in the tournament:
- AndrwsBtlshpPgrm v3.0 (Andrew Cai)
- Colonel (Jie Guan)
- Tertius (Alec Benzer, Mark Fayngersh, Vikram Jayashankar)
- Slayer V5 (Nick Bevacqua)
- Over 9000 (Sam Fingeret)
- Bob (Sam Fingeret)
- BruteForce (Sam Fingeret)
- Random 2.0 (Sam Fingeret)
- Rofl Copter (Matt Lotocki)
#NONAME (Alex Zhu) was not entered because it was less than 50 lines long. Alex Zhu was disqualified by teachers' discretion. His program just shot at cell `A1'.
Zumwalt Mk II (Jonathan Beekman) was not entered because some opponents' ship placements caused it to hang.
Ari Jidai (Jonathan Sorce) was not entered because some opponents' ship placements caused it to crash.
With that being said, let me present the tournament rankings:
nonitalics = benchmark programs; they are not allowed to win the tournament
=== RESULTS ===
1. Over 9000 won 2857
2. Colonel won 2551
3. AndrwsBtlshpPgrm v3.0 won 2536
4. Slayer V5 won 1902
5. Bob won 1794
6. Tertius won 1419
7. BruteForce won 592
8. Random 2.0 won 479
9. Rofl Copter won 234
Congratulations Jie Guan for winning the first annual Battleship Tournament! Also, props to Andrew for putting up a tough fight.
Here are more statistics:
=== ACCURACY ===
Over 9000 : 37.11636673573047%
AndrwsBtlshpPgrm v3.0 : 33.74789674827501%
Colonel : 32.46263314180419%
Tertius : 29.055394377209023%
Slayer V5 : 28.02107767763948%
Bob : 27.673535550917084%
Random 2.0 : 17.22408350601313%
BruteForce : 17.080802952490675%
Rofl Copter : 9.710122203384847%
And even more statistics:
=== FULL RESULTS ===
1 = AndrwsBtlshpPgrm v3.0
2 = Colonel
3 = Tertius
4 = Slayer V5
5 = Over 9000
6 = Bob
7 = BruteForce
8 = Random 2.0
9 = Rofl Copter
1 2 3 4 5 6 7 8 9
1 0 220 318 308 124 375 398 399 394
2 179 0 379 389 56 351 399 399 399
3 81 20 0 29 50 63 381 396 399
4 91 10 370 0 67 168 399 398 399
5 275 343 349 332 0 377 399 399 383
6 24 48 336 231 22 0 398 398 337
7 1 0 18 0 0 1 0 252 320
8 0 0 3 1 0 1 147 0 327
9 5 0 0 0 16 62 79 72 0
We will be sending out an explanation about Over 9000 in the near future, by popular request.
Again, thank you all for participating in the tournament and in the elective. We hope you found it to be interesting and more helpful/fun/challenging than your normal computer science classes. I won't be sending out many emails from now on; I expect one or two more regarding the future of Computer Team. Enjoy the remainder of the year!
The Visualizer source code and dependencies are located here: http://github.com/shewu/Battleship-Visualizer
The Visualizer source code and dependencies are located here: http://github.com/shewu/Battleship-Visualizer
21 June 2010
Farewell CompTeam
Hello all,
Wow! It has been a great first year for BCA Computer Team. You all deserve a big pat on the back for shaping the elective into what it is now and deserve many thanks for your involvement and contributions. Hopefully the elective has fulfilled its intended purpose: to present challenges in computer science to further current knowledge. Please do not feel discouraged by USACO training and the contests, they were meant to be tough and non-routine. Battleship was meant to be a relaxing break from the training problems; hopefully it was a good application of algorithmic programming, data structures, and most of all, problem solving in a real-life programming job.
The real lesson to be learned from CompTeam is to create opportunities for yourself. Don't complain about the teachers; just finish their work quickly so you have more time for your own endeavors. There is a plethora of fresh material waiting: USACO, TopCoder, research, and even projects. The last option is most definitely possible. I'll give you two examples. At the end of junior year, I wrote a minesweeper clone, LOLsweeper, in two days using Java. This year, Mark Fayngersh, Alec Benzer, Vikram Jayashankar, and friends wrote a full-blown iPad game, Blob Defense in about a month using Objective C. Sure, this sounds intimidating at first, but if you are willing to take the time to learn cool techniques, languages, and coding paradigms, you most certainly will get a phenomenal product and you will be impressed at what you are capable of. So when should you start? NOW!
Last but not least, since the elective is in its infancy, I would like to present my expectations for CompTeam's future. I will officially empower Alec Benzer as 2010-2011 Captain at 12:00PM on 24 June 2010. This does not imply that he is the one doing everything, though he is the one managing logistics. Remember that this is CompTeam; it has been successful for the past year because of you, the individual. My stepping down means that I will not be dictating the future of CompTeam. Keep the team alive, make it a tradition, and hopefully it will be recognized as a competent team. Attract freshmen and everyone who wants to pursue computer science or wants a challenge in problem solving with computers. Do a mixture of lectures, contest problems, and projects. Host a game tournament, party, and give out prizes. Share lectures, material, knowledge and put them on a website or central repository. Get parents involved. Learn. Have fun. Make new friends.
I must reiterate myself again: don't let teachers limit your potential. Reflect on the accomplishments you made in CompTeam. That was all you. If you realized that compsci isn't your passion, keep looking. As Steve Jobs said in his Stanford Commencement speech, "Don't settle until you found something (or someone) you love. As with all matters of the heart, you'll know when you find it."
That's all for now. Keep in touch! Feel free if you have programming questions :)
sherry
Battleship Chronicles, Part II
While the contestants were working on their programs, Sam and I worked on the Visualizer. We decided to work in a linear fashion, which probably was not very efficient. Then again, neither of us felt like writing an API or outline. We agreed that Sam would take care of the underpinnings and I would do the graphics and interface.
Sam started out with a backbone from another TopCoder visualizer. He slowly built upon it, changing, adding, and deleting functions as necessary. After a week's worth of work in class, during frees, and at home, Sam had a program that displayed the ships as colored blocks. We showed this on 28 May 2010 and wowed the class. BruteForce, Random 1.0, Bob, Over 9000, Slayer (Nick), and ./battleship (Alec, Mark, Vikram) participated. We were confident that people were awed by how fun the Battleship tournament would be.
Following that Friday was Memorial weekend. This was basically my only free time to substantially revamp the program. Coincidentally, I received my beautiful Dell Ultrasharp U2211 21" screen, of whose widescreen-ness I took advantage to do the graphics for the ships.
Sound effects were secondary, since those could be trivially found on the internet. I settled on a frog croak and glass breaking. After about a day's worth of work, I can say that I have made some progress.
I then sent the two screenshots to two folks, who then gave me comments and suggestions. Both of them thought it was phenomenal compared to the original. One of them suggested using a top-down view instead of a perspective view of the ocean.
In the meantime, the competitors kept on working on and sending me their programs. Sam assisted me in debugging and critiquing programs. He almost cried as he read through one of the programs I received. We showed demos every Tuesday until the 15th of June, since neither of us would be present in class on Fridays. 4 June 2010 was ARML and the Friday after that was afterprom. In addition to the 15th being our last day of class, I decided to have a party for celebrating the end of one year for Computer Team. After two more demo days, the contestants were confident that their programs would fare well in the tournament.
Sam started out with a backbone from another TopCoder visualizer. He slowly built upon it, changing, adding, and deleting functions as necessary. After a week's worth of work in class, during frees, and at home, Sam had a program that displayed the ships as colored blocks. We showed this on 28 May 2010 and wowed the class. BruteForce, Random 1.0, Bob, Over 9000, Slayer (Nick), and ./battleship (Alec, Mark, Vikram) participated. We were confident that people were awed by how fun the Battleship tournament would be.
the second window is 1px higher than the others >_<
In the meantime, the competitors kept on working on and sending me their programs. Sam assisted me in debugging and critiquing programs. He almost cried as he read through one of the programs I received. We showed demos every Tuesday until the 15th of June, since neither of us would be present in class on Fridays. 4 June 2010 was ARML and the Friday after that was afterprom. In addition to the 15th being our last day of class, I decided to have a party for celebrating the end of one year for Computer Team. After two more demo days, the contestants were confident that their programs would fare well in the tournament.
Subscribe to:
Comments (Atom)