Project Resources

Tools Used

Starter code from GitHub: https://github.com/brettpilch/pygame-checkers
Our GitHub repository: https://github.com/LaZY-Discrete-Team/Discrete-Final-Project
Python & Pygame library for code implementation
Trinket.io and Repl.it for gameplay in browser
Online research to learn about the topic, see annotated bibliography

Annotated Bibliography

Math of checkers, MiniMax, and more:

Schaeffer, Jonathan, and Robert Lake. “Solving the Game of Checkers.” Games of No Chance , MSRI Publications Volume 29, 1996, library.msri.org/books/Book29/files/schaeffer.pdf.

This is a research paper written by two Computer Science Professors from the University of Alberta. We used it to learn about game complexity and how to compute the space complexity of checkers.

Moti, Moin Hussain. “Ultimate Tic-Tac-Toe.” Moin H Moti, 17 Mar. 2019, moinmoti.com/project/ultimate_tictactoe/.

We used this illustration created by Student Researcher Moin Hussain Moti to demonstrate alpha-beta pruning.

Eppes, Marissa. “How a Computerized Chess Opponent ‘Thinks’ - The Minimax Algorithm.” Medium, Towards Data Science, 6 Oct. 2019, towardsdatascience.com/how-a-chess-playing-computer-thinks-about-its-next-move-8f028bd0e7b1.

From this Towards Data Science article, we learned about implementing depth-limited MiniMax and found a suitable graphic to aid our explanation of depth limits.

Code resources:

Pilch, Brett. "Pygame-checkers." 9 May 2015, https://github.com/brettpilch/pygame-checkers.

The code for our checkers game was adapted from this two-player Python 2 pygame project we found on Github. It simply uses pygame to create an interface that blocks illegal moves and enables players to move pieces around a chessboard.

Video resources:

Tech With Tim. "Python Checkers AI Tutorial Part 2 - Implementation & Visualization (Minimax)." 9 Sep. 2020, https://www.youtube.com/watch?v=mYbrH1Cl3nw.

We referred to this video while implementing our MiniMax algorithm, specifically to visualize the algorithm and understand how it is affected by the depth limit.

Lague, Sebastian. "Algorithms Explained – minimax and alpha-beta pruning." 20 Apr. 2018, https://www.youtube.com/watch?v=l-hh51ncgDI.

Information from this video informed our decision making on the implementation of the alpha-beta pruning component of the MiniMax algorithm. The visualizations were very helpful to understanding the way in which alpha-beta pruning works.