Formal Verification of Multi-Thread Minimax Behavior Using mCRL2 in the Connect 4

This study focuses on the formal verification of a parallel version of the minimax algorithm using the mCRL2 modeling language, applied to the game of Connect 4. The research aims to ensure that the algorithm behaves correctly in concurrent execution environments by providing a formal model and conducting rigorous verification. The parallel version of minimax distributes computations across multiple threads, with each thread evaluating different successor states concurrently. Using mCRL2, we specify the algorithm’s behavior, generate Labeled Transition Systems (LTSs), and verify critical properties such as the absence of deadlocks, liveness, and correctness of state transitions. The formal verification process demonstrates that the proposed model accurately represents the parallel minimax algorithm and ensures its reliability by verifying properties that guarantee unique and non-redundant actions throughout the execution. The findings highlight the value of formal methods in validating the correctness of parallel artificial intelligence algorithms, laying the foundation for future optimizations that focus on performance.