Efficient board representation for strategy board game AI

Question

Would a bitboard representation still be as effective in a dumbed-down chess-like strategy game which has less than 64 positions or would a simpler array based mailbox implementation be more practical?

Our school's AI class has an annual competition where the professor makes up a board game and we have four weeks to create an AI which plays the game. Typically, the pieces are a subset of chess pieces with similar rules and is played on a smaller board. i.e. 8x5, 7x7, etc. I'm not at all sure how using only 40 bits compare to the typical 64 for chess.

My only issue is that I'm not very familiar with C or C++ and would be more comfortable implementing the program in Java. Is their enough support in Java for bit manipulation where I could implement a bitboard representation and if this would add efficiency, would it be worth the added complexity? Would the learning curve be too steep?

My plan is to use Negamax search with AB pruning, quiessence search, transposition tables, killer moves, etc. depending on time. Any other tips for creating a competitive AI in such a short amount of time?

Answer 1

A bitboard would work, but in my opinion, the added effort and complexity just to get it working properly isn't worth any possible gains in computing efficiency later on.

In the overall scale of things, any efficiencies from bitwise masking (& or |) over fetching an element of an array (or even a List or Map) would be largely overshadowed by whatever AI or search algorithm you intend to use.

That is, an algorithm of exponential or polynomial complexity will still take O(e^n) or O(n^d) and what few CPU cycles you save with binary arithmetic over pointer dereferencing will be insignificant.

Just go with the easiest data structure you can use at this point (probably an array, or whatever Collection) and focus on getting your algorithms to work.

Later, if you have time, you can profile your program and if you find that array lookups are taking up, say, 20% of your run-time then maybe, just maybe, consider refactoring everything to bitwise ops.

Personally, I'd look at possible ways to conduct the searches of the solution space in parallel, to maximize multiple CPU cores, or better yet, in a way that can be distributed across multiple compute nodes. Yes, that'd probably qualify you for at least Master's degree if you discover something really clever. :)

Answer 2

In university I had game AI writing competitions similar to yours, and I achieved the biggest speedups not when I worried about some little minutae like 'is coding things statically faster' or 'will sanity checks slow my program down?' but 'If I write my AI to be smarter/more efficient, it will perform a level of magnitude better, so I'm going to implement this cool new trick I found'.

Usual examples of staggering speedups are alpha-beta pruning, killer heuristic and choosing a good algorithm for calculating the strength of a game state (note that good != more accurate - it could also mean faster and still accurate. After all, if your score calculation is simpler it lets you look more moves ahead, which means you make up for it in spades).

Answer 3

You might as well use bitboards. It's not really that complex, and you get a significant speedup in move-generation and static exchange evaluation. Your AI algorithm, no matter how clever, will still need to do a ton of those.

There's a very good website on the subject: chessprogramming.wikispaces.com/Bitboards

Since your boards are a different size some tricks may not apply, depending on how you assign bits to squares. On the other hand, since it's only a subset of the pieces, some problems that were traditionally problematic to solve with bitboards may not exist.

Answer 4

Setting individual bit in bit scale is usually slower than settings element in boolean array, because the former requires read + bitwise AND/OR + write, while the latter requires just write.

Reading individual bit in bit scale is also slower: read + bitwise AND/OR + shift versus just read.

So if your AI will need lots of reading/writing states of individual board cells, than boolean array will be more effective. At the same time, operation of making a clone of the whole board is faster when board uses less memory, i.e. when cells are packed into bits. If your AI will clone bards often and do only few get/set operations between cloning operations, than bit scale is better regardless of the board size.