This is why he mentions that Karate Kid didn't work well, because one of the factors of a successful play-through was that your opponents health is decreasing, which is something that this AI doesn't look for.

I don't believe that was the case. From the video he mentioned it using the power kicks up all on the first enemy because they produced the most favorable outcome for that game, at the expense of later games when more powerful moves are needed (since the AI can't plan that far ahead).