I've attempted and failed to implement a computer player based on the minimax algorithm. I was right when I thought recursion + dynamically-allocating memory in the stack would be a terrible idea for an AVR microcontroller. I am just going to work on implementing the minimax algorithm on a Python script (running on a host PC with more RAM and computing power than an ATtiny, of course), with the host PC retrieving the game state and inputting its moves through the FT230X/USB serial port.

I will start by implementing a serial port interface to allow data (game state, move inputs, etc.) to be exchanged through the micro USB port.