Menu
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)?
856
Heuristic evaluation is an inspection technique where evaluators explore an interface using a set of usability principles, called heuristics [24]. Heuristic evaluation does not make assumptions about task structure, and it is flexible enough to be adapted to specialized domains [25,10].
In Tic-Tac-Toe, a possible heuristic evaluation function for the current board position is: +100 for EACH 3-in-a-line for computer. +10 for EACH two-in-a-line (with a empty cell) for computer. +1 for EACH one-in-a-line (with two empty cells) for computer.
A heuristic function, is a function that calculates an approximate cost to a problem (or ranks alternatives). For example the problem might be finding the shortest driving distance to a point. A heuristic cost would be the straight line distance to the point.
An admissible heuristic is a non-negative function h of nodes, where h(n) is never greater than the actual cost of the shortest path from node n to a goal. The standard way to construct a heuristic function is to find a solution to a simpler problem, which is one with fewer constraints.
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.
198
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
