Creating a non-perfect game algorithm

Question

I know how algorithms like minimax can be used in order to play perfect games (In this case, I'm looking a game similar to Tic-Tac-Toe)

However, I'm wondering how one would go about creating a non-perfect algorithm, or an AI at different 'skill levels' (Easy, Medium, Hard etc), that a human player would actually have a chance of defeating.

Answer 1

Cut off the search at various depths to limit the skill of the computer. Change the evaluation function to make the computer favor different strategies.

Non-expert human players play with sub-optimal strategies and limited tactics. These roughly correspond to poor evaluation of game states and limited ability to think ahead.

Regarding randomness, a little is desired so the computer doesn't always make the same mistakes and can sometimes luck into doing better or worse than usual. For this, just don't always choose the best path, but choose the among them weighted by their scores. You can make the AI even more interesting by having it refine its evaluation function, i.e. update its weightings, based on the results of the game. This way it can learn a better evaluation function at limited search depth through playing, just as a human might.

Answer 2

One way i use in my games is to utilize random value. For easy game levels, i let the odds of selecting a random number in the favor of the human player. Example:

Easy level: only beat the human if you can randomly select a value less than 10 from the range of 1 to 100

Medium level: beat the human if you can select a random value which is less than 50 from a range of 1 to 100

Hard level: beat the human if you can randomly select a value less than 90 from a range of 1 to 100

I am sure there are better ways, but this might give you an idea

Answer 3

the "simplest" way would be to use a threshold value along with your minmax results, creating a set from those results that exceed the threshold, then randomly select a choice/path for the program to take. the lower the threshold the possibly easier opponent.

i say possibly because even by pure dumb luck the best move could be selected, hence "Beginner's Luck".

essentially, you are looking to increase the entropy (randomness) of the possible outcomes. if you want to specifically dumb down the computer opponent, you could limit the levels your minmax algorithm traverses, or devalue the points for some portion of the algorithm.

Answer 4

It is not easy for a engine to make human mistakes. Reducing the search depth is a straightforward approach but it has its limits. For example, chess engines that are reduced to one ply often give check while one valuable piece is still attacked. When the opponent defends the check with a counterattack, both pieces are en prise. It is unlikely that even an inexperienced human falls for this mistake.

Maybe you can use some ideas from a chess engine called Phalanx: http://phalanx.sourceforge.net/index.html

It is one of the few open source engine that has a sophisticated difficulty level (-e option). If I'm not mistaken, it performs a normal search but sometimes ignores non-obvious moves. evaluate.c contains a function called blunder, which evaluates whether a move is likely to be overlooked by a human.