PROJECT TITLE :

Bitwise-Parallel Reduction for Connection Tests

ABSTRACT:

This paper introduces bitwise-parallel reduction (BPR), an economical technique for performing affiliation tests in hexagonal connection games like Hex and Y. BPR relies on a known property of Y that games will be reduced to one value indicating the fully connected player (if any) through a sequence of reduction operations. We adapt this process for bitwise-parallel implementation and demonstrate its profit over a range of board sizes. BPR is by far the fastest known technique if affiliation tests solely need to be performed once per game, for instance, to judge board fills following Monte Carlo playouts.