Scribd says: Beat our programmers at a coding challenge
coding.scribd.com
coding.scribd.com
Here is his website: http://www.cs.columbia.edu/~kar/teaching.html
Each semester consists of 4 different open ended programming problems like these. You work as a team to compete against other members of the class. There's no tests and each class is run as an open seminar where people talk about their strategy and implementation and consider the best approach to solving these problems.
This was my favorite from my year: http://www.cs.columbia.edu/~kar/4444f02/node18.html
It's like when people get to a certain level of wealth they stop sending status signals.
The game starts off with Apples Bananas and Oranges, but ends with Apples, Bananas and Melons.
Robots are a wise choice for safety's sake when dealing with quantum fruit.
Easiest thing to throw together now is a script which just feeds the whole game history into bayeselo as a bunch of fake chess matches, with the white move advantage set to 0. That's what was done for Tron.
* A good way to measure the potential recruit skills
* Gives a good fun experience to go over later at the interview, both verifying it is the recruit who coded it and setting common background beforehand
* You get people who showed some interest in your company, seeing the contest
* You get people who are interested in hacking around puzzles
[1] (I don't know if scribd sees it that way)
Even if they don't "win", they are greatly superior than a normal resume pusher.
There is just something extremely satisfying about watching your little robot run across a field collecting little fruit.
For me, personally, it sounds like an awesome question, but it's not clear how you would judge it. Let interviewees' bots fight?
Most candidates CANNOT write a string reverse function without the off-by-one error.
twitch
Deleted comment
(fyi, one half of the team who built the game does not possess a dick)
Was there some innuendo somewhere that I missed?
The first priority would be to quickly pick up the vocabulary: what is a state, what is a utility function and so on.
I recently took a class on AI and we used the (rather popular) Artificial Intelligence: A Modern Approach by Russell and Norvig [1]. I didn't actually read the book, but I've heard good things about it so it's definitely worth a look.
[1]: http://aima.cs.berkeley.edu/
All the lectures for the course are available online as well[2]. The professor my semester (Dan Klein) was a brilliant lecturer, so the lectures are worth watching if you have the time. The lecture notes[3] are also online.
[2]: http://webcast.berkeley.edu/playlist#c,d,Computer_Science,9C...
[3]: http://inst.eecs.berkeley.edu/~cs188/fa11/lectures.html
Of course, if you want to participate in this game, you are doubtless in a hurry. So you might want to skim through lectures 2, 3, 6, 7, 10, 11 in roughly that order--they seem to be the most pertinent.
In an intro machine learning course you'd learn about minimax and others, but skip paying any money and just read the basic algorithms here and look up the wiki pages for even more examples: http://www.stanford.edu/~msirota/soco/blind.html (The introduction has some term definitions.)
Edit: Also, the obligatory plug for Artificial Intelligence: A Modern Approach http://www.amazon.com/Artificial-Intelligence-Modern-Approac...
Impossible.
Training phase:
Create a random board configuration. Exhaustively explore the search space to find whether this is a win +1, lose -1, or draw 0 for Player 1. You now have a training example: (board configuration, game outcome)
Now, train a neural network (or other non-linear ML model, e.g. SVM) to predict the expected outcome based upon the board configuration.
Deployment phase:
Port the neural network to Javascript. For each possible move, use the neural network to predict the outcome of that move. Pick the move with highest expected outcome. The neural network will run in constant time, most likely well under 10 seconds per move.
Given that the search space can grow O(4^mn), this can be done only for endgame configurations. Further, not knowing any bounds on the board size makes the input representation difficult to define for a such machine learning approach. And, your target should probably be the weights of an evaluation function, rather than the exact game outcome.
As for the learning algorithm, I know TD-learning was found to be a good approach in various chess programs.
> For each possible move, use the neural network to predict the outcome of that move. Pick the move with highest expected outcome.
You would likely still want to run an alpha-beta search to pick the move to minimize the prediction error.
One thing though: I think resetting the board state should call new_game() again. This likely only matters when testing your bot, but it's nice for variables that need to be instantiated per each game.
It's pretty fun! My current greedy solution is called: SoGreedy. :)
Your bot is doing pretty well already. :)
Example of failed match : http://www.scribd.com/job_game/match/295703 This line for example 1 / 1 / 0 / 0 / 1 - first number is the fruit type - second number is the total fruits - third number is my fruits - fourth number is opponent fruit - fifth number is irrelevant (You'll never see 0.5 in the third or fourth number..)
Also, the API is wrong here : "return the index of that fruit (starting with 0)" => It starts at 1
About the bug: Try to trace() out a few messages in your make_move() function, that might tell you whether something went wrong (the logs will appear at the bottom of the game replays.)
function make_move() { return EAST; }
Besides, there's Number.prototype.toFixed().
We may also add additional languages in the future, like Haskell and Lua, and possibly some advanced playing modes.
What's happened with the ranking?
However, while my bot was compiling, I moved away from the page. Later on trying to resubmit, I kept on getting errors, until I changed the name of my bot submission.
More helpful error messages would greatly improve the whole process. :)
What kind of error are you seeing?
which then displays: Oops! Something went wrong. We're working on a fix. Please visit our homepage for some recommended reading to take your mind off of it.
I WANT HIM TO LIIIIVE AND PLAY WITH OTHER BOTS IN THE REAL WORLD ;_;
Thanks, but no thanks. Hire better developers if you need your algorithm.
There are many standard approaches to the general class of two player board games (they are clearly aware of these, with an alpha-beta based bot).
I would guess that what is going to differentiate winners from losers in this specific game are the exact specifics of the setup. So if they are looking for a solution to an isomorphic problem, it must be a very similar problem - as the general type of challenge is well understood.
It just looks like a neat game to me; I doubt its a cleverly disguised problem from 'social reading and publishing' that they are trying to get a cheap solution to..?
Coincidentally, I really like the game design. I took an AI course recently and we had some really similar using Pacman and Python, and that was fun too, but I would much rather use JavaScript and compete online than use Python and the annoying framework code they gave us.
Downvotes on the comment recognize the wrongly cynical views of the poster.