Minimax
Win
Lose
Draw
s0 - Initial State
player(s)
actions(s)
result(s,a)
terminal(s)
utility(s,p)
Terminal is when it ends
-1 = Means loss
0 = Draw
1 = Win
Turns
MAX
MIN
MAX
MIN
MAX
MIN
minimax(s)
= if (terminal(s)) return utility (2)
= if (player(s)) = MAX return max(all actions) minimax(result(s,a))
= if (players(s)) = MIN return min(all actions) minimax(result(s,a))
MAX is trying to maximize the score (utility) of the game
MIN is trying to minimize the score (utility) of the game for MAX
Alpha = best alternative for MAX
Beta = best alternative for MIN
Nine men’s morris
The game dates back to Roman times, and is mentioned in Ovid.
References
Videos
https://www.youtube.com/watch?v=KU9Ch59-4vw
Sebastian Lague
https://www.youtube.com/watch?v=l-hh51ncgDI&list=PLFt_AvWsXl0f4J6yVWFAFb8jjdeX0gdXZ
Minimax with Alpha Beta Pruning
https://www.youtube.com/watch?v=zp3VMe0Jpf8
https://www.youtube.com/watch?v=zp3VMe0Jpf8
https://www.youtube.com/watch?v=6ELUvkSkCts
https://www.youtube.com/watch?v=STjW3eH0Cik
https://www.youtube.com/watch?v=KU9Ch59-4vw
https://www.youtube.com/watch?v=fT3YWCKvuQE
https://www.youtube.com/watch?v=J1GoI5WHBto
Articles
https://en.wikipedia.org/wiki/Minimax
https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13
https://stackoverflow.com/questions/29041413/understanding-the-minimax-algorithm
https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/
Long Version
https://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html
https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
http://www.wisamyacteen.com/2012/11/an-artificial-intelligence-example-tic-tac-toe-using-c/
https://www.yosenspace.com/posts/computer-science-game-trees.html
https://www3.ntu.edu.sg/home/ehchua/programming/java/javagame_tictactoe_ai.html
https://en.wikipedia.org/wiki/Negamax
https://en.wikipedia.org/wiki/Minimax
http://www.dasconference.ro/papers/2008/B7.pdf
https://jitpaul.blog/2017/07/18/ai-in-nine-men-s-morris-game/
Open source Projects
Short version
https://www.codeproject.com/Articles/43622/Solve-Tic-Tac-Toe-with-the-MiniMax-algorithm
https://github.com/calcitem/Sanmill
https://github.com/trenki2/NineMensMorris
https://unitylist.com/p/12m0/Minimax-AI
https://github.com/trenki2/NineMensMorris
https://github.com/topics/nine-mens-morris
https://github.com/GUSAR1T0/TwelveMensMorris
https://github.com/JakobDomislovic/Nine_Mens_Morris_with_Franka_ROS
https://github.com/S7uXN37/NineMensMorrisBoard
https://github.com/edersasch/boardgames
https://github.com/paul-maxime/merreles
https://github.com/SebLague/Chess-AI/blob/main/Assets/Scripts/Core/AI/Search.cs
https://unitylist.com/p/n25/AI-for-tictactoe
https://unitylist.com/browse?search=minimax