Transcript Hex Game - The Risberg Family

Hex
Combinatorial Search in Game Strategy
by
Brandon Risberg
Menlo School
May 2006
Background
• Where I got the idea:
• I first got the idea for “Hex” when we played it
during an Algebra 2 class period with Mr.
Squilante.
• I got the idea to make an artificial intelligence
for the game when I went to see the “Mastering
the Game” exhibit about computer chess at the
Computer History Museum.
Introduction
• “Hex” is a board
game defined by
the mathematician
Piet Hein
• It is a two player
game played on a
diagonal board.
Rules
• Both players trade off
claiming “hexes” on
the game board.
• The goal is to create a
chain of hexes from
your side to your other
side.
Java Game Programming
•
•
•
•
Used nested “Swing” components and graphics.
Imported image files created in Photoshop.
Used multiple threads to handle animation.
Implemented a recursive method to detect a
winning chain.
• Added help files and windows for ease of use.
• Created an opening splash dialog.
A.I. Algorithms
• Mini-Max
• Generate a move tree.
• Evaluate each position in tree.
• Select best move at each level:
• Minimize score on opponent move.
• Maximize score on own move.
Example Search Tree
A.I. Algorithms (con’t)
• Alpha – Beta pruning
• Pruning branches of the search tree that will
yield less favorable results.
• Improves search speed; does not improve
quality of moves.
• Heuristics or “Rules of Thumb”
• Guidelines that will help constrain the search.
Examples of Heuristics
• In real life:
• Menlo registrar must assign students to class
sections.
• This is a complex search problem.
• Heuristic: make the critical assignments first.
• Senior English sections (workshops) cannot be
interchanged, so begin with these.
• Freshman English classes are interchangeable so do
these last.
Examples of Heuristics
• In board games:
• In chess, keeping your pieces in the center will
usually be a stronger position.
• “A knight on the rim is dim”
• In Hex, a longer chain of connected hexes will
usually be a stronger position.
• This logic is typically built into the static
evaluator.
Care to try a game?