I thought that the most interesting observation was in the paper and not in video, namely the use of pause in Bubble Bobble. As in Tetris, it often found that if it paused, it was happier about the results than if it didn't, but each step when paused let it try again to search for good moves and since it wasn't trapped like in Tetris, it eventually found them.
"Pretty simple" algorithm playing games quite impressively.
http://www.youtube.com/watch?v=xOCurBYI_gY
First, this is awesome - enjoy!
Paper here http://www.cs.cmu.edu/~tom7/mario/mario.pdf
One interesting observation made by Tom Murphy is that the AI found and exploited playable bugs in the game not (commonly) known to human players. I think it's a good example to have available suggesting what a really smart AI might look for to win.