Hand-Drawn Computer Graphics

I have seen three really beautiful animated pieces of art recently:

1. The game Machinarium, which was previously part of the 2nd “Humble Indie Bundle” of charitable games. I played through this game very quickly; were it book, I would say that “I couldn’t put it down.” It is a game where you control a robot character, by point-and-clicking them through various screens, and where no text/words are involved. It is perhaps the only video game I’ve ever played which required use of Menger’s max-flow min-cut theorem. It is made completely out of animated hand-drawn graphics but the design is flawlessly smooth and clean. It even has a Space Invaders sub-game. I cannot recommend it highly enough. (The other two games by the same company, Samorost 1 (free online) & 2, I also recommend for the same reasons.)
2. There was a wonderful hand-drawn-animated video on PhD comics today, about matter physics:
3. Thid, a video posted today on BoingBoing about education reform:

Also, I found out from the very same BoingBoing that the UK is having a referendum to switch to “Alternative Voting” (a.k.a. instant runoff voting). I hope it passes! The most interesting consequence if it passes to me would be the media reports… in the upcoming Canadian election for example, it is simple enough to say “40% of people polled choose Conservative, 30% choose NDP, 20% choose Liberal,” etc, but would you ever get the survey results in a newspaper to list all 120 orderings of the candidates like “2.4% prefer NDP > Conservative > Green > Liberal > Bloc, 1.1% prefer Bloc > Conservative > NDP > Liberal > Green”? This is actually somewhat relevant since Arrow’s Theorem, which I am teaching in class next week, implies that in any electoral system, voting optimally requires advance knowledge of how other voters will behave.

Curbing Academic Honesty

I ran across a paper citing the following:

Austin M J and Brown L D (1999). Internet plagiarism: developing strategies to curb student academic honesty. The Internet and Higher Education 2, 21–33.

Thankfully, the cited work has a slightly different title in real life.

The two authors who made this citation seem to have 2 additional papers all based on the same data, in addition to this weird typo. I think I’ll stick to other sources for my research project…

UPDATE: Another paper on education had the following to say:

We have conducted some studies of the use of two existing collaborative adventure games: Gauntlet (a “dungeons and dragons” game for up to 4 players on the Atari-ST) and Xybots (a D&D video arcade game for 2 players-also by Atari). Our interest in this study has been two-fold …

… preliminary results from the computer based work suggest that cooperation is better with the more impoverished representation of Gauntlet.

Although it’s certainly true that Gauntlet was one of the ST’s best, this also qualifies the paper for doofosity…

TopRock/Paper/Scissors-er

There is apparently a rock-paper-scissors contest, where you program a strategy in C++, to be hosted at UW in the first weeks of November. Registration goes until October 12. The exact rules are not yet announced, but here is a link to the announcement.

Good Ways To Procrastinate

Aside from watching tv, I have indulged in a few other wastes of time over the past few weeks. Some people from the fraternity in which I lived as an undergraduate sent me Desktop Tower Defense, which reminded me of StarCraft… finally though I think that particular game has run its course and I’m no longer addicted to it. Another student here (another Dave, in fact) showed me two neat “think outside the box” type of games… he’s on level 22 in the first and 6 in the second. Finally, this list would not be complete without Crack Attack, a ripoff of Tetris Attack (which itself is one of the top reasons for me to buy a Nintendo DS).

Short Problem

I am going to be a lecturer for CO 456, Introduction to Game Theory this fall. I’ve TAed the course twice and have been taking a program in teaching methodology so I am itching to try out some new techniques on the students.

Incidentally, on my fraternity’s mailing list someone sent out a link to a 25-item variant of the rock-paper-scissors game. (I.e., it is rock-paper-scissors-monkey-alien-tree-nuke-etc… and each item beats exactly 12 of the other items). In that spirit, these might be the first problems for my course. (If you don’t feel like doing it with 25 items, just do rock-paper-scissors).

Problem 0. Is there any strategy that will guarantee you always beat your opponent?

Problem 1. What’s a strategy that in the long run will guarantee that you expect to win as much as you lose, no matter what your opponent does? (Hint: flip coins or roll dice)

Polarium Advance is NP-complete

In the spirit of Tetris, Sudoku, Minesweeper, and other games, we recently determined at the C&O open problem session that the game Polarium Advance is NP-complete. There is a pretty straightforaward reduction from “Hamiltonian path in induced subgraph of a grid graph” to Polarium Advance. That problem can be reduced from “Hamiltonian path in bipartite planar graph of maximum degree 3” as was shown in a 1982 paper by Itai, Papadimitriou and Szwarcfiter. While it would be nice to have developed a paper, it is somewhat encouraging to know that their paper used basically the same idea that we were developing, we were just a quarter of a century too late.

Here’s the formal statement of Polarium Advance.
Input: Integers m, n; an m-by-n grid graph; a (not necessarily proper) 2-colouring of the grid.
Question: Is there a simple path on the graph, such that after inverting the colours on that path, every row is monochromatic?