Sign in to follow this  
AfroFire

Special-Chess AI

Recommended Posts

I am working on a chess game where the board is larger then 8x8, it's now 22x22. There are 22 pawns, 6 rooks, 6 knights, 6 bishops, 3 queens, and a king for each side. After reading through some books, and looking at the AI chess article here on GameDev, I'm a little worried that the AI is going to be too expensive using classical chess means. In Regular Chess, there are 400 variants for the computer to look at upon opening move. There are more then 1600 in Battlefield Chess... Is AI for this game just too unrealistic (I want SOME skill involved) or should it just stay multiplayer? -Bryan

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
The game isn't an idea I came up with, it's just a job I'm doing for someone else. However, I will inform them of the name issue. Thank you everyone for you input regarding the AI thus far, I'm still researching the AI - however, I am fond of the idea of the human player aspect being just as bad as the CPU AI anyways. Perhaps it won't be as bad as I imagine.

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 there are a lot of for loops. Any ideas on optimizing things like that? I might implement some OpenMP support and things like that.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Ah, interesting - Why wouldn't they use bitboards? I always figured a bitboard would be the fastest way to do checks?

Anyways, I keep a list of pieces, and they have pointers to the tiles they are currently on, as well as a list of tile coordinates they have the ability to move to, and the tiles keep a pointer to the piece on it as well - it's a cyclic thang.

Timkin? What do you mean a larger hyper word?

Thank you for the attention thus far.

Share this post


Link to post
Share on other sites
Quote:
Original post by AfroFire
Ah, interesting - Why wouldn't they use bitboards? I always figured a bitboard would be the fastest way to do checks?

Some things are faster with bitboards and some aren't. If you want to program a "bean counter", you can probably get a very fast one using bitboards, but a lot of the chess knowledge that should go in an evaluation function won't be particularly easy to write using a bitboard representation. Adding attack information to your representation can probably speed things up more.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I should mention that a lot of the top chess programs don't use a bitboard representation.


Really?
Rybka is a bitboard engine (at least according to the author) and it's currently pretty much undisputed that it's the strongest engine available.
Crafty is probably the top engine for which the source is available (hmm... maybe not these days, but it was when I was looking for a strong engine) - it's also bitboard.

Can you name a few strong non-bitboard engines? (Ideally with the source available).
I'd be very interested to see code.

Share this post


Link to post
Share on other sites
Quote:
Original post by alun
Quote:
Original post by alvaro
I should mention that a lot of the top chess programs don't use a bitboard representation.


Really?
Rybka is a bitboard engine (at least according to the author) and it's currently pretty much undisputed that it's the strongest engine available.
Crafty is probably the top engine for which the source is available (hmm... maybe not these days, but it was when I was looking for a strong engine) - it's also bitboard.

Can you name a few strong non-bitboard engines? (Ideally with the source available).
I'd be very interested to see code.

Fruit and Sjeng don't use bitboards (at least the versions whose code was publicly available didn't: Fruit used 16x16 and Sjeng 12x12). Neither does Diep (he made his move generator public some time ago, and I've talked to the author), and neither did Rebel (this last one is a little old). I don't have hard proof, but I think Fritz, Junior and Shredder don't use them either.

It is possible that now that 64-bit processors are becoming the norm, more and more chess programs will jump into the bitboard bandwagon, but one can write a very strong program using other representations. Bitboards are *not* the key to a strong chess program. Good algorithms, a good evaluation function, good testing procedures and absence of bugs are the key.

[Edited by - alvaro on April 29, 2007 12:02:39 AM]

Share this post


Link to post
Share on other sites
Bitboards are not inherently faster than other well optimized methods. Especialy not on the x86 line of CPU's (no fast Log2, BSF and BSR instructions are not fast)

Things like move generation and attack and pin detection are trivialy very efficient with bitboards, but other things that engines need are not automatically efficient at all such as actualy evaluating a board position.

Share this post


Link to post
Share on other sites
Quote:
Original post by AfroFire
Timkin? What do you mean a larger hyper word?


I simply meant a manually defined data type that is comprised of 2 or more primitive word types concatenated to form a longer word; and for which the basic bitwise operations are overloaded so that the longer word can be used in the same way you would use a primitive word.

Timkin

Share this post


Link to post
Share on other sites
Bitboards are used for performance reasons, precisely because processors natively support the right number of bits.
It probably doesn't make sense if you have to have another structure to make it work.

Share this post


Link to post
Share on other sites
Quote:
Original post by alun
Bitboards are used for performance reasons, precisely because processors natively support the right number of bits.
It probably doesn't make sense if you have to have another structure to make it work.


Certainly performance would not be as optimal. However, since overloaded operators for hyper-words are typically implemented in terms of native operations, the decline in performance is small (and can be measured by the number of primitive operations required to implement a hyper-word operation). From my experience it's a lot less of a performance drop than using non-bit representations for large state spaces. The worst case scenario is typically bit-shifting, where you need to preserve information that flows out of one word and into the next.

Anyway, I'm certainly not stating that this is the way that the OP should go. I merely indicated that one shouldn't let perceived hardware limitations (in this case native word length) dictate software solutions.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
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.


Most state-of-the-art chess AI now uses bitboards, and if they don't, they should ;) It's simply more efficient. Harder to read and debug? Yes... but a much more efficient use of pipelining/caching/registers. Just a more efficient use of computer architecture overall. Several years ago they weren't as widely used, but that is largely untrue today with 64 bit machines.

Quote:
Original post by alvaro
The algorithms you use are way more important than the board representation.


I disagree - I think they are both vitally important. If I'm using an array[][] and I have to do a multiply + add to access any position and I'm doing lots of for loops with conditional branches, I'm going to get much less done than someone else using a bitboard who can execute multiple queries simultaneously thanks to pipelining.

Quote:
Original post by alvaro
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.


Bitboards are used precisely because there is no looping to find where pieces are, where collisions are, etc. They are highly optimized for generating moves, far more efficient than the offset method.

Here are some interesting papers by Bob Hyatt (Crafty)
http://www.cis.uab.edu/hyatt/boardrep.html
http://www.cis.uab.edu/hyatt/pubs.html

The articles were written a few years ago before 64 bit machines were widely available, so the preference for bitboards has increased even more since then.

As for the Op post... I don't know. A simple array will probably do the job. Bitboards are so convenient for 'regular' chess because a 64-bit unsigned integer perfectly accommodates an 8x8 chessboard. If you are doing 22x22 or something odd like that, it's probably more work than its worth to use a more complex bitboard setup (unless this is a very hardcore project). It's complex enough for an 8x8 chessboard...

EDIT: Also, Sjeng does use bitboards... as of 5 years ago. I also would not be surprised if REBEL doesn't use them since it stopped being developed in 2004.

[Edited by - kosmon_x on April 30, 2007 6:23:00 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this