What are some games with fairly simple heuristics to evaluate positions?

Question

I'm teaching a kid programming, and am introducing some basic artificial intelligence concepts at the moment. To begin with we're going to implement a tic-tac-toe game that searches the entire game tree and as such plays perfectly. Once we finish that I want to apply the same concepts to a game that has too many positions to evaluate every single one so that we need to implement a heuristic to evaluate intermediate positions.

The best thing I could think of was Dots and Boxes. It has the advantage that I can set the board size arbitrarily large to stop him from searching the entire tree, and I can make a very basic scoring function be the number of my boxes minus the number of opponent boxes. Unfortunately, this means that for most of the beginning of the game every position will be evaluated equivalently with a score of 0 because it takes quite a few moves before players actually start making boxes.

Does anyone have any better ideas for games? (Or a better scoring function for dots and boxes)?

Answer 1

Samuel was one of the first to make effective use of heuristic search methods. You can refer the following link:http://incompleteideas.net/book/first/ebook/node109.html

Another game choice could be Reversi aka Othello.

A naive heuristic would be to simply count the number of tiles gained by each valid move and choose the greatest. From there you can factor in a board position and minimizing vulnerable to the opponent.

One game you may consider is Connect Four. A simple game with straightforward rules but more complicated than Tic-Tac-Toe.

If you want to know Heuristic Search Method In Artificial Intelligence then visit this Artificial Intelligence Course.