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
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 | 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 |
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) —
loading...
Last Post: Teaching Kids Programming - Duplicate Numbers of Max Distance in Array (Sliding Window/Two Pointer Algorithms)
Next Post: Teaching Kids Programming - Define Tic Tac Toe using Game Theory Terminologies