Board game AI design: choosing STL data container

I'm coding an AI engine for a simple board game. My simple implementation for now is to iterate over all optional board states, weight each one according to the game rules and my simple algorithm, and selecting the best move according to that score.

As the scoring algorithm is totally stateless, I want to save computation time by creating a hash table of some (all?) board configurations and get the score from there instead of calculating it on the fly.

My questions are:

1. Is my approach logical? (and if not, can you give me some tips to better it? :))

2. What is the most suitable thread-safe STL container for my needs? I'm thinking to use the char array (board configuration) as key and the score as value.

3. Can you give some tips for making my AI a killer one? :)

edit: more info:

The board is 10x开发者_如何转开发10 and there are two players, each with 10 pawns. The rules are much like checkers.

Yes it's common to store evaluated boards into a hash table it's called transposition table. A STL container could be std::vector. In general you have to create a hash function (e.g. zobrist hashing). The hash function calculates a hash value of a particulare board. The result of hash_value modulo HASH_TABLE_SIZE would be the index to the std::vector.

A transposition table entry can hold more information than only board-score and best-move, you can also store to which depth the board is evaluated and if the evaluated-score (in case you are doing alpha-beta search) is

• exact
• a Upper Bound
• or Lower Bound

I can recommend the chessprogramming site, where I have learned a lot. Look for the terms alpha-beta, transposition table, zobrist hashing, iterative deepening. There are also good papers for further reading:

• TA Marsland - Computer Chess and Search
• TA Marsland - A Review of Game Tree Pruning
• AL Zobrist - A New Hashing Method with Application for Game Playing
• J Schaeffer - The games Computers (and People) Play

Your logical approach is ok, you should read and maybe try to use Minimax algorithm :

http://en.wikipedia.org/wiki/Minimax

I think that except from tic tac toe game the number of states would be much too big, you should work on making the counting fast.

Chess and checkers can be done with this approach, but it's not one I'd recommend.

If you go this route then I would use some form of tree. If you think about it, every move reduces the total possibilities that existed before the move was made. Plus, this allows levels of difficulty. Don't pick the best all the time, sometimes pick second best.

The reason I wouldn't go this route is that it's not generally fun. People pick up on this intuitively and they feel it's unfair. I wrote a connect 4 game that was unbeatable, but was rule based rather than game board state based. It was dull. Every move was met with the same response. I think this is what happens in this approach as well. Also, it depends on why you are doing this. If it's to learn AI, very little AI is done like this. If it's to have a fun game, it usually isn't. If it's for the reasons Deep Blue was made, to stretch the limits of what a computer can do, then sure.

I would either use a piece based individual AI and then select the one with the most compelling argument or I would use a variation of hill climbing and put a kind of strategy height into the board. It depends on how much support pieces give one another. For the individual AI I would use neural nets.

A strategy height system would be good for an FPS where soldiers want to know what path has the most cover. Neural nets give each entity more personality. You can even use cascading neural nets where one is the strategy and the second is the personality.