Bitwise Operators

version 1 by Bart Massey

  • Home page
  • Beginning
  • Previous



  • Example: ** Nimrod - Using bitwise XOR to play Nim

    The game of Nim is a skill game in which players take turns taking stones from any one of a number pits until some player wins by taking the last stone. It turns out that a strategy involving XOR is optimal for this game. It is possible to play this strategy in your head, and easy for a computer to play it. Since Nimrod lets the player go first, it is possible for the player to force a win; if the player makes any mistakes, however, the player will lose.

        "Nimrod" by "Bart Massey".
        
        Include Bitwise Operators by Bart Massey.
        
        The maximum score is 1.
        
        There is a room called The Game Room. "An ancient, pitted Nim Table dominates the center of the room. Behind the table, seated in a high-backed chair, is the legendary Nim champion Nimrod. You, it appears, may stand."
        
        A high-backed chair is a scenery supporter in The Game Room. The description is "This chair is carved from ashen granite."
        
        A nim table is a scenery supporter in The Game Room. The description is "This table is waist-high, and has three pits for stones. [The description of pit one] [The description of pit two] [The description of pit three]".
        
        Nimrod is a scenery man on the high-backed chair. The description is "Nimrod is pale, dark-haired and inscrutable."
        
        [ We build a bunch of auxiliary machinery to support the algorithm. ]
        
        To say (n - a number) stones: if n is 0, say "nothing"; if n is 1, say "one stone"; if n is greater than 1, say "[n] stones".
        
        A pit is a kind of thing. Every pit has a number called the stone count. The description of a pit is "[The item described] contains [the stone count of the item described stones]."
        
        A pit called pit one is part of the nim table. The stone count of it is 3. Understand "pit 1" as pit one.
        
        A pit called pit two is part of the nim table. The stone count of it is 5. Understand "pit 2" as pit two.
        
        A pit called pit three is part of the nim table. The stone count of it is 7. Understand "pit 3" as pit three.
        
        Taking it stones from is an action applying to one value and one visible thing and requiring light. Understand "take [number] stone/stones/-- from [pit]" as taking it stones from.
        
        Check taking a number (called n) stones from a pit (called p): let np be the stone count of p; if n > np, say "Your reach exceeds your grasp. Too many stones? The wrong pit? Just confused? Who can say?" instead; if n < 1, say "Clever...but also illegal. Nimrod glares mercilessly at you as you pull your hand back." instead.
        
        Carry out taking a number (called n) stones from a pit (called p): now the stone count of p is the stone count of p - n; say "You feel [n stones] magically fade away at your touch. [The p] now contains [the stone count of p stones]."; try Nimrod moving.
        
        Carry out Nimrod taking a number (called n) stones from a pit (called p): now the stone count of p is the stone count of p - n; say "Nimrod deftly erases [n stones] from [p], leaving [the stone count of p stones]."
        
        Moving is an action applying to nothing.
        
        Definition: A pit is nonempty if the stone count of it is greater than 0.
        
        To decide whether the table is empty: let l be the list of nonempty pits; if the number of entries of l is 0, yes; otherwise no.
        
        [ Finally (finally!) the actual game mechanic is fairly simple.]
        
        Check Nimrod moving when the table is empty: say "Nimrod stares sadly at the empty pits. He hangs his head in shame. He has been defeated."; now the score is 1; end the story.
        
        Report Nimrod moving when the table is empty: say "Nimrod's eyes flash in triumph as he completes his victory."; end the story.
        
        Carry out Nimrod moving:
            say "Nimrod ponders the situation ponderously...[line break]";
            let q be 0;
            repeat with p running through the list of nonempty pits:
                let n be the stone count of p;
                let q be q bit-xor n;
            repeat with p running through the list of nonempty pits:
                let n be the stone count of p;
                let r be q bit-xor n;
                if n > r:
                    let t be n - r;
                    try Nimrod taking t stones from p instead;
            let m be pit one;
            repeat with p running through the list of nonempty pits:
                let nm be the stone count of m;
                let np be the stone count of p;
                if np > nm:
                    now m is p;
            try Nimrod taking 1 stones from m.
        
        Test winning with "take 1 stone from pit 1 / take 1 stone from pit 2 / take 1 stone from pit 1 / take 1 stone from pit 1 / take 1 stone from pit 3 / take 1 stone from pit 3 / take 1 stone from pit 3 / take 1 stone from pit 3".
        
        Test losing with "take 3 stones from pit 1 / take 4 stones from pit 3 / take 1 stone from pit 2".
        
        Test me with "test losing".

    The name "Nimrod" is a Biblical name meaning "Mighty Hunter".