This file implements a TicTacToe AI that iteratively adapts its gaming strategy based on previous run data. It's designed to run with roughly logarthmic time during the game itself while sacrificing in terms of polynomial setup time and space consumption. This code was originally written seeking a more organic approach to game AI than the traditional graph algorithm or minimax methods, which rely largely on brute force and computing power to calculate the best possible move. Although the performance in many fields falls short in practice to the specialized TicTacToe algorithms, while maintaing simplicity it manages to demonstrate a fairly high potential for dynamic learning.
The rough algorithm works as follows. First, the previous run data (by default, stored in two binary files, moves.txt and boards.txt) is loaded, and the data is sorted in-place for easy access during the playthrough. Then, during the computer's turn in the actual playthrough, it searches for any previous runs that mimic the current flow of the game. It then parses through the previous history of moves that were made and either chooses to continue following that pattern (if it predicts a victory) or to devise its own movement pattern (if it predicts a tie or loss). Although multiple algorithms for this new movement selection were tested, selecting squares according to a set of pre-calculated weights (with some minor changes to follow the game rules) ended up as the fastest algorithm that still maintained a relatively high win rate.
To analyze the time and space complexity of the algorithm, let d be the size of the board (so there are d^2 squares on a board of size d) and m be the number of previous runs (assuming m >> d^2). Loading the data takes O(md^2) time and O(md^2) space, and sorting the data in-place afterwards takes O(mlog(m)) time and O(1) space. Each subsequent move takes O(log(m)) time for the binary search and O(1) space. Saving the data afterwards takes O(d^2) time and O(d^2) additional space to write the new test run at the back of the play file. Thus, it can clearly be seen that much of the time and space consumption is consumed to set up the game, but the algorithm is logarithmic during the playthrough (in addition, selecting the option to play a new round after winning or losing instead of just ending the session allows you to save your previously sorted list of runs, which leads to amortized O(log(m)) time and O(md^2) space consumption).