Jump to content
  • Advertisement
Sign in to follow this  
AfroFire

Special-Chess AI

This topic is 4160 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!