We have an app called Shape Chess... it is a variation on chess... unfortunately the AI is extremely weak... I have found it extremely challenging to program the AI without the CPU taking extremely ridiculous amounts of time to make a move... Any advice or tips.. or books for this type of thing? I've seen chess-engines available to use, however this won't help me since the game isn't exactly chess...
Would you be able to use an open source engine? GNU chess comes to mind. However you must read the license agreement CAREFULLY..
If you're writing your own AI, you could try to prune the decision trees so that they're not evaluating too many levels deep. Or perhaps you could try to write some heuristics that mighty help you avoid diving down certain branches.
Hi, I am a chess programmer myself in my free time. This websites contains a lot of useful information: http://chessprogramming.wikispaces.com/
If you don't visit them already I'd recommend: http://aigamedev.com/ http://ai-depot.com/GameAI/Design.html Both have been around for awhile and are excellent resources.
We wrote a chess AI based on min/max trees and a shallow move history. Researching those topics and how to build and recurse through a knowledge base will start you on the right path. Also follow Xyzl's advice and check out GNU chess.