Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Is there a generic platform to allow me to customize the rules to a board game. The board game uses a square grid, similar to Checkers or Chess. I was hoping to take some of the work out of creating this computer opponent, by reusing what is already written.

I would think that there would be a pre-written routine for deciding which moves would lead to the best outcome, and all that I would need to program is the pieces, legal moves, what layout constitutes a win/lose or draw, and perhaps some kind of scoring for value of pieces.

I have seen chess programs that appear to use a recursive routine, so they think anywhere from 2 to 20 moves ahead to create varying degrees of difficulty. I have noticed this on chess.com. The game I am programming will not be as complex.

Is there a platform designed to be re-used for different grid/piece based games.

JavaScript would be preferable, but Java or Perl would be acceptable.

share|improve this question
2  
What to tag... Should there be a tag for board-games? –  George Bailey Jul 3 '12 at 14:51
1  
meta.gamedev.stackexchange.com/questions/316/… - unfortunately the consensus of the time seems to be that this site is intended for video game development only (a shame at least to my mind, but the current law of the land), and while there are computer implementations of board-games I can see a concern that the tag might encourage people to post non-video board game questions here. –  Steven Stadnicki Jul 3 '12 at 16:22
add comment

migrated from stackoverflow.com Jul 3 '12 at 14:20

This question came from our site for professional and enthusiast programmers.

1 Answer

up vote 1 down vote accepted

It seems you're looking for an implementation of the minimax algorithm, and you're willing to program the move generator and evaluation function (the domain specific parts). Having developed a chess engine, I can tell you that a basic minimax search routine is easy to code and produces excellent results (good enough to defeat most human players). Here's some pseudo-code to give you any idea:

minimax(depth, color)
    if depth is 0
        return evaluation()
    if color is ai             // maximize score
        bestvalue := -infinity
        foreach move in move list
            value := minimax(depth - 1, opposite color)
            if value > bestvalue
                 bestvalue := value
    else                       // minimize score
        bestvalue := infinity
        foreach move in move list
            value := minimax(depth - 1, opposite color)
            if value < bestvalue
                 bestvalue := value
    return bestvalue

The algorithm recursively chooses the line that produces the best score assuming optimal play by both sides. These board games are usually symmetrical; your gain is the opponent's loss, which is why one side maximizes while the other side minimizes the score. Don't worry, there are much better explanations out there. :)

As you can see, all it needs is a move list and evaluation function; it doesn't care about the board representation and such. There are many ways to improve on minimax (some are domain specific, others are not) if you need a stronger search.

This is a piece square table:

int[] KnightOpeningPositionValue =
{
    -25,-17,-17,-17,-17,-17,-17,-25,
    -17,-12,  0,  8,  8,  0,-12,-17,
    -17,  0,  8, 12, 12,  8,  0,-17,
    -17,  8, 12, 17, 17, 12,  8,-17,
    -17,  8, 12, 17, 17, 12,  8,-17,
    -17,  4,  8, 12, 12,  8,  4,-17,
    -17,-12,  0,  8,  8,  0,-12,-17,
    -25,-17,-17,-17,-17,-17,-17,-25
}

It adds a specific value for having the knight at a certain square. This is great for encouraging decent positional play. Make sure kings have 2 such tables, as the king should strive for the corners in the opening, and should try to center in the endgame.

share|improve this answer
    
OK, so I just need to double-check.... the evaluation function that I need to code. For chess would it be the following: checkmate=infinity (whether positive or negative), stalemate=0, otherwise the sum value of the pieces? I suspect it is this simple, but I wanted to double-check whether this type of evaluation function would produce reasonable results, or if I would need to produce some additional rules? –  George Bailey Jul 12 '12 at 21:22
1  
Checkmate and draws are usually handled within the search. If the move list is empty and you're in check, then it's checkmate. However, these values are kind of tricky because of path dependency; you want the shortest mate, or you might keep returning a mate score and never actually win. For the evaluation, you should get good results by considering piece values and using piece square tables (example in answer). –  Zong Zheng Li Jul 12 '12 at 22:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.