Developing a Minimax AI for Hex Game Challenge
MiniMax: The Game of Hex
Andrew Spano
The Game: Hex
Hex is a game played on a diamond or rhombus shaped board. Each player is
assigned a color and must build a contiguous bridge with his or her pieces from
one corresponding side of the board to the other.
The Challenge
Write an AI program which uses a minimax algorithm that can beat a competent
human player in the game.
Main Tasks
1)
Create a Representation of the Board State
2)
Create a User Interface for accepting input and displaying moves
3)
Develop method for testing for win condition
4)
Static Evaluation function using Djisktra’s algorithm
5)
Minimax
Representation of Board State
The Board is represented as a list of lists--Each list is a distinct row; each position
of the board represents the piece stored at that column
GUI representation
User Interface run as server.
Dotted Pair sent from interface to list
The Server
Sending the Move
Reading The Move
Testing for Win Condition
●
Must perform Depth first search to determine whether a connected bridge
exists
Adjacency Matrix
Depth First Search
Minimax
●
A minimax algorithm operates by building a decision tree of possible moves,
and assigning a value to how likely each is to result in, or bring the player
closer to, a winning state.
●
The Computer player chooses branches of the tree that maximize its score
and minimize the opponents score
●
Alpha Beta Pruning reduces the number of branches that have to be
evaluated by stopping a branch short if its value is guaranteed to be lower
than a previously calculated branch
Djikstra’s algorithm
Djikstra’s Algorithm
●
Find the shortest edge between nodes
●
Test if the destination node can be reached from the shortest edge. If it can,
repeat the process on its children
●
If it can’t, check the next shortest node
Work in Progess: My Implementation
I am using Djikstra’s algorithm as a static evaluation function. Each position on
the board will be evaluated for the shortest possible path from that position to the
player’s corresponding endpoints. The length of each path will be counted and
then negated
Questions?
Sources
Russell, Stuart J.
;
Norvig, Peter
(2003),
Artificial Intelligence: A Modern Approach
(2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 163–171,
ISBN
0-13-790395-2
Cormen, Thomas H.
;
Leiserson, Charles E.
;
Rivest, Ronald L.
;
Stein, Clifford
(2001). "Section 24.3: Dijkstra's algorithm".
Introduction to
Algorithms
(Second ed.).
MIT Press
and
McGraw–Hill
. pp. 595–601.
ISBN
0-262-03293-7
.
https://towardsdatascience.com/hex-creating-intelligent-adversaries-part-2-heuristics-dijkstras-algorithm-597e4dcacf93
http://www.dcc.fc.up.pt/~fds/aulas/PPD/1314/project3.html
Professor Doug Lea’s Notes
Creating an AI program using the minimax algorithm to challenge competent human players in the game of Hex. Tasks include board state representation, user interface design, win condition testing, and utilizing Dijkstra's algorithm for static evaluation. The AI builds decision trees to determine optimal moves, aiming to outsmart human opponents.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
MiniMax: The Game of Hex Andrew Spano
The Game: Hex Hex is a game played on a diamond or rhombus shaped board. Each player is assigned a color and must build a contiguous bridge with his or her pieces from one corresponding side of the board to the other.
The Challenge Write an AI program which uses a minimax algorithm that can beat a competent human player in the game.
Main Tasks 1) Create a Representation of the Board State 2) Create a User Interface for accepting input and displaying moves 3) Develop method for testing for win condition 4) Static Evaluation function using Djisktra s algorithm 5) Minimax
Representation of Board State The Board is represented as a list of lists--Each list is a distinct row; each position of the board represents the piece stored at that column
GUI representation User Interface run as server. Dotted Pair sent from interface to list
Testing for Win Condition Must perform Depth first search to determine whether a connected bridge exists
Minimax A minimax algorithm operates by building a decision tree of possible moves, and assigning a value to how likely each is to result in, or bring the player closer to, a winning state. The Computer player chooses branches of the tree that maximize its score and minimize the opponents score Alpha Beta Pruning reduces the number of branches that have to be evaluated by stopping a branch short if its value is guaranteed to be lower than a previously calculated branch
Djikstras Algorithm Find the shortest edge between nodes Test if the destination node can be reached from the shortest edge. If it can, repeat the process on its children If it can t, check the next shortest node
Work in Progess: My Implementation I am using Djikstra s algorithm as a static evaluation function. Each position on the board will be evaluated for the shortest possible path from that position to the player s corresponding endpoints. The length of each path will be counted and then negated
Sources Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, pp. 163 171, ISBN 0-13-790395-2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw Hill. pp. 595 601. ISBN 0-262-03293-7. https://towardsdatascience.com/hex-creating-intelligent-adversaries-part-2-heuristics-dijkstras-algorithm-597e4dcacf93 http://www.dcc.fc.up.pt/~fds/aulas/PPD/1314/project3.html Professor Doug Lea s Notes
