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

How about Reversi? It has a pretty nice space of heuristics based on number of pieces, number of edge pieces, and number of corner pieces.

Answer 2

How about starting your Dots and Boxes game with random lines already added. This can get you into the action quickly. Just need to make sure you don't start the game with any boxes.

Answer 3

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 board position and minimizing vulnerably to the opponent.

Answer 4

Take a look at Go.

• Simple enough for kid on very small boards.
• Complexity scales infinitely.
• Has a lot of available papers, algorithms and programs to use either as a scale or basis.

Update: reversi was mentioned, which is a simplified variant of Go. Might be a better choice.

Answer 5

One game you may consider is Connect Four. Simple game with straightforward rules but more complicated that Tic-Tac-Toe.

Answer 6

Four in a line Hard enough, but easy enough to come up with an easy working evaluation function, for example, (distance to four from my longest line - distance to four from my opponent's longest line)

Answer 7

How about Mancala? Only 6 possible moves each turn, and it's easy to calculate the resulting score for each, but it's important to consider the opponent's response, and the game tree gets big pretty fast.

Answer 8

Gomoku is a nice, simple game, and fun one to write AI for.

Answer 9

Checkers will let you teach several methods. Simple lookahead, depth search of best-case-worst-case decisions, differences between short-term and long-term gains, and something they could continue to work on after learning what you want to teach them.

Personally I think that last bit is the most critical -- there are natural points in the AI development which are good to stop at, see if you can beat it, and then delve into deeper AI mechanisms. It keeps your student interested without being horribly frustrated, and gives them more to do on their own if they want to continue the project.

Answer 10

Rubik's Infinity's quite fun, it's a little bit like Connect Four but subtly different. Evauluating a position is pretty easy.

I knocked together a Perl script to play it a while back, and actually had to reduce the number of moves ahead it looked, or it beat me every time, usually with quite surprising tactics.

Answer 11

In regards to a better heuristic for dots and boxes, I suggest looking at online strategy guides for the game. The first result on Google for "dots and boxes strategy" is quite helpful.

Knowing how to use the chain rule separates an OK player from a good one. Knowing when the chain rule will work against you is what separates the best players from the good ones.

Answer 12

I really like Connect Four. Very easy to program using a Minimax algorithm. A good evaluation function could be:

eval_score = 0
for all possible rows/lines/diagonals of length 4 on the board:
    if (#player_pieces = 0) // possible to connect four here?
        if (#computer_pieces = 4)
            eval_score = 10000
            break for loop
        else
            eval_score = eval_score + #computer_pieces
            (less pieces to go -> higher score)
        end if
    else if (#player_pieces = 4)
        eval_score = -10000
        break for loop
    end if
end for

To improve the program you can add:

1. If computer moves first, play in the middle column (this has been proven to be optimal)
2. Alpha-Beta Pruning
3. Move Ordering
4. Zobrist Hashes