Why is the board so big? The size of the board has a huge impact on the number of possible states in the game.

If possible, you could try filling up the new squares with made-up pieces having less range for movement, but that's kind of a cheat.

I guess taking longer to think is just an unavoidable problem. The traditional Minimax style AI is the most commonly used for a reason. Other methods required less resources, but yielded weaker gameplay. But you could try implementing proto-types of both AI types in this project and comparing them.

Read:
http://en.wikipedia.org/wiki/Computer_chess#Brute_force_versus_selective_search

The same techniques are still applicable, but they just won't be able to get you as far. An AI for this game should at least be able to play at the skill level of a beginner. The biggest problem in board games is how the number of moves tends to increase exponentially as you look more turns ahead. Looking a few ply ahead should still be possible.

Make sure you implement quiescence search at the leaves, or your program will be really easy to beat. If you implement depth 1 and quiescence search (easy to do even on your large boards), you will be above the level of someone that just learned how to play. You should be able to get to something like depth 3 or 4, which is probably enough to beat most beginners. Of course, you need a reasonable evaluation function (proximity of pieces to the kings, pawns supporting each other and king safety are probably important).

Once you implement alpha-beta, the move-ordering heuristics you use will determine how deeply you can search. Use iterative deepening, killer heuristic, history heuristic, good captures first (static exchange evaluation would be good for this part), etc.

For games where the number of legal moves is typically huge, it becomes important to grow the search tree in a non-uniform manner. If you can develop a model for the probability distribution of the next move to be played from a given position, you can start with probability 1 at the root, multiply this probability after every move you make by the probability of the move and consider a node a leaf if its probability is below some threshold (instead of being a certain number of moves away from the root). This way you will spend more effort on interesting lines. This brings some added complexities, like the fact that the horizon effect may become worse. Just be careful to always explore the move that you think is best at least as deeply as any other move.

Anyway, that last paragraph is complicated to implement and you shouldn't even try it before you have a working program with a uniformly-growing tree.

By the way, did you make any progress since your first post?

I'd like to point out that while the minimax will suffer from increased board size.
So will the Human players. Possibly moreso.

In my own experience as a human player, with bigger game boards, the gameplay turns more into greedy reactions than longer term strategy. So Any minimax on the computer's part is probably going to look very intelligent.

Get hold of a copy of Zillions of Games, take the chess.zrf file and modify it to define the rules for your new chess variant. (Zillions is a generalised game-playing AI that would allow you to create a decent opponent in a few minutes).

You might also want to know that Battlefield Chess is (according to Pritchard's Encyclopaedia of CVs) a proprietary game by a company called Stracheck, invented by Serge Brochet in 1989. It's played by 4 players on a 16x16 board. You might run into trademark issues.

I hope you've play-tested the game lots... while some chess variants are fantastic - the vast majority are rubbish (and so don't catch on).

Quote:Original post by AfroFire
Buut, also be aware that I can't optimize as much as I would like to, a 22x22 sized board can't be represented by a single 64 bit word

So use bit packing on a larger data structure. If you could avoid for loops on a 64 or 32 bit word, then you can avoid them on a larger hyper-word.

I should mention that a lot of the top chess programs don't use a bitboard representation. The algorithms you use are way more important than the board representation. If you don't want to loop through a lot of empty squares trying to find your pieces when you are generating moves, keep a list of pieces.