AlgoNim is a cryptographic version of Nim – a very simple mathematical game of strategy for two players – that runs directly on Algorand’s Pure Proof-of-Stake (PPoS) consensus protocol at Layer-1. AlgoNim is played from the command-line and players can choose to bet ALGOs for each match.

AlgoNim is the first game built on Algorand Layer-1, incorporating all the Algorand 2.0 features: Algorand Standard Assets (ASA), Atomic Transfers (AT) and Algorand Smart Contracts (ASC1).

This solution explains how AlgoNim was implemented with Algorand’s core Layer-1 feature set. It explains the benefits of such an implementation from a security perspective, in this case, to prevent cheating, and from a performance perspective, where the cost and time efficency gains are significant relative to other blockchains.

AlgoNim: let’s play a crypto-Nim on Algorand from the CLI

What is Nim?

Nim is a very simple mathematical game of strategy for two players. Throughout this solution, we will refer to our hypothetical two players as Alice and Bob.

What is AlgoNim?

AlgoNim is a cryptographic version of Nim that runs on Algorand Layer-1, directly on the Pure Proof of Stake consensus protocol, so nobody can cheat. The game implementation takes advantage of all the features introduced in the Algorand 2.0 protocol: Algorand Standard Assets (ASA), Atomic Transfers (AT) and Algorand Smart Contracts (ASC1) using Algorand Python SDK + PyTeal. PyTeal is a binding for TEAL, the stack-based language for ASC1.

Through seamless interaction between the Algorand Python SDK and PyTeal, AlgoNim automatically writes and initializes a dedicated set of stateless TEAL ASC1s and ASAs for each match. The whole match set-up takes a few seconds and costs about 0.008 ALGOS in transaction fees. AlgoNim accounts require a minimum balance for initialization and opt-in, so the Dealer needs 0.8 ALGO that can be refunded by slightly enhancing the TEAL ASC1s making them more cost-efficient. Considering that a new ASA + ASC1 architecture is generated for each match, this time/cost performance is quite impressive compared to other blockchains.

AlgoNim is played entirely from the command-line interface. Find other AlgoNim players: https://t.me/algonim

AlgoNim rules

AlgoNim is based on Nim’s “normal single heap” variant. Alice is the player who creates the match; she is the Dealer and sets up the game table. Bob is the Opponent.

Rules of the Game:
1. The Dealer chooses a heap of N pieces to be placed on the game table for the match.
2. The Dealer chooses the number M of pieces that can be removed, at most, from the game table on each turn.
3. Players agree on who moves first.
4. On each turn each player removes at least 1 and at most M pieces from the game table;

Whoever removes the last piece of the heap from the table wins the match!

Alice and Bob may choose to bet some ALGOs for the match. Future implementations will accept AlgoNim ASA Score Points instead as the betting reward for the matches. This will enable an AlgoNim global ranking too!

      _       __                 ____  _____   _               
     / \     [  |               |_   \|_   _| (_)              
    / _ \     | |  .--./)  .--.   |   \ | |   __   _ .--..--.  
   / ___ \    | | / /'`\;/ .'`\ \ | |\ \| |  [  | [ `.-. .-. | 
 _/ /   \ \_  | | \ \._//| \__. |_| |_\   |_  | |  | | | | | | 
|____| |____|[___].',__`  '.__.'|_____|\____|[___][___||__||__]
                 ( ( __))                                      
                                                       by cusma

Install AlgoNim

Step 1 - Python modules

AlgoNim uses the following Python3 modules:
1. msgpack
2. docopt
3. algosdk
4. pyteal

To install:

$ pip3 install --upgrade msgpack
$ pip3 install --upgrade docopt
$ pip3 install --upgrade algosdk
$ pip3 install --upgrade pyteal

Step 2 - Environment Settings

To run AlgoNim, you need to set the following environment variables:

$ export ALGORAND_DATA=/path/to/node/data
$ export PATH=/path/to/node/:$PATH

Step 3 - AlgoNim files

Copy the following AlgoNim files into your node’s root directory:

1. algonim.py
2. algonim_asa.py
3. algonim_asc1.py
4. algonim_moves.py
5. algonim_lib.py

How to play

Playing AlgoNim from your CLI is simple, just ask for help:

Input

$ python3 algonim.py --help

Output

AlgoNim, the first crypto-mini-game on Algorand! (by cusma)
Usage:
  algonim.py setup <dealer_mnemonic> <opponent_address> <hours_duration>
                   [--bet-amount=<ba>] [--pieces=<ps>] [--max-removal=<mr>]
  algonim.py join <opponent_mnemonic>
  algonim.py play <player_mnemonic> <asa_pieces_amount>
  algonim.py status <player_address>
  algonim.py close <player_address>
  algonim.py [--help]

Commands:
  setup    Dealer sets up a new AlgoNim match.
  join     Opponent joins the match.
  play     Play your turn.
  status   Display current match status.
  close    Close expired AlgoNim Bet Escrows.

Options:
  -b <ba> --bet-amount=<ba>     Set the bet amount in microAlgos
                                [default: 0].
  -p <ps> --pieces=<ps>         Set the total amount of pieces on game table
                                [default: 21].
  -m <mr> --max-removal=<mr>    Set maximum amount of pieces removal
                                [default: 4].
  -h --help

Step 1 - Match set up (Dealer)

In the first step the Dealer sets up the match, generating the ASAs + ASC1s game architecture. To set up the match, the Dealer may choose the following options (or leave them empty for default values):
1. [--bet-amount=<ba>] is the bet proposal expressed in microALGOs;
2. [--pieces=<ps>] is the number of pieces that the Dealer distributes onto the Game Table;
3. [--max-removal=<mr>] is the maximum number of pieces that can be removed from the Game Table on each turn by the players;

Input

$ python3 algonim.py setup <dealer_mnemonic> NMZRQMXXYSRKVG4ZYJ5OUIN3AOLWJ2ZB5GVIGECAYM6G77D23MPA4BRP6I 2 20000000 21 4

Output

              _       _         
  /\/\   __ _| |_ ___| |__    _ 
 /    \ / _` | __/ __| '_ \  (_)
/ /\/\ \ (_| | || (__| | | |  _ 
\/    \/\__,_|\__\___|_| |_| (_)

MATCH DURATION:      120.0 min
PIECES ON GAME TABLE:    21 

RULES:
1. Players on each turn must remove at least 1 ASA Piece
2. Players on each turn must remove at most 4 ASA Piece
3. Who removes the last ASA Piece form the Game Table wins the match!

Player 1 - Dealer:      SVMHAG6PLL27YYGQX4ETEIZ2GHLSO6M5ICU2MBJVKMDT2ERPNSE27OGWIE
Player 2 - Opponent:    NMZRQMXXYSRKVG4ZYJ5OUIN3AOLWJ2ZB5GVIGECAYM6G77D23MPA4BRP6I 

AlgoNim ASA Pieces ID:   7329523
AlgoNim ASA Turn ID:     7329527 

AlgoNim Sink Account:                   7EUFKLR636O34XW2ZRMTVOCQAXIHUDEEKIY4ZPWAGDRU6A5AONKVN5K4R4
AlgoNim Game Table Account:             JBASDWK7MQNRCYUDZBBGR4DFHEGQTCSZQWNUMW4O2XBNON5CFLWALGKJCA
AlgoNim Bet Escrow Player 1 Account:    PUEKG6EPXF2HMUHB3GTTODXBGUXZX26YK36SJHU7X3ZPQWSKZXUZJAZT3Q
AlgoNim Bet Escrow Player 2 Account:    W6YG5653UWDU4XTSK2767FHLQOTLXGRG53ZJGV6SEVTSMWOMJOAAMBGTX4

Send 'algonim.match' file to your opponent join the match!

May the best win!

Step 2 - Join the match (Opponent)

To join the match the Opponent must decide whether to accept the Dealer’s bet proposal or not. On accepting the proposal, the Opponet will Opt-In to the match’s ASAs and fund both the Bet Escrows with the same amount, issuing an Atomic Transfer (already signed by the Dealer).

Input

$ python3 algonim.py join <opponent_mnemonic>

Output

      _       __                 ____  _____   _               
     / \     [  |               |_   \|_   _| (_)              
    / _ \     | |  .--./)  .--.   |   \ | |   __   _ .--..--.  
   / ___ \    | | / /'`\;/ .'`\ \ | |\ \| |  [  | [ `.-. .-. | 
 _/ /   \ \_  | | \ \._//| \__. |_| |_\   |_  | |  | | | | | | 
|____| |____|[___].',__`  '.__.'|_____|\____|[___][___||__||__]
                 ( ( __))                                      
                                                       by cusma

  Welcome to AlgoNim, the first crypto-mini-game on Algorand!  

The Dealer wants to bet 20.0 ALGO.
Do you want to join the match? [y/N]

Step 3 - Play turn (Dealer or Opponent)

To play a turn the Player must own the AlgoNim ASA Turn. With algonim.py play players may play both a regular turn or the last turn, closing the match and claiming the rewards locked in the Bet Escrows Account.

Input

$ python3 algonim.py play <player_mnemonic> 4

Output

Removing 4 pieces from the Game table...

Play Turn Atomic Transfer consists of:
1. Asset Send of 1 ASA Turn to the other player;
2. Asset Send of an amount P (1 <= P <= M) ASA Pieces from the Game Table Account to Sink Account;

OR

Play Last Turn Atomic Transfer consists of:
1. Asset Send of 1 ASA Turn to the other player;
2. Asset Send of an amount P (1 <= P <= M) ASA Pieces from the Game Table Account to Sink Account;
3. Asset Send of ASA Pieces total supply from Sink Account to winner account;
4. Close Bet Escrow Accounts claiming the betting rewards;

AlgoNim match status

Each player can check the current match status with algonim.py status:

Input

$ python3 algonim.py status NMZRQMXXYSRKVG4ZYJ5OUIN3AOLWJ2ZB5GVIGECAYM6G77D23MPA4BRP6I

Output

MATCH TOTAL PIECES:         21
PIECES ON THE GAME TABLE:   17
It's your turn! Play your best move!

OPPONENT BET ESCROW AMOUNT:  20100000
YOUR BET ESCROW AMOUNT:      20100000
Your Bet Escrow is still locked. 82 blocks left!

This displays ASA Pieces total amount for this match, ASA Pieces currently on the Game Table, and Player’s Turn and Bet Escrows status.

Bet Escrows closing

At the end of the match the winner can claim its own bet amount back, closing the Bet Escrow after it expires with algonim.py close:

Input

$ python3 algonim.py close NMZRQMXXYSRKVG4ZYJ5OUIN3AOLWJ2ZB5GVIGECAYM6G77D23MPA4BRP6I

If one of the players takes too long to play their turn, both players can close their expired Bet Escrows claiming their own bets back.

AlgoNim Architecure

AlgoNim leverages the Algorand’s main protocol features: Algorand Standalone Accounts, Algorand Standard Assets (ASA), Algorand Smart Contracts (ASC1) and Atomic Transfers (AT).

In designing AlgoNim, we worked backwards from the question of: how do you turn a board game into a “blockchain game”? The first step, required an analysis of Nim’s board game structure and rules in order to be able to translate them into the Algorand Architecture, that is: we decomposed the original game into basic elements represented by Algorand’s features.

Below is a brief overview of AlgoNim’s architectural elements followed by how these elements work and interact with each other.

Analyzing the “normal single heap” variant of Nim’s game tells us that we need to handle:

1. Two players - This is an easy one. Since the players interact with the Algorand blockchain, each player is represented by an Algorand Standalone Account. Players have different roles: the Dealer sets up the match while the Opponent joins the game.
2. Piece’s heap - Nim’s pieces are indivisible and their number is decided by the Dealer for each match. Therefore, it seems very natural to “tokenize” the game’s pieces, turning them into indivisible ASAs with a total supply determined by the Dealer.
3. Turns - We need to figure out how to manage game turns, the idea is to create an “ASA Turn” and whoever owns the token plays the turn.
4. Game Table - Is where real Nim’s pieces are placed and then removed on each turn by the players. Since pieces removal must follow certain rules, it seems very straight forward to translate it into a Contract Account, in which such rules are written in TEAL and “ASA Pieces” are placed by the Dealer and then removed on each turn.
5. Sink - This is probably the most counter-intuitive element of AlgoNim’s Algorand architecture: removing pieces from the Game Table in AlgoNim means transferring “ASA Pieces” from the Game Table Contract Account to the Sink Contract Account. While the former ensures that players’ moves follow the rules, the latter stores the removed pieces and serves also as a proof of victory.
6. Bet Escrows - This is where players’ bets are safely guarded until the winner shows the proof of victory or the match expires.

AlgoNim source code structure

The AlgoNim source code consists of 5 .py files:

1. algonim.py
2. algonim_moves.py
3. algonim_asa.py
4. algonim_asc1.py
5. algonim_lib.py

As their names suggest, each one is dedicated to specific functions.

algonim.py

Manages the AlgoNim CLI, letting players execute game moves simply with CLI commands. The CLI has been developed with docopt (which I strongly recommend as a CLI development tool). docopt turns CLI’s __doc__ into a useful dictionary of commands and their arguments.

algonim_moves.py

Provides game’s moves as function calls:

algonim_asa.py

AlgoNim runs using 2 different ASAs:

1. AlgoNim “ASA Piece”
2. AlgoNim “ASA Turn”

Both of them are created by the Dealer with the algonim.py setup command. Inside the match_setup the asa_pieces_create and asa_turn_create functions are called.

AlgoNim “ASA Piece”: this ASA represents the tokenization of match’s pieces to be removed from the Game Table. Being the representation of physical game pieces, the ASA should not be divisible. Their total supply is determined by the Dealer in the match_setup. The parameters of the asset create transaction are showed below:

data = {
        "sender": asset_creator['pk'],
        "fee": min_fee,
        "first": first_valid,
        "last": last_valid,
        "gh": gh,
        "total": total,
        "default_frozen": False,
        "unit_name": 'ALGONIMP',
        "asset_name": 'AlgoNim Piece',
        "manager": asset_creator['pk'],
        "reserve": asset_creator['pk'],
        "freeze": '',
        "clawback": '',
        "url": 'https://github.com/cusma/algonim',
        "flat_fee": True,
        "strict_empty_address_check": False,
        "decimals": 0
        }

AlgoNim “ASA Turn”: this ASA represents the turn. Players are obliged to pass it to the opponent in order to play the moves. As a way to tokenize AlgoNim’s turn structure, this ASA should not be divisible and should be unique.

data = {
        "sender": asset_creator['pk'],
        "fee": min_fee,
        "first": first_valid,
        "last": last_valid,
        "gh": gh,
        "total": 1,
        "default_frozen": False,
        "unit_name": 'ALGONIMT',
        "asset_name": 'AlgoNim Turn',
        "manager": asset_creator['pk'],
        "reserve": asset_creator['pk'],
        "freeze": '',
        "clawback": '',
        "url": 'https://github.com/cusma/algonim',
        "flat_fee": True,
        "strict_empty_address_check": False,
        "decimals": 0
        }

The clawback address and freeze address of both ASA Pieces and ASA Turn are left blank.

algonim_asc1.py

This file contains AlgoNim’s “core functions”. Game rules are written in TEAL using PyTeal, AlgoNim’s ASC1s constitute the game architecture. They regulate interactions between players’ Standalone Accounts and AlgoNim’s ASAs, checking a set of Atomic Transfers that represent game moves. It is worth noting that a new set of ASCs1 and ASAs are generated for each match, making the game architecture unique for each new match. In other words, it is not possible to play with ASCs1 and ASA belonging to different matches.

We will go through each AlgoNim ASC1 giving a brief overview of their TEAL logic, for a deeper understanding of the complete TEAL code it is necessary to take a step further into the source code in which each high level TEAL condition is in turn constituted by more elementary conditions (until reaching the op-codes).

ASC1 Sink

Sink TEAL logic checks the following conditions:

ASC1 Game Table

Game Table TEAL logic checks the following conditions:

ASC1 Bet Escrow

Bet Escrow TEAL logic checks the following conditions:

algonim_lib.py

The functions in this library are more general ones and not strictly related to AlgoNim. Starting from some of Algorand Python SDK elements, this little library provides utilities that let us instantiate an Algod client, write unsigned pay or asset send transactions, push them on chain, and so on. Feel free to expand this library and include it in your personal projects.

TEAL debugging tips

Debugging TEAL source code can turn out to be a difficult process if you don’t know the right tricks. For this reason I would like to share some useful tips that personally helped me in developing AlgoNim. These are nothing extraordinary but you might find them useful.

Testing TEAL Code with Delegated Logic Signature

Once TEAL source code has been generated using PyTeal or handwritten, you need to test it! This is a crucial step in order to ensure that your Algorand Smart Contracts work the way you expect and to avoid exposing users to security risks. AlgoNim utilizes TEAL Contract Accounts but when starting, it is generally simpler to use delegated Logic Signatures instead. Let’s go through the steps of this debugging approach. Suppose we want to test the Game Table Contract Account. Instead of generating and compiling its TEAL source code we will take the following steps:

1. Create a new regular “Dummy Game Table Standalone Account” , that will play the role of a TEAL Contract Account.
2. Sign the TEAL bytecode with the “Dummy Game Table Standalone Account” private key, generating a delegated LogSig (e.g., use goal clerk compile with the options -s and -a <DummyGameTableStandaloneAccount>). More information in this Simple TEAL Example and Account Delegation in the SDKs documentation.
3. Use the delegated LogSig to perform your tests and debug your TEAL code.

Transactions dryrun

Your most powerful ally in TEAL development and debugging is the command goal clerk dryrun. In case a transaction is rejected by TEAL logic, dryrun is the way to discover what piece of logic is failing. In order to use dryrun easily, I suggest the following approach:

1. Write into a file the transaction (or group of transactions) you would like to test against some TEAL logic. To do so, the Python SDK provides the useful write_to_file function.
2. Once your raw transaction (or group of transactions) has been written into a file, dryrun it executing goal clerk dryrun from the CLI.
3. Inspect the result of goal clerk dryrun and find out what piece of TEAL logic is failing.

Gameplay Video

Open future implementations

1. Improving robustness of Bet Escrows (preventing players from stopping the game in the middle and simply waiting for the Bet Escrows to expire);
2. Freezing the match’s ASAs for anyone but the players;
3. Automatically destroying the match’s ASAs at the end of the game;
4. Adding ASA AlgoNim Score to the Sink from the Scores Pool as a reward for the winner;
5. Implementing a “Multi-heaps” variant;
6. Implementing a “Championship” mode (2 out of 3 matches).

Troubleshooting

Issue with KeyError: 'microalgo_bet_amount'

This issue arises if you do not use the latest version of msgpack. Use version 1.0.0.

Run:

$ pip3 install --upgrade msgpack

Contact

If you discover any security vulnerability or issues and want to suggest any improvement proposals please reach out to me at: [email protected]