Recursive Gaming

We present a general-purpose recursive scheme for turn-based games built on the Mina blockchain. A demo implementation of the game tic-tac-toe is implemented using this scheme to showcase its application, which can be extended to games like checkers, chess, battleships... This is additionally the first o1js application using lookup tables.

Each move of the turn based game is represented as a proof. Each player first verifies that the move from the opponent was valid by verifying their proof, and then makes their own move. This two steps are then proven together, and the resulting proof is sent to the opponent. The scheme runs back and forth until a final state is reached (a player wins, a draw is reached...) At the end of the game, this recursive scheme allows the final proof to encode all of the turns that were played. We verify this final proof onchain, setting the winner for the game.

The included demo implementation for tictactoe uses lookup tables to verify that the final state of the board, either a win or a draw position, is part of a precommitted table with all possible win and draw states of the board. This is the first use of lookup tables on o1js, which are not natively supported yet, but were exposed via this PR: https://github.com/o1-labs/o1js/pull/1253