Why an AI for Outwitters is hard to do

[Cookie]

Yes, probably hard, but not actually that hard. E.g. much much easier than Starcraft.

First step: Remove the fog of war (no need to do this in the end, but necessary when you start writing the AI).

Second step: Some kind of goal based search. Goals will be things like taking out units, see a large portion of the board, hitting the base, and create new units. Actually, the branching is not that high in practice, because for many things there will be one or a few best moves.

The one tricky thing is the balance of building up an army and attacking the base. But this is hard for human players too.

I am not saying it is easy. But also, I don't think it is quite as hard as you make it sound. Summoner Wars is one recent similar game for iOS with AI. It does not have fog of war, but it does have high branching and the players have hands that are hidden to the opponent. The AI is not very good, but it is passable.