Saturday, December 6, 2025

GOOFSPIEL: Determinist's Bane

GOOFSPIEL: Determinist's Bane

Jerod Michel, Gao Yucheng
December 2024

"Everyone sees what you appear to be, few experience what you really are."

— Niccolò Machiavelli

Description

Goofspiel—German for "Game of Fools"—is anything but foolish. It is an abrupt arena where perfect information meets imperfect human judgment. Two players, each holding an identical hand of thirteen cards, compete for prizes drawn from a third deck. The rules are deceptively simple: players bid cards simultaneously, the higher bid takes the prize. Yet within this simplicity lies a profound truth about conflict: knowing everything does not mean understanding everything.

This is not a game of chance. It is a game of projection—of convincing your opponent that your eight is a king, and their king is an eight. While Chess shows you the battlefield, and NIM reveals the binary logic of finite economics, Goofspiel shows you the enemy's arsenal but never their intentions.

The prizes sit openly between you—their values clear, but the bids are made in the confines of your opponent's mind. Victory goes not to the player who values the prize most, but to the one who most accurately prices their opponent's desperation.

History

The game first came to public consciousness under the name "Goofspiel" in a 1940 issue of Esquire magazine, presented as a diversion. The name suggests a game for the simple—yet another layer of misdirection. Its mathematical constitution remained hidden for decades.

It's uncovering came in the Cold War crucible of game theory. As mathematicians like von Neumann and Nash dissected conflict through Prisoner's Dilemmas and zero-sum games, Goofspiel sat quietly in the background—too complex for immediate solution, but too elegant to be ignored for much longer.

Then came Sheldon Ross in 1971, who delivered the first definitive mathematical autopsy. His proof demonstrated what experienced players had long suspected: there is no single "best" way to play Goofspiel. No pure strategy can dominate. The game requires deception, unpredictability, and mixed strategies. Optimal play involves calculated randomness—a concept that likely would have made the generals of old shudder.

It is fitting that a game about values hidden in plain sight would itself conceal such mathematical depth within such simple rules. It has since traveled under many aliases: "The Game of Pure Strategy," "Prisoner's Cards," and in some circles, "The Diplomat's Dilemma." Each name captures a different facet of its essence, but all point to the same truth: in a world of perfect information, the only thing left to hide is yourself.

Rules and Gameplay

Materials

Three full suits from a standard deck of playing cards, i.e., the ranks Ace (1) through King (13) of each of the three suits are required. For this discussion, these will be represented thusly:

  • Player 1's Hand: The Club suit (♣). Your arsenal.
  • Player 2's Hand: The Spade suit (♠). The opponent's arsenal.
  • Prize Deck: The Diamond suit (♦). The spoils, or, prizes, shuffled and placed between you.

The Hearts (♥) remain in the box.

The Game

The game proceeds over thirteen rounds—a single, bloody season of conflict.

  1. Deploy the first Prize. The top Diamond is revealed and placed in the center. Its value is the objective for the round.
  2. Private Council. Both players simultaneously select a card from their own hand. This is your bid—your commitment. It is placed face-down. Your opponent does the same.
  3. Revelation. Bids are revealed. A simple calculus determines the victor:
    • The higher bid claims the Diamond prize. Its value is added to their purse.
    • The lower bid gains nothing (except, perhaps, experience).
    • In the event of a tie, no one can claim the prize—there is just scorched earth.
  4. Graveyard. The bid cards, both yours and your opponent's, are discarded to the graveyard. They are spent. They cannot be used again.

The game ends when all thirteen Diamonds have been contested. The player with the highest total value in their purse is the victor.

The Strategic Terrain

Do not be fooled by the procedural simplicity. The game is a marathon of resource calculation and allocation. Wasting a King (13) to secure a low-ranking card is a catastrophic misallocation, a tell-tale sign of desperation, or just foolishness.

The core dilemma is eternal: Do you fight for the current prize, or do you conserve your strength for the future? There are no reinforcements. Every card you play is a permanent reduction of options. The game is a slow and inexorable constriction of possibility, and a lesson in the economy of violence.

Victory is not about winning the most rounds. It is about winning the right rounds. It is about ensuring that the sum of your victories outweighs the sum of your opponent's, no matter what individual skirmishes you might concede.

The true genius of Goofspiel reveals itself not in the first round, but in the second. Once both players understand the rules, they enter into a metagame of prediction and counter-prediction. You are no longer playing cards; you are playing the ghost of your opponent's previous decisions. This is where the mathematics are discerned.

That Goofspiel has no Pure Strategy Equilibrium

Let $A = (a_1, \dots, a_n)$ and $B = (b_1, \dots, b_n)$ be the players' strategies, where $a_i, b_j$ represent the bids for prize $v_i$. The total payoff for Player 1 is:

The payoff function $\pi(A,B) = \sum_{i=1}^n v_i \cdot \mathbb{I}_{a_i > b_i}$
The following can be found in [1].
For $n \geq 2$ distinct prizes, Goofspiel admits no pure strategy Nash equilibrium.

Assume contrary that $(A^*, B^*)$ is a pure strategy Nash equilibrium. Consider the reordering of prizes such that $v_1 > v_2 > \cdots > v_n$.

No ties in equilibrium: If $a_i^* = b_i^*$ for any $i$, either player can profit by deviating to $a_i^* + \epsilon$.

Monotonicity: In equilibrium, we must have $a_i^* > a_j^* \iff b_i^* > b_j^*$ for all $i,j$. Otherwise, a profitable reallocation exists.

Without loss, assume both sequences are increasing: $a_1^* < \cdots < a_n^*$ and $b_1^* < \cdots < b_n^*$.

The expected payoff becomes:

$$\pi(A^*, B^*) = \sum_{i=1}^n v_i \cdot \mathbb{I}_{a_i^* > b_i^*}$$

Contradiction: Consider the alternative pairing where Player 1 uses the identity mapping $a_i = i$ against Player 2's strategy. The maximum is achieved when $\mathbb{I}_{a_i > b_i} = 1$ for all $i$, but this cannot be an equilibrium as Player 2 would deviate.

More precisely, for any fixed pairing $(A,B)$, there exists $k$ such that:

$$\sum_{i=1}^n v_i \mathbb{I}_{a_i > b_i} < \max_{\sigma \in S_n} \sum_{i=1}^n v_i \mathbb{I}_{a_i > b_{\sigma(i)}}$$

where $S_n$ is the symmetric group. The right-hand side represents the optimal reassignment of bids against the fixed strategy.

Thus, no pure strategy profile can be immune to unilateral deviations.

The Nash Equilibrium Interpretation
Dror's result demonstrates that Goofspiel belongs to the class of games where the only Nash equilibria occur in mixed strategies. The inequality: $$\max_A \min_B \pi(A,B) = \min_B \max_A \pi(A,B) = 0$$ holds, and the value of the game is zero under standard scoring. This formalizes the intuition that in optimal play, no deterministic pattern can prevail—each player must randomize their bids to remain unpredictable. The mathematical necessity of deception emerges not as a psychological preference, but as a topological consequence of the strategy space.
For the Practitioner
For the working strategist, this theorem provides a cold consolation: your intuition that "there must be a best way to bid" is mathematically false. The game resists any attempt at deterministic mastery. Your only refuge lies in calculated randomness—the very mixed strategies that define the game's Nash equilibria. In this light, Goofspiel becomes a perfect laboratory for testing how one does with fundamental uncertainty.

Example of Play

The Theater of Thirteen Rounds

What follows is not a transcript, but an autopsy of a typical game—a demonstration of the psychological warfare that unfolds when both players understand the mathematical void at Goofspiel's heart.

Round Prize Player 1 (♣) Player 2 (♠) Outcome
1 5♦ 5 6 Player 2 wins, spending highly
2 2♦ 2 1 Player 1 wins efficiently
3 13♦ 4 12 Player 2 wins the King, overcommitting
4 8♦ 10 3 Player 1 wins, wasting a 10
5 1♦ 1 2 Player 2 wins, continuing the pattern

Let us examine the strategic subtext of these opening moves.

Rounds 1-3: The Opening Gambits

Player 2 begins aggressively, using a 6 to claim a mediocre 5. A questionable allocation of force, signaling either confidence or profligacy. Player 1 responds with surgical efficiency, taking the 2 with a 2—perfect valuation.

Then, the first major prize appears: the King (13). Player 1 makes a bold, almost reckless bluff, bidding a mere 4. Player 2, perhaps fearing a trap or overestimating their opponent's reserves, responds with a 12. Player 1's bluff fails, but it reveals something precious: Player 2 is willing to spend high cards early.

Rounds 4-5: The Psychological Shift

Here, the game's true nature emerges. The 8 appears—a substantial prize. Player 1, perhaps frustrated by the failed bluff or misreading Player 2's remaining strength, deploys a 10. This is a critical error: wasting a high card on a medium prize. Player 2, showing restraint, bids only a 3, conceding the round but preserving their high cards.

The game continues, but the damage is done. Player 1 has revealed their hand's diminishing quality, while Player 2 has conserved their strength. The remaining rounds become a slow, inevitable constriction.

The Endgame

By round 10, the score stands at Player 1: 28 points, Player 2: 35 points. The remaining prizes are 11, 7, and 3. Player 1 holds 11, 13; Player 2 holds 7, 9.

  • Prize 11: Player 1 must bid their 11 to have any hope. Player 2, knowing this, bids 7. Player 1 claims the prize but is left with only a 13.
  • Prize 7: Player 2 bids 9, easily beating Player 1's forced 13—a catastrophic overpayment.
  • Prize 3: Player 1 has no cards left. Player 2 claims it with whatever remains.

Final score: Player 1: 39, Player 2: 45.

Notice that Player 1 won more individual rounds (6 to Player 2's 7), yet lost decisively. Goofspiel is not about victory in battle, but the economic management of force. Player 2 understood this; Player 1 won battles but lost the war through poor resource allocation. The player who appears to be winning in the early rounds is often the one hemorrhaging strategic capital.
The Digital Implementation
In our Bash implementation, the Medium AI would have noted Player 1's wasteful bid of a 10 on prize 8, decrementing its internal PLAYER_HIGH_CARD_COUNT. The Hard AI would have further detected the aggressive pattern and adapted its bidding strategy accordingly, perhaps bluffing more frequently against such an opponent. The mathematics of Dror's proof finds its expression in these adaptive heuristics—the mixed strategies playing out in code.

Play Goofspiel in Command Line

Our Goofspiel implementation posits a simple bidding arena through array manipulations. Player hands and the prize deck are each represented as simple arrays, where card removal and scoring are handled via array slicing and filtering. We use Unicode for suits to give some visual clarity, and we preserve the game's "hidden information" by concealing the AI's actual cards, and reveal only the remaining count.

The AI employs a multi-layered strategy that evolves with difficulty. At the easy level, the computer uses straightforward value-based bidding, matching card values to prize values with some minor randomization. The medium AI introduces psychological warfare through bluffing and pattern recognition, and tracking the player's high-card usage to detect strategic tendencies. The hard AI represents our more ambitious implementation, performing real-time game state analysis that considers score differentials, remaining high cards, and inferred player strategies for adapting its approach.

What makes this implementation compelling is how it demonstrates that, even in a constrained scripting environment, we can model complex decision-making processes that account for incomplete information, opponent modeling, and multi-round strategy. The AI doesn't just react to the current prize, but builds a narrative for the player's style throughout, and counters it accordingly.


#!/bin/bash

# Goofspiel Game in Bash with Machine Learning-inspired difficulty levels

# game state variables
declare -a player_hand=({1..13})           # clubs - player's bidding cards
declare -a ai_hand=({1..13})               # spades - AI's bidding cards  
declare -a prize_deck=({1..13})            # diamonds - prizes to be won
declare -a player_purse=()                 # player's acquired prizes
declare -a ai_purse=()                     # AI's acquired prizes
declare -a chosen_bids=()                  # chosen bids not yet revealed
PLAYER_HIGH_CARD_COUNT=4                   # for 10, J, Q, K
difficulty="medium"

current_prize=""                           # current prize card from top of deck

# define card suit symbols
SPADE="\u2660"
CLUB="\u2663"
DIAMOND="\u2666"
HEART="\u2665"

# function to display the game board
display_table() {
    echo
    echo "==== New Round ===="
    echo
    echo "--- Player's Hand ----"
    hand_string=""
    for card in "${player_hand[@]}"; do
        if [[ -n "$hand_string" ]]; then
            hand_string+=" |"
        fi
        hand_string+="${card}$CLUB"
    done
    echo -e "$hand_string"
    echo
    echo "--- AI's Hand ----"
    echo -e "[${#ai_hand[@]} cards ($SPADE ) remaining]"
    echo
}

# function to get initial game setup
setup_game() {
    echo "Welcome to Goofspiel!"
    echo
    
    # difficulty selection
    while true; do
        echo "Select difficulty:"
        echo "1 - Easy (computer plays with minimal considerations of pattern)"
        echo "2 - Medium (computer bluffs and considers some patterns)"  
        echo "3 - Hard (computer considers patterns aggressively and bluffs aggressively)"
        read -p "Enter choice (1-3): " diff_choice
        
        case $diff_choice in
            1) difficulty="easy"; break ;;
            2) difficulty="medium"; break ;;
            3) difficulty="hard"; break ;;
            *) echo "Invalid choice! Please enter 1, 2, or 3." ;;
        esac
    done
    
    echo "Difficulty set to: $difficulty"
    echo
}

#function to pull a prize at random from the deck
draw_prize() {
    if [ ${#prize_deck[@]} -eq 0 ]; then
        echo "No more prizes left!"
        return 1
    fi
    
    # take the first card
    current_prize="${prize_deck[0]}"
    
    # remove the first card from the deck
    prize_deck=("${prize_deck[@]:1}")
    
    echo -e "~~~~~ Current prize: ${current_prize}$DIAMOND  ~~~~~"
}

shuffle_prize_deck() {
    prize_deck=($(shuf -e "${prize_deck[@]}"))
    echo "Prize deck shuffled!"
}

in_array() {
  local needle="$1"
  shift
  for element in "$@"; do
    if [[ "$element" == "$needle" ]]; then
      return 0 # found
    fi
  done
  return 1 # not found
}

player_to_bid() {
    while true; do
        echo "Make a bid! Enter a rank from your hand (11 = J, 12 = Q, 13 = K):"
        read -p "> " input
        
        # validate input
        if ! in_array "$input" "${player_hand[@]}"; then
            echo ""$input" is not in your hand!"
            continue
        else
            chosen_bids+=($input)
            new_hand=()
            for card in "${player_hand[@]}"; do
	        if [[ "$card" != "$input" ]]; then
	            new_hand+=("$card")
	        fi
	    done
	    player_hand=("${new_hand[@]}")
            break
        fi
    done
}

AI_to_bid_easy() {
    # define the "target bid" as the prize value, plus or minus 1
    target_bid=$(( $current_prize + (RANDOM % 3 - 1) )) # this gives -1, 0, or +1
    # ensure the target bid is between 1 and 13
    target_bid=$(( target_bid < 1 ? 1 : (target_bid > 13 ? 13 : target_bid) ))

    # check if the target_bid is in the AI's hand
    if [[ " ${ai_hand[@]} " =~ " ${target_bid} " ]]; then
    ai_bid=$target_bid
    else
        # if not, find the closest available card in the hand
        closest_diff=14
        for card in "${ai_hand[@]}"; do
            diff=$(( card > target_bid ? card - target_bid : target_bid - card ))
            if (( diff < closest_diff )); then
                closest_diff=$diff
                ai_bid=$card
            fi
        done
    fi
    chosen_bids+=($ai_bid)
    new_AI_hand=()
    for card in "${ai_hand[@]}"; do
        if [[ "$card" != "$ai_bid" ]]; then
            new_AI_hand+=("$card")
        fi
    done
    ai_hand=("${new_AI_hand[@]}")
}

get_value_bid() {
    local prize_value="$1"
    local hand=("${@:2}")  # all remaining arguments are the hand
    
    # same logic as Easy AI
    target_bid=$(( prize_value + (RANDOM % 3 - 1) ))
    target_bid=$(( target_bid < 1 ? 1 : (target_bid > 13 ? 13 : target_bid) ))

    # check if target_bid is in hand
    if [[ " ${hand[@]} " =~ " ${target_bid} " ]]; then
        echo "$target_bid"
        return
    fi
    
    # otherwise find closest card
    local closest_diff=14
    local best_card
    for card in "${hand[@]}"; do
        local diff=$(( card > target_bid ? card - target_bid : target_bid - card ))
        if (( diff < closest_diff )); then
            closest_diff=$diff
            best_card="$card"
        fi
    done
    echo "$best_card"
}

# choose a strategy based on the prize and the player's state
AI_to_bid_medium() {
    local ai_bid

    if [[ $current_prize -gt 9 ]]; then
        # high prize logic
        if [[ $PLAYER_HIGH_CARD_COUNT -gt 0 ]]; then
            # player is still strong. Be unpredictable.
            if [[ $((RANDOM % 2)) -eq 0 ]]; then
                # bluff: bid a low card (1-3)
                ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 <= 3' | head -1)
                # if no low card, default to value mode
                if [[ -z "$ai_bid" ]]; then
                    ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
                fi
            else
                # fight: bid a high card (>= 11)
                ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 >= 11' | head -1)
                # if no high card, default to value mode
                if [[ -z "$ai_bid" ]]; then
                    ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
                fi
            fi
        else
            # player is weak. Steal prize efficiently.
            # find the smallest card in hand that is greater than the expected player bid
            ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
        fi
    else
        # low prize logic - use value mode
        ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
    fi
    chosen_bids+=($ai_bid)
    new_AI_hand=()
    for card in "${ai_hand[@]}"; do
        if [[ "$card" != "$ai_bid" ]]; then
            new_AI_hand+=("$card")
        fi
    done
    ai_hand=("${new_AI_hand[@]}")
}

AI_to_bid_hard_proper() {
    # game-theoretic approach for Goofspiel
    local ai_bid
    
    # Known optimal strategy patterns for Goofspiel:
    case $current_prize in
        13|12|11)  # high prizes - bid high but not necessarily highest
            if [[ " ${ai_hand[@]} " =~ " 13 " ]] && [[ $((RANDOM % 3)) -eq 0 ]]; then
                ai_bid=13
            elif [[ " ${ai_hand[@]} " =~ " 12 " ]]; then
                ai_bid=12
            else
                ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
            fi
            ;;
        10|9|8)    # medium-high prizes - mixed strategy
            local strategy=$((RANDOM % 4))
            case $strategy in
                0) ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 >= 11' | head -1) ;;
                1) ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 <= 3' | head -1) ;;
                *) ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}") ;;
            esac
            ;;
        *)         # low prizes - bid efficiently
            # count remaining high cards in both hands
            local remaining_high_cards=0
            for card in "${ai_hand[@]}" "${player_hand[@]}"; do
                [[ $card -gt 9 ]] && ((remaining_high_cards++))
            done
            
            if [[ $remaining_high_cards -lt 3 ]]; then
                # late game - conservative bidding
                ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
            else
                # early game - sometimes bluff on low prizes
                if [[ $((RANDOM % 5)) -eq 0 ]]; then  # 20% bluff chance
                    ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 <= 2' | head -1)
                    [[ -z "$ai_bid" ]] || ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
                else
                    ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
                fi
            fi
            ;;
    esac
    
    # fallback if the above logic fails
    if [[ -z "$ai_bid" ]] || ! in_array "$ai_bid" "${ai_hand[@]}"; then
        ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
    fi
    chosen_bids+=($ai_bid)
    new_AI_hand=()
    for card in "${ai_hand[@]}"; do
        if [[ "$card" != "$ai_bid" ]]; then
            new_AI_hand+=("$card")
        fi
    done
    ai_hand=("${new_AI_hand[@]}")
}

AI_to_bid_hard_adaptive() {
    local ai_bid
    
    # calculate game phase and player style from available data
    local game_phase=$((13 - ${#prize_deck[@]}))  # rounds played so far (0-12)
    local player_score=0
    local ai_score=0
    
    # calculate current scores from purses
    for card in "${player_purse[@]}"; do
        player_score=$((player_score + card))
    done
    for card in "${ai_purse[@]}"; do
        ai_score=$((ai_score + card))
    done
    
    # analyze player's bidding pattern from score
    local player_efficiency="unknown"
    if [[ $game_phase -gt 3 ]]; then  # enough rounds to have a pattern
        if [[ $player_score -gt $((game_phase * 7)) ]]; then
            player_efficiency="aggressive"  # winning more than average
        elif [[ $player_score -lt $((game_phase * 5)) ]]; then
            player_efficiency="conservative"  # winning less than average
        else
            player_efficiency="balanced"
        fi
    fi
    
    # count remaining high cards for strategic decisions
    local player_high_remaining=0
    local ai_high_remaining=0
    for card in "${player_hand[@]}"; do
        [[ $card -gt 9 ]] && ((player_high_remaining++))
    done
    for card in "${ai_hand[@]}"; do
        [[ $card -gt 9 ]] && ((ai_high_remaining++))
    done
    
    # strategic decision based on game state
    if [[ $current_prize -gt 10 ]]; then
        # high prize strategy
        if [[ $player_efficiency == "aggressive" ]] && [[ $player_high_remaining -gt 1 ]]; then
            # aggressive player with high cards - fight or bluff randomly
            if [[ $((RANDOM % 3)) -eq 0 ]]; then
                # bluff: bid low to trick aggressive player into overbidding
                ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 <= 3' | head -1)
                [[ -z "$ai_bid" ]] && ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
            else
                # fight: bid high to compete
                ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 >= 11' | head -1)
                [[ -z "$ai_bid" ]] && ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
            fi
        elif [[ $player_score -gt $ai_score ]] && [[ $ai_high_remaining -gt $player_high_remaining ]]; then
            # behind but have high card advantage - push hard
            ai_bid=$(printf '%s\n' "${ai_hand[@]}" | awk '$1 >= 11' | head -1)
            [[ -z "$ai_bid" ]] && ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
        else
            # default high prize strategy
            ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
        fi
        
    elif [[ $current_prize -lt 6 ]]; then
        # low prize strategy
        if [[ $player_efficiency == "conservative" ]] || [[ $player_high_remaining -eq 0 ]]; then
            # conservative player or player out of high cards - bid minimally
            ai_bid=$(printf '%s\n' "${ai_hand[@]}" | sort -n | head -1)
        elif [[ $ai_score -gt $player_score ]] && [[ $game_phase -gt 8 ]]; then
            # ahead late game - conserve high cards
            ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
        else
            # default low prize - sometimes bluff with very low card
            if [[ $((RANDOM % 4)) -eq 0 ]] && [[ " ${ai_hand[@]} " =~ " 1 " ]]; then
                ai_bid=1
            else
                ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
            fi
        fi
        
    else
        # medium prize strategy (6-10)
        if [[ $player_efficiency == "aggressive" ]] && [[ $player_high_remaining -lt 2 ]]; then
            # aggressive player running out of high cards - they might bluff
            # counter by bidding slightly higher than value
            ai_bid=$(get_value_bid "$((current_prize + 1))" "${ai_hand[@]}")
            [[ -z "$ai_bid" ]] && ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
        else
            # standard medium prize approach
            ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
        fi
    fi
    
    # final fallback
    if [[ -z "$ai_bid" ]] || ! in_array "$ai_bid" "${ai_hand[@]}"; then
        ai_bid=$(get_value_bid "$current_prize" "${ai_hand[@]}")
    fi
    chosen_bids+=($ai_bid)
    new_AI_hand=()
    for card in "${ai_hand[@]}"; do
        if [[ "$card" != "$ai_bid" ]]; then
            new_AI_hand+=("$card")
        fi
    done
    ai_hand=("${new_AI_hand[@]}")
}

# function to check if game is over
game_over() {
    [ "${#prize_deck[@]}" -eq 0 ]  # game ends when prize deck is empty
}

determine_winner() {
    local player_total=0
    local ai_total=0
    
    # sum over player's purse
    for card in "${player_purse[@]}"; do
        player_total=$((player_total + card))
    done
    
    # sum over AI's purse  
    for card in "${ai_purse[@]}"; do
        ai_total=$((ai_total + card))
    done
    
    echo "Player total: $player_total"
    echo "AI total: $ai_total"
    
    if [ $player_total -gt $ai_total ]; then
        echo "Player wins!"
    elif [ $ai_total -gt $player_total ]; then
        echo "AI wins!"
    else
        echo "It's a tie!"
    fi
}

# main game loop
main() {
    setup_game
    shuffle_prize_deck
    
    while true; do
        display_table
        
        if game_over; then
	    determine_winner
	    break
	fi
	
	draw_prize
	player_to_bid
	
	if [ $difficulty == "easy" ]; then
	    AI_to_bid_easy
	elif [ $difficulty == "medium" ]; then
	    AI_to_bid_medium
	else
	    AI_to_bid_hard_adaptive
	fi
	
	# === BIDS ARE REVEALED ===
        player_bid="${chosen_bids[0]}"  # assuming player bid is first
        ai_bid="${chosen_bids[1]}"      # AI bid is second
        
        echo "Player bid: $player_bid | AI bid: $ai_bid"
        
        # === UPDATE PLAYER_HIGH_CARD_COUNT HERE ===
        if [[ $current_prize -lt 10 ]] && [[ $player_bid -gt 9 ]]; then
            echo "AI notes: Player wasted a high card on a low prize..."
            (( PLAYER_HIGH_CARD_COUNT-- ))
        fi
        
        if [[ $player_bid -gt $ai_bid ]]; then
            player_purse+=("$current_prize")
            echo -e "Player purses $current_prize daimonds!"
        elif [[ $player_bid -lt $ai_bid ]]; then
            ai_purse+=("$current_prize")
            echo -e "Sorry, computer purses $current_prize daimonds." 
        else
            echo -e "Round is a tie! No player purses these $current_prize diamonds..."
        fi
        
        new_deck=()
        for card in "${prize_deck[@]}"; do
	    if [[ "$card" != "$current_prize" ]]; then
	        new_deck+=("$card")
	    fi
	done
        prize_deck=("${new_deck[@]}")

        chosen_bids=()
    done
    echo
    read -p "Play again? (y/n): " play_again
    if [[ $play_again =~ ^[Yy]$ ]]; then
        exec "$0"  # Restart the script
    else
        echo "Thanks for playing Goofspiel!"
    fi

}
	    
# Start the game
main

References

[1] M. Dror, "Simple proof for Goofspiel: the game of pure strategy," Advances in Applied Probability, vol. 21, no. 3, pp. 711–712, 1989.
    Retrieved from Cambridge Core

Dawson's Kayles: The Impartial Rank

$\newcommand{\nim}{\operatorname{nim}}$

Dawson's Kayles

Jerod Michel, Gao Yucheng
December 2024

"War is the realm of uncertainty; three quarters of the factors on which action in war is based are wrapped in a fog of greater or lesser uncertainty."

— Carl von Clausewitz, On War (1832), Book 1, Chapter 3

Description

Dawson's Kayles looks simple at first glance. There is a row of pawns from which players take turns removing any two that are adjacent. The last move wins. But don't be deceived.

History

Dawson's Kayles was invented by Thomas Rayner Dawson (1889-1951), a British chess composer, and considered the "father of fairy chess". Dawson was incredibly prolific: he created over 5,000 chess problems, pioneered many fairy chess pieces (pieces whose movements are different from those of traditional chess pieces) and conditions, was editor of the "Fairy Chess Review", and made significant contributions to combinatorial game theory. Dawson's Kayles emerged in the 1930s when Dawson was exploring impartial games that could be analyzed using the Sprague-Grundy theorem. It's a variant of Kayles (which itself is a bowling-pin game) but reinterpreted as a chess-like game.

Rules and Gameplay

  • Setup: Begin with a single row of $n$ identical tokens.
  • Turn Order: Two players alternate turns, starting with the first player.
  • Legal Moves: On each turn, a player must remove exactly two adjacent tokens.
  • Move Restrictions:
    • Tokens removed must be contiguous (i.e., must be direct neighbors),
    • A player cannot remove single tokens or three tokens,
    • A player cannot skip a turn if a legal move exists.
  • End Condition: The game ends when no adjacent pair of tokens remains.
  • Victory Condition: The player who makes the last legal move wins. (This is considered normal play.)

Mathematical Context: Dawson's Kayles is an impartial game where each position decomposes into independent subgames, allowing analysis through Grundy numbers and the Sprague-Grundy theorem.

Sprague-Grundy Theory

We begin with some basic concepts. The following provide a framework for analyzing games such as Dawson's Kayles through their underlying combinatorial structure.

Combinatorial Game

A combinatorial game is a tuple $(P, M, p_0)$ where:

  1. $P$ is a set of positions,
  2. $M: P \to 2^P$ gives the set of moves from each position,
  3. $p_0 \in P$ is the starting position,
  4. players alternate moves, and
  5. the game terminates in finite time (i.e., it is not an infinite sequence).

Impartial Game

A combinatorial game is impartial if:

  1. the set of available moves depends only on the position, and not on which player moves, and
  2. both players have the same moves available from every position.

Normal Play Convention

Under normal play, the player who cannot move loses.

Nim, which we discussed in Chapter 1, serves as the foundational example of an impartial game. Its significance stems from the Sprague-Grundy Theorem, which establishes that every impartial game, under normal play, is equivalent to a Nim heap. The Grundy number (or nimber) of a position generalizes the concept of Nim heap sizes to arbitrary impartial games, providing a complete combinatorial invariant for game equivalence. Dawson's Kayles, while more structurally complex, inherits this theoretical framework and can be analyzed through the lens of nimber calculus.

To systematically analyze such games it is convenient to use graphical representation.

Game Graph

The game graph is a directed acyclic graph $G = (V,E)$ where:

  1. $V$ is the set of game positions, and
  2. $(u,v) \in E$ if and only if there exists a legal move from $u$ to $v$.

The following position types admit a recursive characterization that will form the computational core of our impartial game analysis.

P- and N-Positions

For any position in an impartial combinatorial game under normal play:

  1. a P-position is a position where the Previous player (the player who just moved) can force a win, and
  2. an N-position is a position where the Next player (the player about to move) can force a win.

The following lemma describes the recursive procedure underlying both the proof of the Sprague-Grundy theorem as well as practical computation of Grundy numbers for Dawson's Kayles positions.

Characterization of P/N-Positions

For any position $p$ in an impartial combinatorial game under normal play:

  1. $p$ is a P-position if and only if every move from $p$ leads to an N-position, and
  2. $p$ is an N-position if and only if there exists at least one move from $p$ to a P-position.

Sprague-Grundy Theory

The true power of impartial game analysis emerges when we consider games which decompose into independent components.

Disjunctive Sum of Games

The disjunctive sum of $n$ combinatorial games $G_1, G_2, \dots, G_n$, denoted $G_1 \oplus G_2 \oplus \cdots \oplus G_n$, is a game where:

  1. a position is an $n$-tuple $(p_1, p_2, \dots, p_n)$ with $p_i$ a position in $G_i$,
  2. a move consists of choosing exactly one component game $G_i$ and making a legal move in that component, and
  3. the game ends when no moves are possible in any component.

Dawson's Kayles naturally decomposes into a disjunctive sum, as independent rows can be analyzed separately and their strategic values combined. We recall the following from our previous chapter.

Minimum Excludant (mex)

For any subset $S \subseteq \mathbb{N}\cup\{0\}$, the minimum excludant of $S$ is given by:

\[ \text{mex}(S) = \min\{n \in \mathbb{N}_0 : n \notin S\} \]

Grundy Number (Nimber)

The Grundy number (or nimber) of a position $p$, denoted $\nim(p)$, is defined recursively as:

\[ \nim(p) = \text{mex}\{\nim(q) : q \in M(p)\} \]

where $\text{mex}(S)$ (minimum excludant) of a set $S$ of nonnegative integers is the smallest nonnegative integer not in $S$.

The Grundy number provides a refinement of the P/N-position classification: a position $p$ is a P-position if and only if $\nim(p) = 0$, and an N-position if and only if $\nim(p) > 0$. The following can be found in [1].

Sprague-Grundy Theorem

Every impartial combinatorial game under normal play is equivalent to a Nim heap of size $\nim(p)$. Moreover, for a disjunctive sum of games $G = G_1 \oplus G_2 \oplus \cdots \oplus G_n$ with position $p = (p_1, p_2, \dots, p_n)$, the Grundy number is given by:

\[ \nim(p) = \nim(p_1) \oplus \nim(p_2) \oplus \cdots \oplus \nim(p_n) \]

where $\oplus$ denotes the nim-sum (bitwise XOR) operation.

The proof proceeds by structural induction on the game graph. Notice the Grundy number correctly characterizes move options: from any position $p$ with $\nim(p) = n$, we have that for every $m < n$ there exists a move to some position $q$ with $\nim(q) = m$, but no move to a position distinct from $p$ with Grundy number $n$. Notice also that the disjunctive sum $G_1 \oplus \cdots \oplus G_n$ with position $p = (p_1, \dots, p_n)$, we may let $N = \nim(p_1) \oplus \cdots \oplus \nim(p_n)$. Then for any $t$ with $0 \leq t < N$, there exists an index $i$ and a move $p_i \to q_i$ in $G_i$ such that:

\[ \nim(p_1) \oplus \cdots \oplus \nim(q_i) \oplus \cdots \oplus \nim(p_n) = t. \]

This mirrors the Nim strategy of reducing a single heap to achieve the desired nim-sum. The terminal position (where no legal move is available) has Grundy number 0, and all moves from a position with Grundy number 0 must lead to positions with positive Grundy numbers. This establishes that the game is strategically equivalent to playing Nim with heap sizes equal to the Grundy numbers of the component positions.

We recall the following from Chapter 1.

Nim-sum

Let $a = \sum a_k 2^k$ and $b = \sum b_k 2^k$, where $a_k, b_k \in \{0,1\}$ for $k \in \mathbb{N}$, be the binary expansions for nonnegative integers $a$ and $b$ respectively. The nim-sum $a$ and $b$, denoted $a \oplus b$, is given by

\[ a \oplus b = \sum_{k} \left((a_k + b_k) \bmod 2\right) 2^k. \]

This operation is equivalent to bitwise exclusive OR (XOR) and extends to multiple operands associatively.

We now have a framework that allows us to analyze Dawson's Kayles by computing Grundy numbers for various board configurations.

The Winning Strategy

Recall that, initially, the game consists of $n$ tokens arranged in a single row, where players take turns removing exactly two adjacent tokens. This typically splits the row into independent segments, thereby making the disjunctive sum immediately applicable.

Position Decomposition

Let $D(n)$ denote a Dawson's Kayles position with $n$ contiguous pawns. Removing two adjacent pawns at positions $k$ and $k+1$ decomposes the position into a disjunctive sum:

\[ D(n) \rightarrow D(k-1) \oplus D(n-k-1) \quad \text{for } k = 1, 2, \dots, n-1, \]

where $D(0)$ represents the empty position with Grundy number $0$.

Computing Grundy Numbers for Dawson's Kayles

The Grundy numbers for Dawson's Kayles follow the recurrence:

\[ \nim(D(n)) = \text{mex} \left\{ \nim(D(k-1)) \oplus \nim(D(n-k-1)) : k = 1, 2, \dots, n-1 \right\} \]

with base cases $\nim(D(0)) = 0$ and $\nim(D(1)) = 0$ (as removing a single pawn is not a legal move).

The first few values computed via this recurrence are:

\begin{align*} \nim(D(2)) &= \text{mex}\{0 \oplus 0\} = 1 \\ \nim(D(3)) &= \text{mex}\{0 \oplus 0,\ 0 \oplus 0\} = 1 \\ \nim(D(4)) &= \text{mex}\{0 \oplus 1,\ 0 \oplus 0,\ 1 \oplus 0\} = 2 \\ \nim(D(5)) &= \text{mex}\{0 \oplus 1,\ 0 \oplus 1,\ 1 \oplus 0,\ 1 \oplus 0\} = 0 \\ \nim(D(6)) &= \text{mex}\{0 \oplus 2,\ 0 \oplus 1,\ 1 \oplus 1,\ 1 \oplus 0,\ 2 \oplus 0\} = 3 \\ \nim(D(7)) &= \text{mex}\{0 \oplus 0,\ 0 \oplus 2,\ 1 \oplus 1,\ 1 \oplus 1,\ 2 \oplus 0,\ 0 \oplus 0\} = 1 \\ \nim(D(8)) &= \text{mex}\{0 \oplus 3,\ 0 \oplus 0,\ 1 \oplus 1,\ 1 \oplus 1,\ 2 \oplus 1,\ 0 \oplus 0,\ 3 \oplus 0\} = 1 \end{align*}

These values provide the foundation for optimal play. For example, $\nim(D(6)) = 3$ and $\nim(D(4)) = 2$.

Periodicity and Patterns

A remarkable feature of Dawson's Kayles is the eventual periodicity of its Grundy number sequence. The following can be found in [1].

Periodicity of Dawson's Kayles

The Grundy numbers for Dawson's Kayles are eventually periodic with period 34, starting at $n = 52$.

Let $G(n) = \nim(D(n))$. Since moves only affect heaps of size $

\[ G(n) = \text{mex}\{G(i) \oplus G(j) : n \rightarrow (i,j) \text{ via legal move}\}. \]

Let $M$ be the maximum Grundy number observed (empirically $M \leq 3$). Consider the sequence of state vectors $\vec{S}_k = (G(k), G(k+1), \dots, G(k+33))$ for $k \geq 0$, where $\vec{S}_k \in \{0,1,\dots,M\}^{34}$, a finite set of size at most $(M+1)^{34}$.

By the pigeonhole principle, there must exist indices $a < b$ such that $\vec{S}_a = \vec{S}_b$. We show that periodicity begins at $a$ with period $p = b-a$, and proceed with induction on $n \geq a$.

  1. Base: For $n = a, a+1, \dots, a+33$, we have $G(n) = G(n+p)$ by the state vector equality.
  2. Inductive hypothesis: Assume $G(m) = G(m+p)$ for all $m < n$ with $n \geq a+34$. Then \begin{align} G(n+p) &= \text{mex}\{G(i+p) \oplus G(j+p) : \text{moves from } n+p\} \notag \\ &= \text{mex}\{G(i) \oplus G(j) : \text{moves from } n\} \label{eq:secondline} \\ &= G(n) \notag \end{align} where the second equality holds by the inductive hypothesis, as equivalent moves from $n$ and $n+p$ must produce identical nim-sums.

That this occurs with period 34, starting at $n = 52$, is a straightforward computation.

The periodicity enables one to compute winning strategies for arbitrarily large positions, as only a finite number of Grundy numbers are needed.

Winning Strategy Derivation

The winning strategy follows directly from the Sprague-Grundy Theorem:

  1. For a position consisting of multiple contiguous blocks \[ D(n_1) \oplus D(n_2) \oplus \cdots \oplus D(n_k), \] we compute the nim-sum \[ S = \nim(D(n_1)) \oplus \nim(D(n_2)) \oplus \cdots \oplus \nim(D(n_k)). \]
  2. If $S = 0$, the position is a losing one for the player about to move (i.e., a P-position).
  3. If $S \neq 0$, a winning move exists in some block $D(n_i)$ where the player can move to a position $D(m)$ such that \[ \nim(D(m)) = \nim(D(n_i)) \oplus S. \] This ensures the nim-sum becomes $0$.

This demonstrates how Dawson's Kayles reduces to Grundy number calculations via Sprague-Grundy theory.

Example of Play

Consider the position $D(6) \oplus D(4)$. We have $\nim(D(6)) = 3$ and $\nim(D(4)) = 2$, so the nim-sum is $3 \oplus 2 = 1 \neq 0$. This is an N-position, so the next player (let's call her Alice) can win.

Alice needs to find a move in one of the rows that changes the nim-sum to 0. She looks for a move in $D(6)$ that will leave a position with Grundy number $3 \oplus 1 = 2$. One such move is removing tokens 1 and 2 from the $D(6)$ row, which leaves $D(4)$ in that row, and $\nim(D(4)) = 2$. Then the new position is $D(4) \oplus D(4)$ with nim-sum $2 \oplus 2 = 0$, a P-position.

Figure: Example winning move in Dawson's Kayles from position $D(6) \oplus D(4)$.

Game Progression

Let's trace through a complete game sequence:

  1. Initial: $D(6) \oplus D(4)$ with nim-sum $1 \oplus 0 = 1$ (N-position)
  2. Alice's move: Removes tokens 1 and 2 from $D(6)$, leaving $D(4) \oplus D(4)$ with nim-sum $0 \oplus 0 = 0$ (P-position)
  3. Bob's move: From $D(4) \oplus D(4)$, Bob must move in one component. Suppose he removes token 2 from the first $D(4)$ (removing tokens 1-3), leaving $D(1) \oplus D(4)$ with nim-sum $1 \oplus 0 = 1$ (N-position)
  4. Alice's response: Alice computes $\nim(D(1)) = 1$, $\nim(D(4)) = 0$, so $S = 1$. She needs to move to a position with nim-sum 0. She can remove token 1 from $D(1)$ (leaving $D(0)$), resulting in $D(4)$ alone with nim-sum 0.
  5. Final moves: Bob faces $D(4)$ (nimber 0, P-position) and has no winning moves. Whatever he does, Alice can mirror or respond to maintain the winning position.

This example demonstrates how the theoretical framework translates to practical play: computing nim-sums, identifying winning moves through Grundy number manipulation, and executing the winning strategy.

Play Dawson's Kayles in Command Line


#!/bin/bash

# NIM Game in Bash with Machine Learning-inspired difficulty levels

# game state variables
declare -A board
declare -a blocks
declare -a grundy_numbers=(0 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1)
current_player="human"
difficulty="medium"

# function to display the game board
display_board() {
    echo "Current board:"
    
    # display pawns
    for ((i=1; i<=$n; i++)); do
        if [ ${board[$i]} -eq 1 ]; then
            printf " ● "  # filled circle for pawn
        else
            printf "   "  # empty space
        fi
    done
    printf "\n"
    
    # display position numbers beneath
    for ((i=1; i<=$n; i++)); do
        printf " %-2d" $i  # numbers aligned under each position
    done
    printf "\n"
}

# function to calculate nim-sum (XOR of all rows)
calculate_nim_sum() {
    local sum=0
    for pawns in "${blocks[@]}"; do
        sum=$((sum ^ pawns))
    done
    echo $sum
}

# function to get current blocks from the board
get_blocks() {
    blocks=()
    local current_block=0
    
    for ((i=1; i<=n; i++)); do
        if [ ${board[$i]} -eq 1 ]; then
            ((current_block++))
        else
            if [ $current_block -gt 0 ]; then
                blocks+=($current_block)
                current_block=0
            fi
        fi
    done
    
    if [ $current_block -gt 0 ]; then
        blocks+=($current_block)
    fi
}

# function to find optimal move
find_optimal_move() {
    get_blocks
    local nim_sum=$(calculate_nim_sum)
    
    # if nim-sum is 0, any move is losing, so return to random
    if [ $nim_sum -eq 0 ]; then
        echo "random"
        return
    fi
    
    # try to find a move that gives nim-sum 0
    for ((pos=1; pos
[1] Berlekamp, E. R., Conway, J. H., and Guy, R. K. Winning Ways for your Mathematical Plays, volumes 1 and 2. Academic Press, London, 1982.

NIM: The Thief and the Warhead

NIM: The Thief and the Warhead

Jerod Michel, Gao Yucheng
December 2024

"When a prince is brave and powerful, he can make peace reign as and when he wants.
If, however, he has no powers, someone stronger than him will conquer his lands
and rule at his pleasure."

— Vlad Dracul III, Letter to the elders of Brașov, 1456

Description 

Despite its simple rules, Nim is a game of pure logic with a guaranteed winning strategy for one of the players if they play perfectly. The optimal strategy is based on binary digital sums (or, nim-sums). A player in a losing position, then, can win only if their opponent makes a mistake.

In essence, Nim is a foundational game in the field of combinatorial game theory and is a perfect example of a two-player, finite, impartial game with perfect information.

History

The origins of NIM are obscure, but certainly very old, and probably began in China as a game called "捡石头" (Jiǎn shítou). The name "NIM" is also a mystery. It was likely coined by the Harvard mathematician Charles L. Bouton, who was the first to published a mathematical analysis of the game in the Annals of Mathematics in 1901. One theory is that he took it from the archaic English verb nim, meaning "to take" or "to steal".

  • NIMATRON (1940): An electro-mechanical beast built by Westinghouse for the 1940 World's Fair. It was a public spectacle, a "robot" that could play a perfect game. It won 90% of its games against humans, mostly by intimidating them into mistakes—a valid example of psychological warfare augmented by machinery.
  • FERMIAC (1947): Built by physicist Stanislaw Ulam (of H-bomb and Monte Carlo method fame), this was a portable computer designed to simulate neutron transport. But its first public demonstration? Playing and winning a game of NIM. The line between a weapon of science and a game was blurred from the very start.
  • The MANIAC (1952): At Los Alamos National Laboratory—the birthplace of the atomic bomb—the mathematicians and computer scientists needed a way to test the power of their new machine, the MANIAC I. What was one of the very first tasks they programmed? A perfect NIM-playing algorithm.

Rules and Gameplay

  • Setup: The game starts with several rows (or heaps) of objects, such as stones or matches. A common initial setup is that with three rows containing 3, 5, and 7 objects.
  • Gameplay: Players take turns. On a player's turn, they must remove one or more objects from a single row of their choosing. They may take as many objects as they want (from a single object up to the entire row) from this chosen row.
  • Winning: The player who is forced to take the last object loses. (Note that this is the "misère" convention. In the "normal" version, the player who takes the last object wins).

The complete strategy, solved by Charles L. Bouton in 1901, is based on a binary operation called the nim-sum.

The Nim-Sum

The nim-sum of non-negative integers is their addition in base 2 without carry. It is denoted by the symbol '$\oplus$' (XOR, exclusive OR). Every nonnegative integer has a unique binary representation, which allows us to define this operation precisely.

Computing the Nim-sum

To compute the nim-sum of rows of sizes $a$, $b$, $c$, \dots:

  1. Write each number in base 2 (binary), using the unique binary representation of each nonnegative integer.
  2. Align the numbers by their binary digits, padding with leading zeros as needed so all numbers have the same number of digits.
  3. For each column (bit position), perform addition modulo 2: $0 \oplus 0 = 0$, $1 \oplus 0 = 1$, $0 \oplus 1 = 1$, $1 \oplus 1 = 0$.
  4. The resulting binary string is the nim-sum.

Example

Let's compute the nim-sum of rows of size 3, 5, and 7, using their binary representations. We write each number with the same number of digits by padding with leading zeros:

$$\begin{align*} 3 &= 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = (011)_2 \\ 5 &= 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0 = (101)_2 \\ 7 &= 1\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = (111)_2 \\ \text{Nim-sum} &= (001)_2 = 1 \\ \text{Calculation: } & \begin{array}{c@{\,}c@{\,}c@{\,}c} & 0 & 1 & 1 \\ \oplus & 1 & 0 & 1 \\ \oplus & 1 & 1 & 1 \\ \hline & 0 & 0 & 1 \\ \end{array} \end{align*}$$

The nim-sum is 1.

The Winning Strategy

  • A game state is balanced if its nim-sum is $0$.
  • A game state is unbalanced if its nim-sum is not $0$.
  1. If a player is presented with a balanced position ($nim\text{-}sum = 0$), any move they make will necessarily leave an unbalanced position.
  2. If a player is presented with an unbalanced position ($nim\text{-}sum \neq 0$), there always exists at least one move that will leave a balanced position.
  3. The final position (all rows size 0) is balanced ($0 \oplus 0 \oplus \dots \oplus 0 = 0$).

Therefore, the winning strategy is: Always move to leave your opponent with a balanced position.

Let the rows be $a_1, a_2, \dots, a_n$ and let $s = a_1 \oplus a_2 \oplus \dots \oplus a_n$.

Proof of (1): From a balanced position, all moves lead to an unbalanced position.

Suppose $s = 0$. A player's move changes the size of one row, say $a_k$, to a new value $a'_k$ where $a'_k < a_k$. We will show this new position is unbalanced.

Consider the new nim-sum $s' = a_1 \oplus \dots \oplus a'_k \oplus \dots \oplus a_n$.
We know:

$$\begin{align*} s &= 0 = a_1 \oplus \dots \oplus a_k \oplus \dots \oplus a_n \\ \Rightarrow a_k &= a_1 \oplus \dots \oplus a_{k-1} \oplus a_{k+1} \oplus \dots \oplus a_n \end{align*}$$

Now, substitute into the expression for $s'$:

$$\begin{align*} s' &= (a_1 \oplus \dots \oplus a_{k-1} \oplus a_{k+1} \oplus \dots \oplus a_n) \oplus a'_k \\ s' &= a_k \oplus a'_k \end{align*}$$

Since $a'_{k} \neq a_k$, it follows that $a_{k} \oplus a'_k \neq 0$. Therefore, $s' \neq 0$. $\square$

Proof of (2): From an unbalanced position, there exists a move to a balanced position.

Suppose $s \neq 0$. Let $d$ be the position of the most significant (leftmost) 1-bit in the binary representation of $s$.

There must be at least one row, say $a_{k}$, that also has a 1 in bit position $d$ (because if all rows had 0 there, the nim-sum would have 0 in that position).

We choose this row $a_{k}$ to make our move. We will reduce $a_{k}$ to $a'_{k} = a_{k} \oplus s$.

We must verify two things:

  1. This is a valid move: $a'_{k} < a_{k}$.
    The operation $a_{k} \oplus s$ affects bits only from position $d$ downwards. Because $a_{k}$ and $s$ both have a 1 in bit $d$, $a_{k} \oplus s$ will have a 0 in bit $d$. All higher bits remain unchanged. Thus, $a'_k$ is indeed smaller than $a_{k}$.
  2. This move creates a balanced position:
    The new nim-sum $s'$ is: $$\begin{align*} s' &= a_{1} \oplus \dots \oplus a'_{k} \oplus \dots \oplus a_{n} \\ &= a_{1} \oplus \dots \oplus (a_{k} \oplus s) \oplus \dots \oplus a_{n} \\ &= (a_{1} \oplus \dots \oplus a_{k} \oplus \dots \oplus a_{n}) \oplus s \\ &= s \oplus s \\ &= 0 \end{align*}$$ The new position is balanced.
$\square$

Example of Play

Let's play a game with rows as (3, 5, 7). As calculated earlier, $3 \oplus 5 \oplus 7 = 1$. This is an unbalanced position. Player 1 (the winning player) must find a move that makes the nim-sum 0.

They compute for each row:

  • Row 1: $3 \oplus 1 = 2$. (Valid move: remove 1 from row 1 to leave 2).
  • Row 2: $5 \oplus 1 = 4$. (Valid move: remove 1 from row 2 to leave 4).
  • Row 3: $7 \oplus 1 = 6$. (Valid move: remove 1 from row 3 to leave 6).

Player 1 chooses one of these moves, say, taking 1 from row 3, leaving rows as (3, 5, 6). The new nim-sum is $3 \oplus 5 \oplus 6 = 0$, a balanced position for Player 2. From here, whatever Player 2 does, Player 1 can always return the game to a balanced position, eventually taking the last object.

In NIM there is always a linchpin—a single point of failure upon which the entire structure of the game is precariously balanced. The uninitiated see three separate (and possibly dissimilar) rows; the strategist sees a single, hidden device: the nim-sum.

Play Nim in Command Line

In crafting this NIM implementation, we embrace Bash not as a limitation but as a vehicle for clarity. The game states are maintained in simple arrays, where each element represents a row of stones. This minimalist data structure contrasts well with the strategic depth we have coded within the AI routines.

The AI employs the mathematical foundation of combinatorial game theory through the nim-sum calculation (bitwise XOR operations), transforming the game into an elegant exercise in binary arithmetic. For the easy difficulty, random moves simulate those of a novice player, while the medium AI introduces some probabilistic decision-making, occasionally 'forgetting' optimal strategies to create a more human-like opponent. The hard AI fully implements the classic winning algorithm. This implementation demonstrates how, even in a shell scripting environment, we can encode sophisticated game theory concepts that respond intelligently to player input while remaining computationally transparent.

The result is a didactic tool where the reader can trace the exact logic behind each computer move, watching the nim-sum calculations unfold in real time as the AI navigates the game tree according to proven mathematical principles.


#!/bin/bash

# NIM Game in Bash with Machine Learning-inspired difficulty levels

# game state variables
declare -a rows
current_player="human"
difficulty="medium"
learning_rate=0.1  # For medium difficulty "learning" simulation

# function to display the game board
display_board() {
    echo
    echo "=== NIM GAME ==="
    echo "Rows:"
    for i in "${!rows[@]}"; do
        stones=""
        for ((j=0; j<${rows[i]}; j++)); do
            stones+="● "
        done
        echo "Row $((i+1)) [${rows[i]} stones]: $stones"
    done
    echo
}

# function to calculate nim-sum (XOR of all rows)
calculate_nim_sum() {
    local sum=0
    for stones in "${rows[@]}"; do
        sum=$((sum ^ stones))
    done
    echo $sum
}

# function to find the optimal move for hard difficulty
find_optimal_move() {
    local nim_sum=$(calculate_nim_sum)
    local non_one_rows=0
    local rows_with_more_than_one=0
    
    # count rows with more than 1 stone
    for stones in "${rows[@]}"; do
        if [ $stones -gt 1 ]; then
            ((rows_with_more_than_one++))
            ((non_one_rows++))
        elif [ $stones -eq 1 ]; then
            ((non_one_rows++))
        fi
    done
    
    # in misere Nim, strategy differs when all rows are 1 stone
    if [ $rows_with_more_than_one -eq 0 ]; then
        # all rows have 0 or 1 stones - odd number of 1's means take 1, even means take all?
        # actually, in misere with all 1's: odd number of rows -> take 1 to leave even
        local ones_count=0
        for stones in "${rows[@]}"; do
            if [ $stones -eq 1 ]; then
                ((ones_count++))
            fi
        done
        
        if [ $((ones_count % 2)) -eq 1 ]; then
            # edd number of 1's - take 1 to leave even number for opponent
            for i in "${!rows[@]}"; do
                if [ ${rows[i]} -eq 1 ]; then
                    echo "$i 1"
                    return
                fi
            done
        else
            # even number of 1's - take all from first available row
            for i in "${!rows[@]}"; do
                if [ ${rows[i]} -eq 1 ]; then
                    echo "$i 1"
                    return
                fi
            done
        fi
    fi
    
    # if nim-sum is 0, no optimal move exists - take from largest row but leave good position
    if [ $nim_sum -eq 0 ]; then
        # take 1 from the first available row (losing position anyway)
        for i in "${!rows[@]}"; do
            if [ ${rows[i]} -gt 0 ]; then
                echo "$i 1"
                return
            fi
        done
    fi
    
    # find a move that makes nim-sum 0, but avoid leaving bad misère positions
    for i in "${!rows[@]}"; do
        local target=$(( ${rows[i]} ^ $nim_sum ))
        if [ $target -lt ${rows[i]} ]; then
            local take=$(( ${rows[i]} - $target ))
            
            # check if this move leaves only 1-stone rows (dangerous in misere)
            local temp_rows=("${rows[@]}")
            temp_rows[i]=$target
            local remaining_multi_stone=0
            for stones in "${temp_rows[@]}"; do
                if [ $stones -gt 1 ]; then
                    ((remaining_multi_stone++))
                fi
            done
            
            # if this would leave only single stones, make sure we leave odd number
            if [ $remaining_multi_stone -eq 0 ]; then
                local ones_count=0
                for stones in "${temp_rows[@]}"; do
                    if [ $stones -eq 1 ]; then
                        ((ones_count++))
                    fi
                done
                # we want to leave odd number of 1's for opponent in misere
                if [ $((ones_count % 2)) -eq 1 ]; then
                    echo "$i $take"
                    return
                fi
            else
                echo "$i $take"
                return
            fi
        fi
    done
    
    # fallback: take 1 from first available row
    for i in "${!rows[@]}"; do
        if [ ${rows[i]} -gt 0 ]; then
            echo "$i 1"
            return
        fi
    done
}

# function for computer's move
computer_move() {
    echo "Computer's turn..."
    sleep 1
    
    local nim_sum=$(calculate_nim_sum)
    local row_to_take stones_to_take
    
    case $difficulty in
        "easy")
            # random valid move
            while true; do
                local random_row=$(( RANDOM % ${#rows[@]} ))
                if [ ${rows[random_row]} -gt 0 ]; then
                    local max_take=${rows[random_row]}
                    stones_to_take=$(( (RANDOM % max_take) + 1 ))
                    row_to_take=$random_row
                    break
                fi
            done
            ;;
            
        "medium")
            # sometimes optimal, sometimes random (simulating learning)
            local random_choice=$(( RANDOM % 100 ))
            if [ $random_choice -lt 70 ]; then  # 70% chance of optimal move
                read row_to_take stones_to_take <<< $(find_optimal_move)
            else
                # random move
                while true; do
                    local random_row=$(( RANDOM % ${#rows[@]} ))
                    if [ ${rows[random_row]} -gt 0 ]; then
                        local max_take=${rows[random_row]}
                        stones_to_take=$(( (RANDOM % max_take) + 1 ))
                        row_to_take=$random_row
                        break
                    fi
                done
            fi
            ;;
            
        "hard")
            # always optimal move
            read row_to_take stones_to_take <<< $(find_optimal_move)
            ;;
    esac
    
    # execute the move
    rows[row_to_take]=$(( ${rows[row_to_take]} - stones_to_take ))
    echo "Computer takes $stones_to_take stone(s) from row $((row_to_take + 1))"
}

# function for human player's move
human_move() {
    while true; do
        echo "Your turn! Enter row number and stones to take (e.g., '2 3' for row 2, 3 stones):"
        read -p "> " input
        
        # parse input
        local row_num=$(echo $input | awk '{print $1}')
        local take_num=$(echo $input | awk '{print $2}')
        
        # validate input
        if [[ ! "$row_num" =~ ^[1-3]$ ]] || [[ ! "$take_num" =~ ^[0-9]+$ ]]; then
            echo "Invalid input! Please enter: row(1-3) stones(number)"
            continue
        fi
        
        local row_index=$((row_num - 1))
        
        if [ ${rows[row_index]} -eq 0 ]; then
            echo "Row $row_num is empty! Choose another row."
            continue
        fi
        
        if [ $take_num -lt 1 ] || [ $take_num -gt ${rows[row_index]} ]; then
            echo "Invalid number of stones! You can take 1 to ${rows[row_index]} from row $row_num."
            continue
        fi
        
        # valid move - execute it
        rows[row_index]=$(( ${rows[row_index]} - take_num ))
        echo "You take $take_num stone(s) from row $row_num"
        break
    done
}

# function to check if game is over
game_over() {
    local total=0
    for stones in "${rows[@]}"; do
        total=$((total + stones))
    done
    [ $total -eq 1 ]  # game ends when only 1 stone remains
}

# function to get initial game setup
setup_game() {
    echo "Welcome to NIM!"
    echo
    
    # difficulty selection
    while true; do
        echo "Select difficulty:"
        echo "1 - Easy (computer plays randomly)"
        echo "2 - Medium (computer sometimes makes mistakes)"  
        echo "3 - Hard (computer always plays optimally)"
        read -p "Enter choice (1-3): " diff_choice
        
        case $diff_choice in
            1) difficulty="easy"; break ;;
            2) difficulty="medium"; break ;;
            3) difficulty="hard"; break ;;
            *) echo "Invalid choice! Please enter 1, 2, or 3." ;;
        esac
    done
    
    echo "Difficulty set to: $difficulty"
    echo
    
    # row setup
    echo "Set up the initial stones for 3 rows (max 18 stones per row, all different):"
    declare -A used_values
    
    for i in {1..3}; do
        while true; do
            read -p "Stones for row $i (1-18): " stones
            
            if [[ ! "$stones" =~ ^[0-9]+$ ]] || [ $stones -lt 1 ] || [ $stones -gt 18 ]; then
                echo "Please enter a number between 1 and 18."
                continue
            fi
            
            if [ ${used_values[$stones]} ]; then
                echo "This number is already used in another row! Choose a different number."
                continue
            fi
            
            used_values[$stones]=1
            rows[$((i-1))]=$stones
            break
        done
    done
    
    # who goes first (player choice)
    while true; do
    echo
    echo "Who should go first?"
    echo "1 - Player first"
    echo "2 - Computer first" 
    echo "3 - Random"
    read -p "Enter choice (1-3): " first_choice
    
    case $first_choice in
        1) current_player="human"; break ;;
        2) current_player="computer"; break ;;
        3) 
            local random_choice=$(( RANDOM % 2 ))
            if [ $random_choice -eq 0 ]; then
                current_player="human"
            else
                current_player="computer"
            fi
            break 
            ;;
        *) echo "Invalid choice! Please enter 1, 2, or 3." ;;
    esac
done

echo "$current_player will go first!"
}

# main game loop
main() {
    setup_game
    
    while true; do
        display_board
        
        if game_over; then
	    # in normal play, the player who is forced to take the last stone loses
	    if [ "$current_player" = "human" ]; then
		echo "Game over! You took the last stone. Computer wins!"
	    else
		echo "Game over! Computer took the last stone. You win!"
	    fi
	    break
	fi
        
        if [ "$current_player" = "human" ]; then
            human_move
            current_player="computer"
        else
            computer_move
            current_player="human"
        fi
    done
    
    echo
    read -p "Play again? (y/n): " play_again
    if [[ $play_again =~ ^[Yy]$ ]]; then
        exec "$0"  # Restart the script
    else
        echo "Thanks for playing NIM!"
    fi
}

# start the game
main

Tuesday, April 27, 2021

Encrypting and decrypting data with python crypto library (in spyder)


#%%
from cryptography.fernet import Fernet

def write_key():
    """
    Generates a key and save it into a file
    """
    key = Fernet.generate_key()
    with open("key.key", "wb") as key_file:
        key_file.write(key)
        
def load_key():
    """
    Loads the key from the current directory named `key.key`
    """
    return open("key.key", "rb").read()

# generate and write a new key
write_key()

# load the previously generated key
key = load_key()

#%%
message = "Hello World!".encode()

# initialize the Fernet class
f = Fernet(key)

#%%
# encrypt the message
encrypted = f.encrypt(message)

#%%
# print how it looks
print(encrypted)

#%%
decrypted_encrypted = f.decrypt(encrypted)
print(decrypted_encrypted)
#%%
Build a simple message encoder:

from cryptography.fernet import Fernet

def write_key():
    """
    This generates a key and saves it into a file
    """
    key = Fernet.generate_key()
    with open("key.key", "wb") as key_file:
        key_file.write(key)
        
def load_key():
    """
    This loads the key from the current directory named `key.key`
    """
    return open("key.key", "rb").read()

def encrypt_message(message):
    """
    Encrypts a message
    """
    key = load_key()
    encoded_message = message.encode()
    f = Fernet(key)
    encrypted_message = f.encrypt(encoded_message)

    print(encrypted_message)

if __name__ == "__main__":
    encrypt_message("message to encrypt")


Output:
b'gAAAAABgh68zeqW0pQgDTZlZs-1ezzDCAHkz5SnPYKuFIrLJ8bgwHuZoJONFMShSBKLP1Xh5cjf9wLB_TbluMQ1MNRpNDs5n7UlSVa7obfaHtfCnc_FWuzA='
Build a simple decoder:

from cryptography.fernet import Fernet

def load_key():
    """
    This loads the key from the current directory named `key.key`
    """
    return open("key.key", "rb").read()

def decrypt_message(encrypted_message):
    """
    Decrypts an encrypted message
    """
    key = load_key()
    f = Fernet(key)
    decrypted_message = f.decrypt(encrypted_message)

    print(decrypted_message.decode())

if __name__ == "__main__":
    decrypt_message(b'gAAAAABgh68zeqW0pQgDTZlZs-1ezzDCAHkz5SnPYKuFIrLJ8bgwHuZoJONFMShSBKLP1Xh5cjf9wLB_TbluMQ1MNRpNDs5n7UlSVa7obfaHtfCnc_FWuzA=')


Output:
message to encrypt

CSV phonebook program with simple ui menu in python


import os
import csv


phones = []
name_pos = 0
phone_pos = 1
phone_header = [ 'Name', 'Phone Number']

def proper_menu_choice(which): # decides whether input is a member of phones
    if not which.isdigit():
        print ("'" + which + "' needs to be the number of a phone!")
        return False
    which = int(which)
    if which < 1 or which > len(phones):
        print ("'" + str(which) + "' needs to be the number of a phone!")
        return False
    return True
    
def delete_phone(which): # deletes a member of phones
    if not proper_menu_choice(which):
        return
    which = int(which)

    del phones[which-1]
    print( "Deleted phone #", which)

def edit_phone(which): # allows to edit a member of phones
    if not proper_menu_choice(which):
        return
    which = int(which)
        
    phone = phones[which-1]
    print("Enter the data for a new phone. Press  to leave unchanged.")
    
    print(phone[name_pos])
    newname = input("Enter phone name to change or press return: ")
    if newname == "":
        newname = phone[name_pos]
        
    print(phone[phone_pos])    
    newphone_num = input("Enter new phone number to change or press return: ")
    if newphone_num == "":
        newphone_num = phone[phone_pos]
            
    phone = [newname, newphone_num]
    phones[which-1] = phone

  
def save_phone_list(): # writes members of phones to csv file

    f = open("myphones.csv", 'w', newline='')
    for item in phones:
        csv.writer(f).writerow(item)
    f.close()
  
def load_phone_list(): # creates phones list from csv file
    if os.access("myphones.csv",os.F_OK):
        f = open("myphones.csv")
        for row in csv.reader(f):
            phones.append(row)
        f.close()

def show_phones(): # prints contents of phones list
    show_phone(phone_header, "")
    index = 1
    for phone in phones:
        show_phone(phone, index)
        index = index + 1
    print()

def show_phone(phone, index): # formats the output of show_phones(), above
    outputstr = "{0:>3}  {1:<20}  {2:>16}"
    print(outputstr.format(index, phone[name_pos], phone[phone_pos]))

def create_phone(): # appends new name/number to phones list
    print("Enter the data for a new phone:")
    newname = input("Enter name: ")
    newphone_num = input("Enter phone number: ")
    phone = [newname,newphone_num]
    phones.append(phone)
    
def menu_choice(): # simple ui menu
    """ Find out what the user wants to do next. """
    print("Choose one of the following options?")
    print("   s) Show")
    print("   n) New")
    print("   d) Delete")
    print("   e) Edit")
    print("   r) Reorder")
    print("   q) Quit")
    choice = input("Choice: ")    
    if choice.lower() in ['n','d', 's','e', 'r', 'q']:
        return choice.lower()
    else:
        print(choice +"?")
        print("Invalid option")
        return None
    
def reorder_phones():
    global phones       # this insures that we use the one at the top
    phones.sort() # replace this pass (a do-nothing) statement with your code


def main_loop():
    
    load_phone_list()
    
    while True:
        choice = menu_choice()
        if choice == None:
            continue
        if choice == 'q':
            print( "Exiting...")
            break     # jump out of while loop
        elif choice == 'n':
            create_phone()
        elif choice == 'd':
            which = input("Which item do you want to delete? ")
            print("which is ", which)
            delete_phone(which)
        elif choice == 's':
            show_phones()
        elif choice == 'e':
            which = input("Which item do you want to edit? ")
            print("which is ", which)
            edit_phone(which)
        elif choice == 'r':
            reorder_phones()
        else:
            print("Invalid choice.")
            
    save_phone_list()
    

# The following makes this program start running at main_loop() 
# when executed as a stand-alone program.    
if __name__ == '__main__':
    main_loop()

Wednesday, December 4, 2019

A LISP/SCHEME interpreter in python (modeled after that from norvig.com, but for python rather than python3)
 
import math
import operator as op

Symbol = str              # a symbol in scheme is a python string
Number = (int, float)     # a number in scheme is a python int or float
Atom   = (Symbol, Number) # an atom in scheme is a symbol or number
List   = list             # a list in scheme is a list in python
Exp    = (Atom, List)     # an expression is an atom or list
Env    = dict             # A Scheme environment (defined below) 
                          # is a mapping of {variable: value}

def Tokenize(char):
    return char.replace('(', ' ( ').replace(')', ' ) ').split() # Tokenizer

program="(begin (define r 10) (* pi (* r r)))"

def Parse(program):
    return ReadTokens(Tokenize(program)) # Parser

def Atom(token):
    try: return int(token)
    except ValueError:
        try: return float(token)
        except ValueError:
            return Symbol(token) # Atomizer

def ReadTokens(tokens):
    if len(tokens) == 0:
        print("SyntaxError: unexpected EOF")
    token = tokens.pop(0)
    if token == '(':
        L = []
        while tokens[0] != ')':
            L.append(ReadTokens(tokens))
        tokens.pop(0)
        return L
    elif token == ')':
        print("unexpected ')'")
    else:
        return Atom(token) # put tokens one by one into list

def pprint(param):
    print(param) # implement python print as a function

def standard_env():
    env = Env()
    env.update(vars(math)) # sin, cos, sqrt, pi, ...
    env.update({
        '+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv,
        '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq,
        'abs':     abs,
        'append':  op.add,
        'apply':   lambda proc, args: proc(*args),
        'begin':   lambda *x: x[-1],
        'car':     lambda x: x[0],
        'cdr':     lambda x: x[1:],
        'cons':    lambda x,y: [x] + y,
        'eq?':     op.is_,
        'expt':    pow,
        'equal?':  op.eq,
        'length':  len,
        'list':    lambda *x: List(x),
        'list?':   lambda x: isinstance(x, List),
        'map':     map,
        'max':     max,
        'min':     min,
        'not':     op.not_,
        'null?':   lambda x: x == [],
        'number?': lambda x: isinstance(x, Number),
        'print':   pprint,
        'procedure?': callable,
        'round':   round,
        'symbol?': lambda x: isinstance(x, Symbol),
    })
    return env # main translater (from python to lisp)

global_env = standard_env()
env=global_env

def eval(x):
    if isinstance(x, Symbol):        # variable reference
        return env[x]
    elif isinstance(x, Number):      # constant number
        return x                
    elif x[0] == 'if':               # conditional
        (_, test, conseq, alt) = x
        exp = (conseq if eval(test, env) else alt)
        return eval(exp)
    elif x[0] == 'define':           # definition
        (_, symbol, exp) = x
        env[symbol] = eval(exp)
    else:                            # procedure call
        proc = eval(x[0])
        args = [eval(arg) for arg in x[1:]]
        return proc(*args)

def Schemestr(exp):
    if isinstance(exp, List):
        return '(' + ' '.join(map(Schemestr, exp)) + ')' 
    else:
        return str(exp) # enter scheme expressions into this function

def repl(prompt='lis.py> '):
    while True:
        val = eval(Parse(raw_input(prompt)))
        if val is not None: 
            print(Schemestr(val)) # prompt


Sunday, August 13, 2017

Searching for incidence structures in certain nonAbelian groups with MAGMA

The following code searches for incidence structures in the nonAbelian groups \(\mathbb{F}_{p^{2}}\times H\) where \(H\) is the integers modulo \(p+1\). We first define several functions.
 Bin_op:=function(p,x,y)   //defines a binary operation on a cartesian product
    return <x[1]+y[1]^(p^(Integers() ! y[2])),x[2]+y[2]>;
end function;

Op_inv:=function(p,x)    //defines the inverse wrt above binary operation
    return <(-x[1])^(p^(Integers() ! -x[2])),-x[2]>;
end function;

nPow:=function(a,n,p)   //defines nth power wrt above binary operation
    i:=0;
    x:=a;
    while i lt n+1 do
        x:=Bin_op(p,x,a);
        i:=i+1;
    end while;
    return x;
end function;

Trans_bin:=function(A,p,x)  //creates translation by x of set of elements wrt above binary op
    X:={};
    for a in A do
        Include(~X,Bin_op(p,x,a));
    end for;
    return X;
end function;

Build_S:=function(G,p,s)   //builds set of elements of form <h,0> where h is in GF(p,s)
    H:=Set(GF(p,s));
    X:={G|};
    for h in H do
        Include(~X,<h,0>);
    end for;
    return X;
end function;

Build_splint:=function(p,W)  //builds set of 1-dim subgroups of W
    X:={@ @};
    for w in W diff {<0,0>} do
        Y:={w};
        for i in {0..p-1} do
            Include(~Y,nPow(w,i,p));
        end for;
        Include(~X,Y);
    end for;
    return X;
end function;

Build_flesh:=function(p,A)   //collects members of form x*y where x,y are in A and puts them in a set
    X:=A;
    for x,y in X do
        Include(~X,Bin_op(p,x,y));
    end for;
    return X;
end function;

fleshPow:=function(p,A,n)   //builds subgroup generated by members of A
    i:=0;
    X:=A;
    while i lt n+1 do
        X:=Build_flesh(p,X);
        i:=i+1;
    end while;
    return X;
end function;

Build_splint0:=function(p,W,k)  //builds set of subgroups of W of order p^k
    X:={@ @};
    for A in Subsets(W diff {<0,0<},k) do
        Y:=A;
        while # Y lt # Build_flesh(p,Y) do
            Y:=Build_flesh(p,Y);
        end while;
        if # Y eq p^k then
            Include(~X,Y);
        end if;
    end for;
    return X;
end function;

Build_cos_reps:=function(G,Subgrp,p)  //builds set of coset reps of a subgroup of G
    X:={};
    Y:={};
    for g in G do
        W:={};
        for g1 in Subgrp do
            Include(~W,Bin_op(p,g,g1));
        end for;
        if W notin X then
            Include(~X,W);
            Include(~Y,g);
        end if;
    end for;
    return SetToIndexedSet(Y);
end function;

Build_diff:=function(G,p,s)   //builds incidence structure which is union of differences of subgroups of G
    S:=Build_S(G,p,s);
    Spl:=Build_splint0(p,S,s-1);
    X:=Build_cos_reps(G,S,p);
    Y:={};
    for i in {1..# X} do
        Y:=Y join Trans_bin(S diff Spl[i],p,X[i]);
    end for;
    return Y;
end function;

Build_diff0:=function(G,p,s,W,m)  //variation of above union
    S:=Build_S(G,p,s);
    Spl:=W;
    X:=Build_cos_reps(G,S,p);
    Y:={};
    for i in {1..m} do
        Y:=Y join Trans_bin(S diff Spl[i],p,X[i]);
    end for;
    for i in {m+1..# X} do
        Y:=Y join Trans_bin(Spl[i],p,X[i]);
    end for;
    return Y;
end function;


Multi:=function(p,G,U)   //builds multiset {u1-u2 | u1,u2 are in U and u1 not equal to u2}
    X:={* *};
    for u1,u2 in U do
        if u1 ne u2 then
            Include(~X,Bin_op(p,u1,Op_inv(p,u2)));
        end if;
    end for;
    return X;
end function;

Check_multi:=function(p,G,U)  //checks multiplicites of members of multiset and puts them into a set
    X:={};
    for g in G diff {G ! <0,0<} do
        Include(~X,Multiplicity(Multi(p,G,U),g));
    end for;
    return X;
end function;

Check_multi0:=function(p,G,U)  //variation of above function that keeps track of whether the cayley graph is an srg
    X:={};
    Y:={};
    for u in U do
        Include(~X,Multiplicity(Multi(p,G,U),u));
    end for;
    for u in Set(G) diff (U join {<0,0<}) do
        Include(~Y,Multiplicity(Multi(p,G,U),u)); 
    end for;
    return [* X, Y *];
end function;
Here we check whether the set union obtained with \(p=7\) and \(s=2\) is a difference set.
 p:=7;   //finds almost differecne set in the nonabelian group G=GF(p,s)xC where C is integers modulo p+1
s:=2;
H1:=Set(GF(p,s));
r:=(p^s-1)/(p-1);
r:=Integers() ! r;
H2:=Set(Integers(r));
G:=Set(CartesianProduct(H1,H2));
S:=Build_S(G,p,s);
Spl:=Build_splint0(p,S,s-1);
X:=Build_cos_reps(G,S,p);
for m in {5..# X} do
U:=Build_diff0(G,p,s,Spl,m);
print "m=",m;
Check_multi(p,G,U);
end for;

Searching for 1 1/2 designs in cyclic codes with MAGMA

Here we try to find 1 1/2-designs in cyclic codes. 1 1/2-designs are interesting since they correspond to directed strongly regular graphs.
 D := function(d,p,n)        //creates set of dth power residues in GF(p,n)
    x := PrimitiveElement(GF(p,n))^d;
    DD := {GF(p,n)|};
    for i in {0..p^n-1} do
        Include(~DD,x^i);
    end for;
    return DD;
end function;
Di := function(d,p,n,i)     //creates ith class of dth power residues in GF(p,n)
    x := PrimitiveElement(GF(p,n))^i;
    return {GF(p,n)|x*a:a in D(d,p,n)};
end function;

C_union := function(A,d,p,n)  //creates union of cyclotomic classes over set A of indices
    X := {};
    for i in A do
        X := X join Di(d,p,n,i);
    end for;
    return X;
end function;

cTrans:=function(C,i)   //creates additive translate of union by i of dth power power residues
    X:={};
    for c in C do
        Include(~X,c+i);
    end for;
    return X;
end function;

CycBuild:=function(D,N,k,q)  //builds cyclic code of length N with D as defining set
    G:=ZeroMatrix(GF(q),k,N);
    for i in {1..k} do
        for j in {1..N} do
            if j-1 in cTrans(D,i-1,N) then
                G[i,j]:=1;
            else
                G[i,j]:=0;
            end if;
        end for;
    end for;
    return G;
end function;

ZeroCols:=function(G)   //creates set of zero columns of matrix
    X:={};
    for j in {1..NumberOfColumns(G)} do
        if Transpose(G)[j] eq ZeroMatrix(GF(2),1,NumberOfRows(G)) then
            Include(~X,j);
        end if;
    end for;
    return # X;
end function;

Build_supps:=function(C,l)   //collects supports of words in code into set
    X:={};
    for c in Words(C,l) do
        Include(~X,Support(c));
    end for;
    return X;
end function;

Check_ades:=function(b0,B,t); //check replication number of incidence structure
    X:={};
    for Y in Subsets(b0,t) do
        Z:={};
        for b in B do
            if Y subset b then
                Include(~Z,b);
            end if;
        end for;
        Include(~X,# Z);
    end for;
    return X;
end function;

Check_112:=function(F,B)  //checks whether incidence structure is a 1 1/2 design
    U:={};
    V:={};
    for x in F do
        for b in B do
            X:={};
            Y:={};
            for y in (b diff {x}) do
                for c in (B diff {b}) do
                    if y in c and x in c then
                        if x in b then
                            Include(~X,);
                        else
                            Include(~Y,);
                        end if;
                    end if;
                end for;
            end for;
            if x in b then
                Include(~U,# X);
            else
                Include(~V,# Y);
            end if;
        end for;
    end for;
    return [* U, V *];
end function;\
Here we carry out a search.
 d:=2;           //searches for 1 1/2 designs in codes
n:=1;
q:=2;
for p in {5..201} do
    if IsPrime(p) then
        if p^n mod d eq 1 then
            G:=Set(GF(p,n));
            for A in Subsets({0..d-1},1) do
                for k in {p} do
                    C:=LinearCode(CycBuild(C_union(A,d,p,n),p,k,q));
                    for l in {3..p} do
                        B:=Build_supps(C,l);
                        if B ne {} then
                            if # Check_112(G,B)[1] eq 1 and # Check_112(G,B)[2] eq 1 and {Check_112(G,B)[1],Check_112(G,B)[2]} ne {{0},{0}} then
                                print C,A,p,k,l,Check_112(G,B),Check_ades(G,B,1),Check_ades(G,B,2),ZeroCols(CycBuild(C_union(A,d,p,n),p,k,q));
                            end if;
                        end if;
                    end for;
                end for;
            end for;
        end if;
    end if;
end for;

Linguistics and Information Theory