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 take turn to play. Their objectives are opposite. One wins and the other has to lose. We call these two players: (agent, opponent). If agent wins $10, opponent has to lose $10.

The game is transparent so that two players know exactly the same information. Poke-cards playing is not a two player zero-sum game as you might not know the opponent’s cards in his/her hand.

Some Two Players Zero-Sum Game: Tic-tac-toe, Chess.

Number Halving Game

Given a start Number N, each player takes turn to either reduce it by one or divide it by two (if it is odd, the result is the flooring for example, 5//2=2). The player wins if it gets to zero. For example:

Number = 50
Agent = 25
Opponent = 12
Agent = 6
Oppenent = 5
Agent = 2
Opponent = 1
Agent = 0 (Wins)

Two Players Zero-Sum Game Terminologies

State: the status of a game including the player’s turn and game information such as pieces positions on a chess board, or current number in above Number Halving Game.

IsEnd(s): return if the game is ended – could be a draw in Tic-Tac-Toe or one wins

Action: next actions that a player could play, for example on a Tic-Tac-Toe, the actions could be empty slots not occupied. For number halving game, it could be either “/” or “-”

Succ(state, action): Taking a state and action, it should return the next state.

Utility(state): the “score” for a end-state. If it is a draw, it returns 0. If agent wins, return math.inf otherwise returns -math.inf

Python Class to Define a Number Halving Game

class NumberHalvingGame(object):
    def __init__(self, N):
        self.N = N

    def startState(self):
        return (+1, self.N)

    def isEnd(self, state):
        player, num = state
        return num == 0

    def action(self, state):
        return ('/', '-')

    def utility(self, state):
        player, num = state
        assert num == 0
        return player * math.inf

    def succ(self, state, action):
        player, num = state
        if action == '-':
            return (-player, num - 1)
        elif action == '/':
            return (-player, num // 2)

    def player(self, state):
        _player, num = state
        return _player

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