Algorithms For Gaming
Different types of games
Number of players
Zero player - bingo, snakes and ladders
One - solitaire
Two - chess, tic-tac-toe
Many - poker
Unlimited - MMO
Information Availability
Complete Information (can see the state of the game)
Chess
Tic-tac-toe
Incomplete Information (info is hidden)
Auctions
Poker
Chance
Deterministic
Chess
Go
Stochastic
https://en.wikipedia.org/wiki/Stochastic
Backgammon
Poker
Turn-based or Concurrent
Turn-based
Concurrent
Typical types of games for AI:
Two player
Complete information
Deterministic
Turn Based
Examples:
Chess
Checkers
Tic-tac-toe
The Cat Trap (https://llerrah.com/cattrap.htm)
Decision Making Approaches
Tree-based decision making (Brute force)
Predict the outcome of all possible player moves
Choose the move that yields the best result
This algorithm produces only the next move
Time complexity
For Tic-Tac-Toe, the time complexity is 9! (Factorial), which is 9x8x7x6x5x4x3x2 = 362800 (Worst case)
Removing discounting duplicates, rotations and reflections is 26830
Minimax
https://docs.google.com/document/d/1s4qGALbK-hotAb6uU2N5L0pK6Y_pUGA0J-gYZwum4FQ/edit
Minimize the opponents maximum payoff
Minimize your own maximum loss
Tree-based algorithm, performing a depth-first search
Brute force
Max and min nodes
References
Courses
https://www.linkedin.com/learning/ai-algorithms-for-gaming
Videos
https://www.youtube.com/watch?v=U4ogK0MIzqk
https://www.youtube.com/channel/UCUbp3Qabq6iYQrN2QC-ZUXw/search?query=minimax
https://www.youtube.com/watch?v=zp3VMe0Jpf8
https://www.youtube.com/watch?v=STjW3eH0Cik
https://www.youtube.com/watch?v=UjQ1AzSvCp8&list=PLjTSKEJpqIeDrUYF7DKspT2r9H38vg5dC
https://www.youtube.com/watch?v=VrrnjYgDBEk
Books
https://www.amazon.com.au/Artificial-Intelligence-Stuart-Russell/dp/0136042597
Open Source Projects
https://github.com/topics/nine-mens-morris
https://github.com/MartinMSPedersen/Crafty-Chess
https://web.archive.org/web/20071026090003/http://www.brucemo.com/compchess/programming/index.htm
https://www.chessprogramming.org/Main_Page
https://github.com/SebLague/Chess-AI/blob/main/Assets/Scripts/Core/AI/Search.cs
https://sebastian.itch.io/chess-ai
https://stackoverflow.com/questions/29041413/understanding-the-minimax-algorithm
http://www.wisamyacteen.com/2012/11/an-artificial-intelligence-example-tic-tac-toe-using-c/
https://www.codeproject.com/Articles/43622/Solve-Tic-Tac-Toe-with-the-MiniMax-algorithm
Ninemen morris with Bluetooth
https://github.com/S7uXN37/NineMensMorrisBoard