<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Tic-Tac-Toe via Bitboards
This notebook defines the game tic-tac-toe.
It is played on a $3 \times 3$ board.  There are two players, which are called X and O.  Player X starts.  Player X always puts an 'X' into an empty field on the board, while player O always puts an 'O' in an empty field of the board.  The goal of the game for player X is to get three Xs into a row, column, or diagonal line, while player O needs to get three Os into a row, column, or diagonal line.
In this notebook, the board is represented as a bitboard, i.e. every state is represented as an integer.  If s is a state, the first nine bits of s specify the positions of the Xes, while the second nine bits specify the positions of the Os.  Player X is encoded as the number 0,  while player O is encoded as the number 1.
The global variable gPlayers stores the list of players.
Step1:  States are represented as integers.  The first 9 bits encode the marks of the player X, the next 9 bits encode the marks of the player O.  Initially, the board is empty and hence no bit is set.
The variable gStart represents the start state.
Step2:  The function set_bits takes one parameter
Step3:  The function set_bit(n) returns a number that has exactly the $\texttt{n}^\textrm{th}$ bit set.
Step4:  The function to_board(state) takes an integer state as its argument that represents a state of the game Tic-Tac-Toe.  It converts this state into a string that represents the board corresponding to the state.
Step5:  Given a state that is represented as a number, the function empty(state) returns the set of indexes of those cells such that neither player X nor player O has placed a mark in the cell.  Note that there are 9 cells on the board.  Each of these cells can hold either an 'X' or an 'O'.  If the $i^\textrm{th}$ cell is marked with a 'X', then the $i^\textrm{th}$ bit of state is set.  If instead the $i^\textrm{th}$ cell is marked with an 'O', then the $(9+i)^\textrm{th}$ bit of state is set.  If the $i^\textrm{th}$ cell is not yet marked, then both the $i^\textrm{th}$ bit and the $(9+i)^\textrm{th}$ are $0$.
Step6:  Given a state and the player who is next to move, the function next_states(state, player) computes the set of states that can be reached from state.
Note that player X is encoded as the number $0$, while player O is encoded as the number $1$.
Step7:  The global variable gAllLines is a list of eight bit masks.  These masks can be used to test whether there are three identical marks in a row, column, or diagonal.
Step8:  The function utility takes one argument
Step9:  finished(state) is True if the game is over.
Step10:  The function get_move asks the user to input a move in the format r,c where r is the row and the c is the column where the next symbol is to be placed.
Step11:  The function final_msg(state) informs the user about the result of the game once the game is finished.
Step12:  Drawing the Board
Step13:  This function creates the canvas for the start state.  It draws an empty board which is later used for the game.
Step14:  The function get_symbol(state, row, col) takes three arguments
Step15:  This function takes three arguments
<ASSISTANT_TASK:>
Python Code:
gPlayers = [0, 1]
Explanation: Tic-Tac-Toe via Bitboards
This notebook defines the game tic-tac-toe.
It is played on a $3 \times 3$ board.  There are two players, which are called X and O.  Player X starts.  Player X always puts an 'X' into an empty field on the board, while player O always puts an 'O' in an empty field of the board.  The goal of the game for player X is to get three Xs into a row, column, or diagonal line, while player O needs to get three Os into a row, column, or diagonal line.
In this notebook, the board is represented as a bitboard, i.e. every state is represented as an integer.  If s is a state, the first nine bits of s specify the positions of the Xes, while the second nine bits specify the positions of the Os.  Player X is encoded as the number 0,  while player O is encoded as the number 1.
The global variable gPlayers stores the list of players.
End of explanation
gStart = 0
Explanation: States are represented as integers.  The first 9 bits encode the marks of the player X, the next 9 bits encode the marks of the player O.  Initially, the board is empty and hence no bit is set.
The variable gStart represents the start state.
End of explanation
def set_bits(Bits):
    result = 0
    for b in Bits:
        result |= 1 << b # bitwise or 2**b
    return result
"{:b}".format(set_bits([0, 1, 4]))
assert set_bits([0, 1, 4]) == 2**0 + 2**1 + 2**4
Explanation: The function set_bits takes one parameter:
* Bits is a list of numbers that specify bit positions in an integer.
The function returns an integer such that the bits specified in Bits are set. Counting starts with $0$.
End of explanation
def set_bit(n): 
    return 1 << n
assert set_bit(7) == 2 ** 7
Explanation: The function set_bit(n) returns a number that has exactly the $\texttt{n}^\textrm{th}$ bit set.
End of explanation
def to_board(state):
    result = '+-+-+-+\n'
    for cell in range(9):
        if state & (2 ** cell) != 0:
            result += '|X'
        elif state & (2 ** (cell + 9)) != 0:
            result += '|O'
        else:
            result += '| '
        if (cell + 1) % 3 == 0:
            result += '|\n+-+-+-+\n'
    return result
print(to_board(set_bits([0,2,3,5,7,9+1,9+4,9+6])))
Explanation: The function to_board(state) takes an integer state as its argument that represents a state of the game Tic-Tac-Toe.  It converts this state into a string that represents the board corresponding to the state.
End of explanation
def empty(state):
    Free  = { n for n in range(9) }
    Free -= { n for n in range(9) if state & (1 << n) != 0 }
    Free -= { n for n in range(9) if state & (1 << (9 + n)) != 0 }
    return Free
state = set_bits([2, 3, 5, 9+1, 9+4, 9+8])
print(to_board(state))
empty(state)
Explanation: Given a state that is represented as a number, the function empty(state) returns the set of indexes of those cells such that neither player X nor player O has placed a mark in the cell.  Note that there are 9 cells on the board.  Each of these cells can hold either an 'X' or an 'O'.  If the $i^\textrm{th}$ cell is marked with a 'X', then the $i^\textrm{th}$ bit of state is set.  If instead the $i^\textrm{th}$ cell is marked with an 'O', then the $(9+i)^\textrm{th}$ bit of state is set.  If the $i^\textrm{th}$ cell is not yet marked, then both the $i^\textrm{th}$ bit and the $(9+i)^\textrm{th}$ are $0$.
End of explanation
def next_states(state, player):
    Empty  = empty(state)
    Result = []
    for n in Empty:
        next_state = state | set_bit(player * 9 + n)
        Result.append(next_state)
    return Result
state = set_bits([2,3,5,10,13,15])
print(f'state:\n{to_board(state)}')
print('next states:')                  
for s in next_states(state, 0):
    print(to_board(s))
Explanation: Given a state and the player who is next to move, the function next_states(state, player) computes the set of states that can be reached from state.
Note that player X is encoded as the number $0$, while player O is encoded as the number $1$.
End of explanation
gAllLines = [ set_bits([0,1,2]), # 1st row
              set_bits([3,4,5]), # 2nd row
              set_bits([6,7,8]), # 3rd row
              set_bits([0,3,6]), # 1st column
              set_bits([1,4,7]), # 2nd column
              set_bits([2,5,8]), # 3rd column
              set_bits([0,4,8]), # falling diagonal
              set_bits([2,4,6]), # rising diagonal
            ]
for state in gAllLines:
    print(to_board(state))
Explanation: The global variable gAllLines is a list of eight bit masks.  These masks can be used to test whether there are three identical marks in a row, column, or diagonal.
End of explanation
def utility(state):
    for mask in gAllLines:
        if state & mask == mask:
            return 1               # the computer has won
        if (state >> 9) & mask == mask:
            return -1              # the computer has lost
    # 511 == 2**9 - 1 = 0b1_1111_1111  
    if (state & 511) | (state >> 9) != 511: # the board is not yet filled
        return None
    # at this point, the board has been filled, but there is no winner hence its a draw
    return 0 # it's a draw
s1 = set_bits([0, 2, 3, 6, 1+9,  4+9, 5+9]) # 'X' has won
print(to_board(s1))
utility(s1)
s2 = set_bits([0, 2, 6, 8, 1+9, 4+9, 7+9]) # 'O' has won
print(to_board(s2))
utility(s2)
s3 = set_bits([0, 2, 5, 6, 7, 1+9, 3+9, 4+9, 8+9]) # it's a draw
print(to_board(s3))
print(utility(s3))
s4 = set_bits([0, 2, 5, 6, 1+9, 3+9, 4+9]) # it ain't over yet
print(to_board(s4))
print(utility(s4))
Explanation: The function utility takes one argument:
- state  is an integer representing the board.
The function returns 1 if the computer has won the game, -1 if the game is lost for 
the computer, 0 if it's a draw, and None if the game has not yet been decided.
End of explanation
def finished(state): 
    return utility(state) != None
s = set_bits([0, 2, 5, 6, 7, 1+9, 3+9, 4+9, 8+9])
print(to_board(s))
finished(s)
Explanation: finished(state) is True if the game is over.
End of explanation
def get_move(state):
    while True:
        try:
            row, col = input('Enter move here: ').split(',')
            row, col = int(row), int(col)
            if row not in {0, 1, 2} or col not in {0, 1, 2}:
                print('Illegal input. The move has to be a pair of  the form "row,col"')  
                print('where row and col are numbers from the set {0,1,2}.')
                continue
            mask = set_bit(row * 3 + col)
            if state & (mask | (mask << 9)) == 0:
                return state | (mask << 9)
            print("Don't cheat! Please try again.")
        except:
            print('Illegal input.')  
            print('row and col are numbers from the set {0,1,2}.')
Explanation: The function get_move asks the user to input a move in the format r,c where r is the row and the c is the column where the next symbol is to be placed.
End of explanation
def final_msg(state):
    if finished(state):
        if utility(state) == -1:
            print('You have won!')
        elif utility(state) == 1:
            print('The computer has won!')
        else:
            print("It's a draw.");
        return True
    return False
Explanation: The function final_msg(state) informs the user about the result of the game once the game is finished.
End of explanation
import ipycanvas as cnv
size = 150
Explanation: Drawing the Board
End of explanation
def create_canvas():
    canvas = cnv.Canvas(size=(size * 3, size * 3 + 50))
    display(canvas)
    return canvas
Explanation: This function creates the canvas for the start state.  It draws an empty board which is later used for the game.
End of explanation
def get_symbol(state, row, col):
    mask = set_bit(row * 3 + col)
    if mask & state == mask:
        return 'X'
    if mask & (state >> 9) == mask:
        return 'O'
    return ' '  
Explanation: The function get_symbol(state, row, col) takes three arguments:
* state is an integer representing a tic-tac-toe board.
* row is an integer in range(3) that specifies a row in the board.
* col is an integer in range(3) that specifies a column in the board.
The function returns the mark that is placed in the given row and column.  If this position is empty, a blank ' ' is returned.
End of explanation
def draw(state, canvas, value):
    canvas.clear()
    n = 3
    canvas.font          = '90px sans-serif'
    canvas.text_align    = 'center'
    canvas.text_baseline = 'middle'
    for row in range(n):
        for col in range(n):
            x = col * size
            y = row * size
            canvas.line_width = 3.0
            canvas.stroke_rect(x, y, size, size)
            symbol = get_symbol(state, row, col)
            if symbol != ' ':
                x += size // 2
                y += size // 2
                if symbol == 'X':
                    canvas.fill_style ='red'
                else:
                    canvas.fill_style ='blue'
                canvas.fill_text(symbol, x, y)
    canvas.font = '12px sans-serif'
    canvas.fill_style = 'green'
    for row in range(n):
        for col in range(n):
            x = col * size + 16
            y = row * size + 141
            canvas.fill_text(f'({row}, {col})', x, y)
    canvas.font = '20px sans-serif'
    canvas.fill_style = 'black'
    x = 1.5 * size
    y = 3.2 * size
    canvas.fill_text(str(value), x, y)
draw(set_bits([0, 2, 5, 6, 1+9, 3+9, 4+9]), create_canvas(), -1)
Explanation: This function takes three arguments:
- state is the current state of the game.
- canvas is a canvas used to draw the state.
- value is the value of the game for player X.
The function draws the given State onto canvas.  Below that, the value is printed.
End of explanation
<END_TASK>