Teaching Kids Programming – Define Tic Tac Toe using Game Theory Terminologies

Teaching Kids Programming: Videos on Data Structures and Algorithms

We can store the state of a Tic-Tac-Toe Game using a 3×3 array. There are two players: agent (+1) and opponent (-1). If a slot is un-occupied, we mark it as zero. To check a Tic-Tac-Toe game to see if it is a end state, we need to check if the game has any consecutive slots of same player for rows/columns, or diagonals.

The actions are un-occupied slots and the succ marks a un-occupied slot and returns (next player, new state).

Below is a class to define the Tic Tac Toe Game.

class TicTacToeGame(object):
    def __init__(self):
        self.state = self.startState()
        
    def startState(self):
        return (+1, [[0 for _ in range(3)] for _ in range(3)])
        
    def utility(self, state):
        _player, s = state
        outcome = self.check(state)
        assert outcome != None
        return outcome * math.inf
    
    def player(self, state):
        _player, s = state
        return _player
        
    def check(self, state):
        _player, s = state
        for r in s:
            if r[0] == r[1] == r[2] and r[0] != 0:
                return r[0]
        for r in zip(*s):
            if r[0] == r[1] == r[2] and r[0] != 0:
                return r[0]
        if s[0][0] == s[1][1] == s[2][2] and s[0][0] != 0:
            return s[0][0]
        if s[0][2] == s[1][1] == s[2][0] and s[0][2] != 0:
            return s[0][0]
        if sum(sum(abs(x) for x in r) for r in s) == 9:
            return 0            
        return None
        
    def isEnd(self, state):
        outcome = self.check(state)
        return outcome != None
        
    def actions(self, state):
        _player, s = state
        ans = []
        for r in range(3):
            for c in range(3):
                if s[r][c] == 0:
                    ans.append((r, c))
        return ans
    
    def succ(self, state, action):
        _player, s = state
        s[action[0]][action[1]] = _player
        return -_player, deepcopy(s)

Game Theory – Game Algorithms

• Teaching Kids Programming – Alpha Beta Pruning Algorithm on NegaMax (Game Theory)
• Teaching Kids Programming – NegaMax Algorithm (Game Theory)
• Teaching Kids Programming – Alpha-Beta Pruning Algorithm (Game Theory)
• Teaching Kids Programming – Define Tic Tac Toe using Game Theory Terminologies
• Teaching Kids Programming – Introduction to Two Players Zero-Sum Game (Number Halving)
• Teaching Kids Programming – MinMax Algorithm in Game Tree (Game Theory, Tic Tac Toe)

–EOF (The Ultimate Computing & Technology Blog) —