| |
CS Games is a year old competitive event hosted by McGill University
in Montreal. It allows students from both US and Canadian schools to
compete against each other in an agglomerate of logic, coding, and computer
gaming trials. Our experience included sessions of logic puzzles, AI
development, debugging, website design, assembly coding, and more. In
addition to these mind-intensive events, points were also scored based
on our involvement in a city-wide scavenger hunt, a computer gaming
tournament, and some friendly improv theater contests.
Events:
- Solitary Teamwork (Team Software Engineering)
Flavor: Awesome.
This was the first contest to take place. Three members from each
team were sent into some computer labs with the task to program the
game ConnectFour. The rules made this contest interesting:
1st 30 minutes: Team can sit together.
Next 2 hrs: Team cant have communication amongst its members.
Last 30 minutes: Team can sit together.
This put necessity on the commonly ignored planning phase of programming.
Our tasks were to implement the game ConnectFour, and as many of the
optional features as possible:
Game selection/start menu
2D GUI
3D GUI
Network playable
Multiple local players
Dumb computer player
Smart compuer player
Installation package
Readme
Each feature had a specific point value if implemented correctly.
We were provided with a common set of resources (no internet) to use
as reference.
Our team was well formed to cover most of the features. John had just
learned opengl, and was excited to put it to use, and Rusty was learning
network programming. Our effort earned us sixth place in the event,
and although we know we made tons of mistakes, we are comfortable
knowing that other teams probably did, too.
- A Date with the Web (Web Design/Programming)
Taking place on Sunday morning the web design competition charged
its participants with both an artistic and technical challenge. Each
team had to develop a site for "MatchMaker.com" your standard
internet dating service. Two people from each team were given resources
in HTML, PHP, MySQL and Adobe Photoshop and had to build the most
comprehensive site possible in the 3 hours alloted.
The RPI combantants were Brian Fields and Brent Josefiak, both
Juniors.
Before delving into the actual competition it should be noted that
although both participants had experience with HTML neither of us
had used much PHP beforehand. On the trip up we read a manual or
two and then at midnight on Sat we decided a little hand's on practice
would be helpful so we found an internet cafe which was open. Surrounded
by Koreans playing Warcraft 3 we learned the basics of setting up
a PHP server.
When we actually entered the competition, that last minute cramming
proved invaluable. Most of the technical aspects of the session
were even more advanced than what we had covered but, our knowledge
was enough to make headway throughout the time alloted. The art
and actual HTML flew by and we managed to develop a working account
creation and login system. So despite having not nearly enough background
in this arena we managed to pull out a solid middle of the pack
finish.
- Battlefield 2004 (A.I. Programming Competition)
This year, we were challenged to write a program to play Nine-Men’s-Morris.
Each school had a team of 3 people who programmed the AI over the
course of two days. Nine-Men’s-Morris is an interesting choice because
the game features several unique phases, requiring two completely
different algorithms. It should be noted that Nine-Men’s-Morris is
a draw game like tic-tac-toe, in that if the first player plays a
perfect game, the second player can only tie him. Given the time constraints
we had, however, this was probably not a factor.
At the end of the first day, all teams competed against each other
in a round-robin tournament. The teams were then ranked, and this
rank determined a player’s seed in the final round. At the end of
the second day, each team played in an elimination-style tournament
with the results determining the number of points received.
The AI was to be implemented in Java. Our algorithm we made was very
nice and could have wreaked a lot of havoc, but due to our slow start
the first day, and an unsolved problem the second day, our system
was not working at its optimum, and could only play a defensive game
which is not the best for Nine-Men's-Morris.
- Core Dump (Debugging)
This contest tested to see how alert you were. There were classic
mistakes all through sorting alorithms, tree functions, determinant
functions, and more. John and Ben had little trouble getting the third
highest score in Debugging.
- Inartificial Intelligence (Logic)
The logic competition involved creative problem solving for a variety
of word problems. In most cases the solution to a logic question was
a single phrase, number or sentence. One example of a logic question
is, “Given 2 ropes that each take one hour to burn beginning
at one end of a rope, how can we measure 45 minutes using only the
2 ropes and a lighter?”
- H4ck3rz Gu1ld HQ (Scripting)
The assignment here was to solve as many scripting problems possible
in the three hours, using only unix shell scripting languages (that
is, bash, csh, .... and not perl).
This contest was tough, but JJ and Rusty nailed 2nd place. Here are
some sample problems.
Easy:
isleapyear
determines whether a given year is a leap year or not. It outputs 1 if so, 0 if not.
The clever solution here is to use the program 'calendar' found with many distributions of unix/linux.
I ran calendar on the year specified and checked to see if there was a Feb 29.
Hard:
minesweeper
minesweeper is a text version of the classic Minesweeper game in
which one tries to determine where the hidden mines are placed in
a mine field. The playing field is represented by a square grid
of ASCII characters: ? means the square has not been uncovered,
and a number if the square has been uncovered is present between
0 to 8 to represent how many mines are surrounding this square.
Abomb is represented by an asterix, *.
Each turn, the square grid is printed out and input is taken via
the command line. The aquare grid contains the coordinates starting
from 0 to (size-1) on both labelled axes. The x-values change as
you move horizontally while the y-values change as you move vertically.
The bottom-left corner has coordinates (x,y) = (0,0). An input is
of the form: xcoord ycoord. The user is prompted until he enters
a valid input.
A valid screen printout could look like the following:
3 ? ? ? ?
Y 2 ? ? ? ?
1 ? ? 2 1
0 ? ? 1 ?
0 1 2 3
X
Enter Move:
The program processes the input and uncovers the square. If the
square does not contain a bomb, then the program draws the new
minefield. If the area did contain a bomb, then the program quits,
informing the player thta he/she has lost.
If the player is confident that he has found all the bombs and
the only squares which remain uncovered are the bomb squares,
he enters "ok" at the input prompt. If the only remaining
uncovered squares indeed all contain bombs, then the user is informed
that he won and the time played is printed out. Otherwise, the
player loses.
We did not attempt to solve this problem.
- To Big O or To Little O? That is the Question. (Algorithms)
The algorithm competition involves problem solving as well however,
the solutions required a somewhat detailed method to solve the problem
rather than just the answer. For example, we had to come up with 2
methods for generating any Fibonacci number and dictate each step.
- Rage Against the Binary Machine (Assembly/Performance Programming)
This was another of those awesome events. JJ, Ben and Rusty earned
3rd place here.
The contest was to solve some problems in Mjollnir assembly language.
It is a stack based language that runs on a virtaul machine, so think
Java.
Everybody was given a tutorial and quick reference of the language
to study, the night before. We reviewed it and after being confused
from the documents, were worried about the contest. It seemed to us
that there was lot of inter-contradiction in the documentation, things
like order of arguments in subtraction and loading instructions.
Well, our fears became reality when we tried out the assembler. Hardly
half of the documented instructions worked the way we expected! We
were adapting to the situation and making things work, when we noticed
that other teams were complaining about the broken assembler. At that
point we got quiet and worked at our own pace, which was always a
few steps ahead of other teams. It was fun to discover that left shifts
were not working, make a procedure using multiplication, and 5 minutes
later hear everyone complain about left shifts.
Here is a sample question:
CRC32 compilation
The Cyclic Redundancy Code 32. Convert this C algorithm to Mjollnir
assembly. You are not required to code up the exact algorithm
as shown below, as long as it is the same algorithm and performs
the correct computation, you will recieve full marks.
unsigned long crc32(const unsigned char *s, unsigned int len)
{
unsigned int i;
unsigned long crc32val;
crc32val = 0;
for(i=0; i< len; i++)
crc32val =crc32_tab[(crc32val^s[i])& 0xff]^(crc32val >>8);
return crc32val;
}
Start stack
1. pointer to u634s: value to compute the crc32 of
2. pointer to u64s: tab values
End top of stack
1. u64: correct crc32 value
Solved it. Was about 100 assembly instructions.
- Live Another Night (LAN Gaming)
Three games were used as media to determine the school with best gamers:
Midnight Club 2, Moonbase Commander, and Desert Combat.
JJ, our racer, placed an extreme first place in all his races. However,
the tracks that he competed in were longer than the tracks that 2/3
of the other races were held in, and the scores were based on time
completed. So of course we had to bring this to authorities attention.
Moonbase Commander is a turn based strategy game, chosen for the specific
reason that probably no one had ever played it. Brent did fairly well,
of course losing to the player who downloaded the game and practiced
all weekend.
And John totally killed without bias everybody who appeared on his
screen in Desert Combat.
- Snapenger Hunt (Scavenger Hunt)
Cram people in a pone booth! Take pictures of dancing locals! Find...
more stuff!
Teams were paired off to cooperatively collect as much strangeness
as possible.
- Other events
At some point in every day there would be a few team members with
no current task. To put good minds to use, each day there was a Problem
of the Day. Of course, we bossed all the other teams and correctly
answered all three questions. One of the questions asked involved
dice and the abbreviations of the names of the months. Another one
was a chess game where you had to achieve and outcome in a certain
number of moves. I dont remember the exact details of them, but trust
me when I say it was awesome.
A less awesome event filled saturday afternoon. Instead of playing
ball in the gym, we all did some improv comedy. Our team did alright,
and Dom Lacoste was a hit, but there wasnt much funny occurring.
Finally there was a "participation points" category for
scoring. Doing things like yelling your schools name and wearing a
costume earned you points. Also you could make a video to intimidate
the other teams. See ours: RPI FlashOut! The crowd loved the video.
We got ruined in the rest of this category, but we feel it doesnt
count for anything, because we know we had fun.
|