Home
Teaching Kids Programming – Define Tic Tac Toe using Game Theory Terminologies
Tags:, , , , , ,

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

January 22, 2022 No Comments algorithms, Game Theory, games, python, teaching kids programming, WIFI, youtube video

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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)
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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
579 words
Last Post: Teaching Kids Programming - Introduction to Two Players Zero-Sum Game (Number Halving)
Next Post: Teaching Kids Programming - MinMax Algorithm in Game Tree (Game Theory, Tic Tac Toe)

The Permanent URL is: Teaching Kids Programming – Define Tic Tac Toe using Game Theory Terminologies

Related posts:

  1. Teaching Kids Programming – Duplicate Numbers of Max Distance in Array (Sliding Window/Two Pointer Algorithms) Teaching Kids Programming: Videos on Data Structures and Algorithms Given an integer array nums and...
  2. Teaching Kids Programming – Introduction to Two Players Zero-Sum Game (Number Halving) Teaching Kids Programming: Videos on Data Structures and Algorithms Two Players Zero-Sum Game: Two Players...
  3. Teaching Kids Programming – MinMax Algorithm in Game Tree (Game Theory, Tic Tac Toe) Teaching Kids Programming: Videos on Data Structures and Algorithms The total number of possible game...
  4. Teaching Kids Programming – Alpha-Beta Pruning Algorithm (Game Theory) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the following Two MinMax Game...
  5. Teaching Kids Programming – NegaMax Algorithm (Game Theory) Teaching Kids Programming: Videos on Data Structures and Algorithms Given a MinMax implementation, one problem...
  6. Teaching Kids Programming – A Light Talk on Breadth First Search, Uniform Cost Search and Dijkstra Shortest Path Graph Algorithms Teaching Kids Programming: Videos on Data Structures and Algorithms Breadth First Search Algorithm (BFS) performs...
  7. The Facebook Initial Coding Interview Experience Update: I have been careful enough not to leak any confidential information after signing the...
  8. Teaching Kids Programming – Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a list of...

Leave a Reply