If it's a general turn based game of some kind, I think both strategy and tactics are the way to go over a brute force type of method (as everybody else has suggested). You can find a lot of info on realtime strategy and tactics on CGF-AI, and it shouldn't be too hard to adapt it to a turn based game. The hardest part is probably making good use of the extra processing time you have (compared to a realtime game, since a turn based AI can take several seconds per turn without frustrating the player) without taking too much time (minutes would start to get annoying).

Quote:

Original post by alvaro The first thing I would try is depth 1 search. Concentrate on getting a strong evaluation function that will play reasonably well even with such minimal search...

Thats just what I did to start off. It takes about 1 second to make a move and the play is indeed quite good.

I discovered that having formations doesnt work too well as the pieces need to keep moving freely. Although there are a (very) few places where it might be helpful to have your players positioned, the evaluation function easily handles this. So there I think the current approach is working fine.

The next thing I try will be to expand a few selective moves as some people suggested.

And I had a thought - just a thought - that rather than looking at all the moves and filtering out the bad ones (which is essentially what i'm doing now), why not just generate the ones likely to be good? Something like: it would be nice to move a piece here, what pieces can come here?
If that is faster, then once such 'likely good' moves are generated, they could be explored further, and we have a much smaller tree...
Does that make any sense?

Quote:

Original post by pacman2003 [...]And I had a thought - just a thought - that rather than looking at all the moves and filtering out the bad ones (which is essentially what i'm doing now), why not just generate the ones likely to be good? Something like: it would be nice to move a piece here, what pieces can come here? If that is faster, then once such 'likely good' moves are generated, they could be explored further, and we have a much smaller tree... Does that make any sense?

Yeah, that's basically how you'd implement the suggestion of strategy and tactics. It sounds really simple, but you can make it _very_ complicated (such as generating not only good moves, but also N-turn plans to eventually get a piece in that position.
You do need a good heuristic also, though, because if you try an alpha-beta search that only considers obviously good moves, a 'bad' move might win the game since it was never considered by the AI (kind of like sacrificing a queen for a guaranteed checkmate a variable number of turns later).

Regardless of the direction you search (forwards or backwards), you need to really work on the evaluation function (and honestly the direction shouldn't affect speed that much. taking a full second to evalute only the possible moves for a single turn sounds pretty bad - is that for also considering the opponent's response to each possible set of moves?)