kotlin-uttt.kt

package main

// Main calls Bitboard.moveGen(Bitboard(), depth = 7)

class Bitboard(var validField: Int = ALL_FIELDS, var board: Array<IntArray> = arrayOf(IntArray(9), IntArray(9)), var turn: Int = 0) {

    private var cachedMetaField: IntArray = intArrayOf(-1, -1)
    private var cachedGameOver: Boolean = false
    private var cachedMetaFieldDirty = true
    private var cachedGameOverDirty = true

    fun dirty(){
        cachedMetaFieldDirty = true
        cachedGameOverDirty = true
    }

    fun taken(pos: Int): Boolean {
        return (board[0][toIndex(field(pos))] or board[1][toIndex(field(pos))]) and square(pos) != 0
    }

    fun makeMove(move: Int){
        val field = field(move)
        val square = square(move)
        board[turn][toIndex(field)] = board[turn][toIndex(field)] or square

        if(fieldIsBlocked(toIndex(square)) || isWon(field)){
            validField = ALL_FIELDS
        } else {
            validField = square
        }
        turn = 1 - turn
        dirty()
    }

    fun getAllMoves(): List<Int> {
        val list = mutableListOf<Int>()

        for(i in 0..8){
            if(((1 shl i) and validField) != 0){
                for(s in 0..8){
                    val move = (1 shl s) or ((1 shl i) shl 16)
                    if(!taken(move) && !fieldIsBlocked(i)){
                        list.add(move or (if(validField == ALL_FIELDS) ALL_FIELDS_LEGAL else 0))
                    }
                }
            }
        }

        return list
    }

    fun undoMove(move: Int){
        val field = field(move)
        val square = square(move)
        board[1 - turn][toIndex(field)] = board[1 - turn][toIndex(field)] and square.inv()
        if((move and ALL_FIELDS_LEGAL) != 0){
            validField = ALL_FIELDS
        } else {
            validField = field
        }
        turn = 1 - turn
        dirty()
    }

    fun fieldIsBlocked(field: Int): Boolean {
        val whiteField = board[WHITE][field]
        val blackField = board[BLACK][field]
        return isWon(whiteField) || isWon(blackField) || isTied(whiteField or blackField)
    }

    fun isGameOver(): Boolean {
        if(!cachedGameOverDirty)
            return cachedGameOver

        val sum = board[0].map { popcnt(it) }.sum()
        if(sum < 9) return false

        val metaField = getMetaField()
        val ret = isWon(metaField[WHITE]) || isWon(metaField[BLACK]) || isGameTied()
        cachedGameOver = ret
        cachedGameOverDirty = false
        return ret
    }

    fun getMetaField(): IntArray {
        if(!cachedMetaFieldDirty)
            return cachedMetaField

        val field = IntArray(2)
        for (p in 0..1){
            field[p] = ((isWon(board[p][0])).toInt() shl 8) or ((isWon(board[p][1]))
                .toInt() shl 7) or ((isWon(board[p][2]))
                .toInt() shl 6) or ((isWon(board[p][3]))
                .toInt() shl 5) or ((isWon(board[p][4]))
                .toInt() shl 4) or ((isWon(board[p][5]))
                .toInt() shl 3) or ((isWon(board[p][6]))
                .toInt() shl 2) or ((isWon(board[p][7]))
                .toInt() shl 1) or ((isWon(board[p][8]))
                .toInt() shl 0)
        }

        cachedMetaField = field
        cachedMetaFieldDirty = false
        return field
    }

    companion object {

        val WHITE = 0
        val BLACK = 1

        val FIELD = 0x1FF shl 16
        val SQUARE = 0xFFFF
        val ALL_FIELDS_LEGAL = 1 shl 25

        /**
         * 0o777
         */
        val ALL_FIELDS = oct(777)

        val DIAGS = intArrayOf(oct(421), oct(124))
        val ROWS = intArrayOf(oct(700), oct(70), oct(7))
        val COLS = intArrayOf(oct(111), oct(222), oct(444))
        val O_O = oct(50)

        fun moveGen(board: Bitboard, depth: Int): Long {
            if(board.isGameOver()) return 0
            val moves = board.getAllMoves()
            return moves.size + if(depth > 0){
                moves.map {
                    board.makeMove(it)
                    val ret = moveGen(board, depth - 1)
                    board.undoMove(it)
                    ret
                }.sum()
            } else { 0 }
        }

        fun field(i: Int) = (i and FIELD) shr 16
        fun square(i: Int) = (i and SQUARE)

        /**
         * Basically fast log2 for powers of two
         */
        fun toIndex(i: Int) = 31 - Integer.numberOfLeadingZeros(i)

        fun isWon(field: Int) =
            (field and DIAGS[0]) == DIAGS[0]
                    || (field and DIAGS[1]) == DIAGS[1]
                    || (field and  ROWS[0]) ==  ROWS[0]
                    || (field and  ROWS[1]) ==  ROWS[1]
                    || (field and  ROWS[2]) ==  ROWS[2]
                    || (field and  COLS[0]) ==  COLS[0]
                    || (field and  COLS[1]) ==  COLS[1]
                    || (field and  COLS[2]) ==  COLS[2]

        fun isTied(field: Int) = field == ALL_FIELDS
    }
}