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.