Representing Tic-tac-toe in ternary form, and efficiently generating all possible boards. - yduf

Rather than doing binary to ternary number conversion (implying divide and mod by 3), we can directly count in binary-coded ternary form.

Ternary Increment

My own code to increment from 1 to N in binary-coded ternary representation. Trick is to use the binary + for handling carry over, by first allowing propagation when it will be needed and then masking spurious bits.

TODO: would it allow general addition operation (ternary) + binary operand ?

#include <cstdint>

#include <iostream>
#include <bitset>

int main() {
    uint16_t b = 0;

    for( int i = 0; i < 10; ++i) {
        std::cout << std::bitset<16>( b) 
                  << " = " << i 
                  << std::endl;

        // ternary increment
        auto comb = b & 0b10101010'10101010;
        auto mask = comb >> 1;
        auto inc = ( ( b | mask) +1 ) & ~mask;
        b = inc;
  
        // ternary decrement
        auto int3 = b;
        --int3;
        comb = int3 & 0b10101010'10101010;
        mask = comb >> 1;
        int3 = int3 & ~mask;
  		
        // int3 == b before increment 
    }
}

Notes: it still requires 2*9=18bits to represent Tic-tac-toe state in Binary-Coded Ternary (contrary to the sample code above which use 16bits integer).

Resources

• Binary Coded Ternary and Its Inverse
• Ternary numeral system
• Binary-coded decimal
• How can 3-state bit packed together?
• Power of three
• Bitboard to titboard (ternary bitboard) conversion
• Titboards