Combinatorial Game Theory | Set 2 ( Game of Nim ) | A C ++ program to implement Game of Nim . The program assumes that both players are playing optimally ; A Structure to hold the two parameters of a moveA move has two parameters - 1 ) pile_index = The index of pile from which stone is going to be removed2 ) stones_removed = Number of stones removed from the pile indexed = pile_index ; A C function to output the current game state . ; A C function that returns True if game has ended and False if game is not yet over ; A C function to declare the winner of the game ; A C function to calculate the Nim - Sum at any point of the game . ; A C function to make moves of the Nim Game ; The player having the current turn is on a winning position . So he / she / it play optimally and tries to make Nim - Sum as 0 ; If this is not an illegal move then make this move . ; If you want to input yourself then remove the rand ( ) functions and modify the code to take inputs . But remember , you still won 't be able to change your  fate/prediction. ; Create an array to hold indices of non - empty piles ; A C function to play the Game of Nim ; Driver program to test above functions ; Test Case 1 ; We will predict the results before playing The COMPUTER starts first ; Let us play the game with COMPUTER starting first and check whether our prediction was right or not ; Test Case 2 int piles [ ] = { 3 , 4 , 7 } ; int n = sizeof ( piles ) / sizeof ( piles [ 0 ] ) ; We will predict the results before playing The HUMAN ( You ) starts first ; Let us play the game with COMPUTER starting first and check whether our prediction was right or not playGame ( piles , n , HUMAN ) ;
#include <iostream> NEW_LINE #include <math.h> NEW_LINE using namespace std ; #define COMPUTER  1 NEW_LINE #define HUMAN  2 NEW_LINE struct move { int pile_index ; int stones_removed ; } ; void showPiles ( int piles [ ] , int n ) { int i ; cout << " Current ▁ Game ▁ Status ▁ - > ▁ " ; for ( i = 0 ; i < n ; i ++ ) cout << " ▁ " << piles [ i ] ; cout << " STRNEWLINE " ; return ; } bool gameOver ( int piles [ ] , int n ) { int i ; for ( i = 0 ; i < n ; i ++ ) if ( piles [ i ] != 0 ) return ( false ) ; return ( true ) ; } void declareWinner ( int whoseTurn ) { if ( whoseTurn == COMPUTER ) cout << " HUMAN won " else cout << " COMPUTER won " return ; } int calculateNimSum ( int piles [ ] , int n ) { int i , nimsum = piles [ 0 ] ; for ( i = 1 ; i < n ; i ++ ) nimsum = nimsum ^ piles [ i ] ; return ( nimsum ) ; } void makeMove ( int piles [ ] , int n , struct move * moves ) { int i , nim_sum = calculateNimSum ( piles , n ) ; if ( nim_sum != 0 ) { for ( i = 0 ; i < n ; i ++ ) { if ( ( piles [ i ] ^ nim_sum ) < piles [ i ] ) { ( * moves ) . pile_index = i ; ( * moves ) . stones_removed = piles [ i ] - ( piles [ i ] ^ nim_sum ) ; piles [ i ] = ( piles [ i ] ^ nim_sum ) ; break ; } } } else { int non_zero_indices [ n ] , count ; for ( i = 0 , count = 0 ; i < n ; i ++ ) if ( piles [ i ] > 0 ) non_zero_indices [ count ++ ] = i ; ( * moves ) . pile_index = ( rand ( ) % ( count ) ) ; ( * moves ) . stones_removed = 1 + ( rand ( ) % ( piles [ ( * moves ) . pile_index ] ) ) ; piles [ ( * moves ) . pile_index ] = piles [ ( * moves ) . pile_index ] - ( * moves ) . stones_removed ; if ( piles [ ( * moves ) . pile_index ] < 0 ) piles [ ( * moves ) . pile_index ] = 0 ; } return ; } void playGame ( int piles [ ] , int n , int whoseTurn ) { cout << " GAME STARTS " struct move moves ; while ( gameOver ( piles , n ) == false ) { showPiles ( piles , n ) ; makeMove ( piles , n , & moves ) ; if ( whoseTurn == COMPUTER ) { cout << " COMPUTER ▁ removes " << moves . stones_removed << " stones ▁ from ▁ pile ▁ at ▁ index ▁ " << moves . pile_index << endl ; whoseTurn = HUMAN ; } else { cout << " HUMAN ▁ removes " << moves . stones_removed << " stones ▁ from ▁ pile ▁ at ▁ index ▁ " << moves . pile_index << endl ; whoseTurn = COMPUTER ; } } showPiles ( piles , n ) ; declareWinner ( whoseTurn ) ; return ; } void knowWinnerBeforePlaying ( int piles [ ] , int n , int whoseTurn ) { cout << " Prediction ▁ before ▁ playing ▁ the ▁ game ▁ - > ▁ " ; if ( calculateNimSum ( piles , n ) != 0 ) { if ( whoseTurn == COMPUTER ) cout << " COMPUTER ▁ will ▁ win STRNEWLINE " ; else cout << " HUMAN ▁ will ▁ win STRNEWLINE " ; } else { if ( whoseTurn == COMPUTER ) cout << " HUMAN ▁ will ▁ win STRNEWLINE " ; else cout << " COMPUTER ▁ will ▁ win STRNEWLINE " ; } return ; } int main ( ) { int piles [ ] = { 3 , 4 , 5 } ; int n = sizeof ( piles ) / sizeof ( piles [ 0 ] ) ; knowWinnerBeforePlaying ( piles , n , COMPUTER ) ; playGame ( piles , n , COMPUTER ) ; knowWinnerBeforePlaying ( piles , n , COMPUTER ) ; return ( 0 ) ; }