How can I make a computer opponent for my board game?

Question

I am trying to create a game, not exactly checkers, but the level of its interactivity is on par with checkers as opposed to something more complex (I think) like chess.

Anyway, according to my analysis, the UI, gameplay, player turns, time constraints, rewards are very easy to implement.

What I find hard is the actual CPU logic.

I'm looking at checkers as an example because I used to play checkers on my PC and Nokia long before sophisticated modern AI became a thing. Are there techniques used in old checkers games that I could use to calculate which of its moves is the most advantageous for it to win the game?

I would implement a logic on my own but I need a special algorithm to compute every possible move, and this will def take me a decade to implement.

I am sure there is a smarter and quicker way but I have no idea.

Answer 1

You might be able to apply the minmax algorithm here. It can be applied to any turn-based game without information hiding, no randomness and a small number of possible moves each turn. The only thing you have to adapt to each game is the rating function.

First, you need a rating function. A rating-function analyzes the playing field, rates which player currently appears to have a better chance of winning, and outputs it as a positive (computer has an advantage) or negative (player has an advantage) number.

You could calculate the rating by simply checking material advantage: Who has more pieces on the board? A more advanced rating function might also check how the pieces are positioned. You could, for example, give a higher score to pieces which have many ways to move and few ways in which they can be attacked. You could also try to quantify progress to a strategical goal. In chess, that might be things like pawns being closer to promotion or control of the center of the board.

Writing a rating function which accurately judges the game situation is the part which requires the deepest understanding of the mechanics of your particular game. You might have to do a lot of playtesting.

Then you use this function to calculate the rating of every currently possible AI move followed by every possible player response to that move. Then pick the AI move where the enemy response with the worst rating (from the PoV of the AI) is still rated higher than the worst-rated response of every other AI move.

A cheap way to make the AI stronger is to not just explore one round in the future but even more rounds. But keep in mind that the computation time will increase exponential. A much more efficient and elegant way, however, is usually to improve your rating function so the AI can make better strategic decisions. When the game has a large number of possible moves each turn, the performance can be enhanced through alpha-beta pruning (not following obviously bad tree branches).

I am looking forward to some challenging matches against the AI of your game.

Answer 2

They used a rule based ai. The difference between regular programming and neural networks is the following.

In regular programming the Programmers get data and write rules to generate output.

In Neural networks the programmers get data and a set of expected outputs, write models and try to generate rules by training the models with random weights and variations.

For all digital games the rules are known beforehand and can be programmed, otherwise the game would never really end, because the rule to win or lose would be undefined.

Basic ai in modern games involves finite state machines, fuzzy logic, path finding, recursive calculation of many rounds beforehand to approximate the best success chance or strongest move before making a move (chess and round based games), handwritten ai often is cheating to provide the illusion of intelligence or challenge (halo 1)

I recommend to read the book "game ai programming by example".