The game is Bagh-Chal.
Minimax with Alpha-beta pruning that Lirik mentioned is a good place to start, but it takes some time to wrap your mind around if you're not familiar with it.
Alternatively, you can think about how you would play the game if you had a perfect memory and could do fast calculations and try to implement that. The upside is that's usually easier to understand.
Minimax would probably result in shorter but more difficult to understand (for those unfamiliar with it) code that depending on the game, could result in playing a perfect game if the game is simple enough (however it also has the disadvantage of favoring not losing to winning because it assumes the opponent will be playing perfectly as well).
Since it sounds like it's a game of complete information (the whole board is visible to all players at all times) a properly implemented Minimax with infinite look-ahead could give an AI that would never lose (assuming infinite computation time). In games using Minimax, the difficulty level is often determined by how many moves ahead the algorithm looks at.
If you wish to learn about Artificial Intelligence then visit this Artificial Intelligence Course.