Historically, my AI has been more like...Artificial Ignorance. I just never delved too deeply into this portion of the technology.

I recently finished a prototype of my game concept. Programming wise, I was delighted to see logic separated in a way that it was straightforward to make two players set to CPU and then sit back to watch the game unravel. After reviewing my prototype though, I felt the game needed more fun factor, so I changed some of the fundamentals. While the game feels more legit, the AI mechanics are now pretty broken.

I'd like to give a brief synopsis of my game and my theory of a AI methodology to see your thoughts.

Synopsis
{"name":"609157","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/4\/0433a8a44d64fa042e21ffa79cb6bba1.png","w":640,"h":1136,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/4\/0433a8a44d64fa042e21ffa79cb6bba1"}
There is a hex grid with spawn points for two different players and a random set of obstacles (walls along an edge or a grid space that is completely impassable). Each player draws 7 hex "tokens" (pretty much "cards") from their shuffled deck (not going to cover how the deck is built here) and one player gets to go first.

The tokens can be either a Pawn or an Effect. A Pawn can be played on a spawn point on the grid, has health points, a color attack strength and has triangular arrows pointing outwards. If an edge of the token has an arrow, that's a way a pawn can attack. If no arrow, an opponent Pawn can blindside the Pawn on that edge.

Effect tokens change things at a global or Pawn scope when played. For example, restore a Pawn's health or remove an opponent Pawn from the playing field. There's also Spell effects that certain Pawns in play on the grid have to cast.

During your turn you can: spawn a Pawn token, play an Effect token, discard a token in your hand, slide a Pawn on the grid or rotate a Pawn on the grid. For the last two options are chosen as the turn's move, if two opposing Pawns are adjacent to each other and either one has an arrow pointing at the other, combat ensues. If both are facing each other, the Pawn with the greater attack strength does damage to the one with the weaker strength (damage dealt is equal to the difference in this situation). If a Pawn's hit points get to 0, it is removed from the field and the victor is awarded a point (or more if the Pawn is worth more).

Pawns have different tags/abilities that change the rules above. For example, one Pawn might have a "Wolf" tag and it might be able to move up to two spaces in one turn. There might be an Effect token that doubles the strength of all Pawns that are a "Wolf". The "colored" attack strength is also part of the definition of the Pawn which means different things to different Effects.

AI Idea
I am thinking of doing the following:
copy the grid to memory -> consider all moves -> for each move, consider all opponent's potential moves with what's showing (AI doesn't know what's in the opponent's hand) -> for each opponent move -> consider one last move. This would produce an Outcome object with varying statistics (how many points were earned, how many of your Pawns were lost, defensive rating, etc.).

This process would create a lot of Outcome objects of which the AI could evaluate and then pick one to go forth with.

In the image above, if Red is the AI player, it's consider all moves:
Pawns it can spawn: 5
Adjacent spaces a pawn on the field can slide to: 12
Possible rotations (5 per Pawn): 20
Effect tokens that can be played (assuming all): 2
Possible moves for Red: 37

For the 2 green in play:
Adjacent spaces a pawn on the field can slide to: 10
Possible rotations (5 per Pawn, except the one who has arrows in all directions): 5
Possible moves for Green: 15

And one more time for Red, we'll say another 37 possible moves for approximation (they may have one less card in their hand or there may no longer be a valid spawn point after their first move, etc.)

This yields 37 x 15 x 37 possible Outcomes: 20,535 possibilities. My fear is this could grow to be unmanageable (mobile platform). I plan on making the code such that I can tell how many turns to look forward (above is looking 3 ahead) to mitigate this.

Anyway, after these Outcomes, I'm going to have Strategy objects the AI is currently going for. A strategy might be, get more Pawns on the grid, get points, capture spawn points, etc. AI will also have Traits (like defensive-minded or risky player) which help pick the strategies. The possible outcomes + the strategy chosen based on the AI's traits determine which Outcome it chooses and thus dictates what the AI plays for its turn.

Thoughts?

As Max said, what you've described is a space of states that can occur during a game (by a state I mean given player hands at a particular turn, pawns and their attribute levels on board etc.). As you have guessed there's lots of states and traversing the whole decission tree of all these states is infeasible.

Instead one can either apply some min-max logic for picking up the next action. In your turn (by your I mean the respective AI) you try to maximalize the outcome. Then you simulate opponent's turn and you try to maximize his outcome which is actually minimal outcome from your point of view, hence the name.

As Max suggested, Alfa-beta pruning can reduce the number of suitable turns by pruning non-perspective branches. Other thing to keep in mind is that you should limit the number of turns you look ahead. The algorithm itself is quite easy, what is not easy is assigning a meaningful metric to the turn outcomes. Bad metric means that the algorithm will pick bad moves. Finding a good metric will take lots of trial and error runs.

Or you might then consider some self-learning algorithm either to find the metric or to drive the AI itself. This is not my field of expertise either. For me the AI indeed meant artificial ignorance as you put it. I did few things some time ago, but mostly trivial ones like described above for classic battleships game written in Prolog. Last time I did some AI it was an UT2k4 bot that should have been been capable of playing capture the flag. We decided to go the easy way and implemented simple if-then-else logic. Whis suprisingly worked well, but I don't think it's applicable in this case.

That's why you look ahead say 5 or 10 turns, not just one, for example, that would turn it into a simple greedy algorithm. Somehow, it would work, but wouldn't be much smart.