What's a Good Mobile-Friendly Game to Build a Pattern Matching AI For?

Question

So, I have a grad class on artificial intelligence and our final project was to implement a softbot in Java to play minesweeper. Well, I'm having a lot of fun, but when I discussed this project with my buddy who I write iPhone games with (or more aptly I've done the art, he's done the programming, for the most part for our past games), he pointed out to me -- "In an app version, wouldn't your AI adversary already know where all the mines are and just pick a wrong move a certain amount of the time depending on the difficulty?"

That got me thinking... I really enjoyed this class and was hoping to apply it in some way to a mobile app, perhaps an Android app. But he's right... this is a case where knowledge of the world is equivalent to an automatic win, so there's no real need for AI, even for a human v. computer "race" sort of minesweeper contest.

So here's my question: What's a good game that I can attack with a pattern-matching based AI, which actually NEEDS AI for a computer player to do well (i.e. full knowledge of the world is not good enough for a solution)?

I figured Go was too intense to be able to implement well on a mobile device, so all the remaining games I could think of seemed like more candidates for traditional adversarial search w/ pruning (which excites me less), e.g.:

• Chinese checkers
• Classic checkers
• Chess

I wanted to get you guys' ideas, though, as it would be fun to do a more novel game perhaps, and I'd love to do something like minesweeper, which involved pattern matching, rather than just an adverserial minmax search.

So kudos if you can think up any classic games that can utilize a pattern matching heavy solution, where knowledge of the world does not guarantee a win.

(P.S. I'm putting this under homework. It's not for an assignment, but I figured since it relates to my final project in a roundabout sort of way I might as well make it clear it's origins are school related...)

EDIT To clarify, of course I could just do a real-time game w/ AI or try to invent my own puzzle game, but I was kind of thinking of doing a pre-existing board based game... Just trying to think of one with pattern matching in it...

EDIT 2 As the first answer pointed out chess could be done well on mobile hardware. I'm still hoping for pattern matching, though.

Answer 1

I think today's handhelds are suitable for chess; at least, I seem to remember that there were chess programs on my HP48 calculator that routinely beat me:

• http://www.hpcalc.org/details.php?id=795
• http://www.hpcalc.org/details.php?id=3067

4MHz and 128KB of memory. Oh yeah.