Recomendamos encarecidamente consultar el siguiente artículo como requisito previo para ello. Teoría de juegos combinatorios | Conjunto 1 (Introducción) En esta publicación, se analiza Game of Nim. El Juego de Nim se describe mediante las siguientes reglas: “ Dado un número de pilas en las que cada pila contiene una cierta cantidad de piedras/monedas. En cada turno, un jugador puede elegir solo una pila y quitar cualquier cantidad de piedras (al menos una) de esa pila. Se considera que el jugador que no puede moverse pierde el juego (es decir, el que toma la última piedra es el ganador). Por ejemplo, considere que hay dos jugadores , A y B , e inicialmente hay tres montones de monedas que inicialmente tienen 3, 4, 5monedas en cada uno de ellos como se muestra a continuación. Suponemos que el primer movimiento lo hace A. Consulte la siguiente figura para una comprensión clara de todo el juego. 
Entonces, ¿ A tenía una gran experiencia en este juego? o él/ella estaba teniendo alguna ventaja sobre B al comenzar primero? Ahora juguemos de nuevo, con la misma configuración de las pilas que arriba, pero esta vez B comenzando primero en lugar de A. Por la figura anterior, debe quedar claro que el juego depende de un factor importante: ¿Quién comienza el juego primero? Entonces, ¿el jugador que comienza primero ganará siempre? Volvamos a jugar el juego, comenzando desde A
, y esta vez con una configuración inicial de pilotes diferente. Las pilas tienen 1, 4, 5 monedas inicialmente. ¿Ganará A nuevamente ya que comenzó primero? Dejanos ver. 
Entonces, el resultado es claro. A ha perdido. ¿Pero cómo? Sabemos que este juego depende en gran medida de qué jugador comienza primero. Por lo tanto, debe haber otro factor que domine el resultado de este juego simple pero interesante. Ese factor es la configuración inicial de los montones/pilas. Esta vez la configuración inicial era diferente a la anterior. Entonces, podemos concluir que este juego depende de dos factores:
- El jugador que empieza primero.
- La configuración inicial de las pilas/montones.
De hecho, ¡podemos predecir el ganador del juego incluso antes de jugarlo! Nim-Sum: El valor XOR acumulativo del número de monedas/piedras en cada pila/montón en cualquier punto del juego se llama Nim-Sum en ese punto. “Si tanto A como B juegan de manera óptima (es decir, no cometen ningún error), entonces el jugador que comienza primero tiene la garantía de ganar si el Nim-Sum al comienzo del juego es distinto de cero. De lo contrario, si Nim-Sum se evalúa como cero, entonces el jugador A definitivamente perderá”. Para la prueba del teorema anterior, consulte- https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula
Estrategia óptima:
- Si la suma XOR de ‘n’ números ya es cero, entonces no hay posibilidad de hacer que la suma XOR sea cero mediante una sola reducción de un número.
- Si la suma XOR de ‘n’ números no es cero, entonces hay al menos un único enfoque por el cual si reduce un número, la suma XOR es cero.
Inicialmente podrían existir dos casos. Caso 1: Nim Sum inicial es cero Como sabemos, en este caso, si se juega de manera óptima , B gana, lo que significa que B siempre preferiría tener Nim sum igual a cero para el turno de A. Entonces, como el Nim Sum es inicialmente cero, cualquier número de elementos que A elimine del nuevo Nim Sum sería distinto de cero (como se mencionó anteriormente). Además, como B preferiría una Nim Sum igual a cero para el turno de A , entonces jugaría un movimiento para hacer que la Nim Sum fuera cero nuevamente (lo cual siempre es posible, como se mencionó anteriormente). El juego se ejecutará siempre que haya elementos en cualquiera de los montones y en cada uno de sus respectivos turnos A haría que Nim sum sea distinto de cero y Bvolvería a ser cero y, finalmente, no quedarán elementos y B será el último en elegir y gana el juego. Es evidente por la explicación anterior que la estrategia óptima para cada jugador es hacer que el Nim Sum para su oponente sea cero en cada uno de sus turnos, lo que no será posible si ya es cero. Caso 2: Nim Sum inicial no es cero Ahora, siguiendo el enfoque óptimo A , Nim Sum sería cero ahora (lo cual es posible ya que la Nim sum inicial no es cero, como se mencionó anteriormente). Ahora, en el turno de B , dado que la suma mínima ya es cero, sea cual sea el número que elija B , la suma mínima sería distinta de cero y Apuede elegir un número para hacer que la suma nim sea cero nuevamente. Esto irá siempre que haya elementos disponibles en cualquier pila. Y A será el que elija el último artículo. Entonces, como se discutió en los casos anteriores, debería ser obvio ahora que la estrategia óptima para cualquier jugador es hacer que la suma mínima sea cero si no es cero y si ya es cero, cualquier movimiento que haga el jugador ahora, puede ser contrarrestado. .
Apliquemos el teorema anterior en los juegos jugados anteriormente. En el primer juego, A comenzó primero y el Nim-Sum al comienzo del juego fue 3 XOR 4 XOR 5 = 2, que es un valor distinto de cero y, por lo tanto, A ganó. Mientras que en el segundo juego, cuando la configuración inicial de las pilas era 1, 4 y 5 y A comenzaba primero, entonces A estaba destinado a perder ya que el Nim-Sum al comienzo del juego era 1 XOR 4 XOR 5 = 0 .
Implementación:
En el programa a continuación, jugamos el Nim-Game entre la computadora y el humano (usuario) El programa a continuación usa dos funciones knowWinnerBeforePlaying() : : Indica el resultado antes de jugar. playGame() : juega el juego completo y finalmente declara al ganador. La función playGame() no toma información del humano (usuario), sino que utiliza una función rand() para recoger aleatoriamente una pila y eliminar aleatoriamente cualquier cantidad de piedras de la pila seleccionada. El siguiente programa se puede modificar para recibir información del usuario eliminando la función rand() e insertando funciones cin o scanf().
C++
/* A C++ program to implement Game of Nim. The program
assumes that both players are playing optimally */
#include <iostream>
#include <math.h>
using namespace std;
#define COMPUTER 1
#define HUMAN 2
/* A Structure to hold the two parameters of a move
A move has two parameters-
1) pile_index = The index of pile from which stone is
going to be removed
2) stones_removed = Number of stones removed from the
pile indexed = pile_index */
struct move
{
int pile_index;
int stones_removed;
};
/*
piles[] -> Array having the initial count of stones/coins
in each piles before the game has started.
n -> Number of piles
The piles[] are having 0-based indexing*/
// A C function to output the current game state.
void showPiles (int piles[], int n)
{
int i;
cout <<"Current Game Status -> ";
for (i=0; i<n; i++)
cout << " " << piles[i];
cout <<"\n";
return;
}
// A C function that returns True if game has ended and
// False if game is not yet over
bool gameOver(int piles[], int n)
{
int i;
for (i=0; i<n; i++)
if (piles[i]!=0)
return (false);
return (true);
}
// A C function to declare the winner of the game
void declareWinner(int whoseTurn)
{
if (whoseTurn == COMPUTER)
cout <<"\nHUMAN won\n\n";
else
cout <<"\nCOMPUTER won\n\n";
return;
}
// A C function to calculate the Nim-Sum at any point
// of the game.
int calculateNimSum(int piles[], int n)
{
int i, nimsum = piles[0];
for (i=1; i<n; i++)
nimsum = nimsum ^ piles[i];
return(nimsum);
}
// A C function to make moves of the Nim Game
void makeMove(int piles[], int n, struct move * moves)
{
int i, nim_sum = calculateNimSum(piles, n);
// 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 (nim_sum != 0)
{
for (i=0; i<n; i++)
{
// If this is not an illegal move
// then make this move.
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;
}
}
}
// The player having the current turn is on losing
// position, so he/she/it can only wait for the opponent
// to make a mistake(which doesn't happen in this program
// as both players are playing optimally). He randomly
// choose a non-empty pile and randomly removes few stones
// from it. If the opponent doesn't make a mistake,then it
// doesn't matter which pile this player chooses, as he is
// destined to lose this game.
// 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.
else
{
// Create an array to hold indices of non-empty piles
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;
}
// A C function to play the Game of Nim
void playGame(int piles[], int n, int whoseTurn)
{
cout <<"\nGAME STARTS\n\n";
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\n";
else
cout <<"HUMAN will win\n";
}
else
{
if (whoseTurn == COMPUTER)
cout <<"HUMAN will win\n";
else
cout <<"COMPUTER will win\n";
}
return;
}
// Driver program to test above functions
int main()
{
// Test Case 1
int piles[] = {3, 4, 5};
int n = sizeof(piles)/sizeof(piles[0]);
// We will predict the results before playing
// The COMPUTER starts first
knowWinnerBeforePlaying(piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame(piles, n, COMPUTER);
/*
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
knowWinnerBeforePlaying (piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame (piles, n, HUMAN); */
return(0);
}
// This code is contributed by shivanisinghss2110
C
/* A C program to implement Game of Nim. The program
assumes that both players are playing optimally */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define COMPUTER 1
#define HUMAN 2
/* A Structure to hold the two parameters of a move
A move has two parameters-
1) pile_index = The index of pile from which stone is
going to be removed
2) stones_removed = Number of stones removed from the
pile indexed = pile_index */
struct move
{
int pile_index;
int stones_removed;
};
/*
piles[] -> Array having the initial count of stones/coins
in each piles before the game has started.
n -> Number of piles
The piles[] are having 0-based indexing*/
// A C function to output the current game state.
void showPiles (int piles[], int n)
{
int i;
printf ("Current Game Status -> ");
for (i=0; i<n; i++)
printf ("%d ", piles[i]);
printf("\n");
return;
}
// A C function that returns True if game has ended and
// False if game is not yet over
bool gameOver(int piles[], int n)
{
int i;
for (i=0; i<n; i++)
if (piles[i]!=0)
return (false);
return (true);
}
// A C function to declare the winner of the game
void declareWinner(int whoseTurn)
{
if (whoseTurn == COMPUTER)
printf ("\nHUMAN won\n\n");
else
printf("\nCOMPUTER won\n\n");
return;
}
// A C function to calculate the Nim-Sum at any point
// of the game.
int calculateNimSum(int piles[], int n)
{
int i, nimsum = piles[0];
for (i=1; i<n; i++)
nimsum = nimsum ^ piles[i];
return(nimsum);
}
// A C function to make moves of the Nim Game
void makeMove(int piles[], int n, struct move * moves)
{
int i, nim_sum = calculateNimSum(piles, n);
// 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 (nim_sum != 0)
{
for (i=0; i<n; i++)
{
// If this is not an illegal move
// then make this move.
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;
}
}
}
// The player having the current turn is on losing
// position, so he/she/it can only wait for the opponent
// to make a mistake(which doesn't happen in this program
// as both players are playing optimally). He randomly
// choose a non-empty pile and randomly removes few stones
// from it. If the opponent doesn't make a mistake,then it
// doesn't matter which pile this player chooses, as he is
// destined to lose this game.
// 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.
else
{
// Create an array to hold indices of non-empty piles
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;
}
// A C function to play the Game of Nim
void playGame(int piles[], int n, int whoseTurn)
{
printf("\nGAME STARTS\n\n");
struct move moves;
while (gameOver (piles, n) == false)
{
showPiles(piles, n);
makeMove(piles, n, &moves);
if (whoseTurn == COMPUTER)
{
printf("COMPUTER removes %d stones from pile "
"at index %d\n", moves.stones_removed,
moves.pile_index);
whoseTurn = HUMAN;
}
else
{
printf("HUMAN removes %d stones from pile at "
"index %d\n", moves.stones_removed,
moves.pile_index);
whoseTurn = COMPUTER;
}
}
showPiles(piles, n);
declareWinner(whoseTurn);
return;
}
void knowWinnerBeforePlaying(int piles[], int n,
int whoseTurn)
{
printf("Prediction before playing the game -> ");
if (calculateNimSum(piles, n) !=0)
{
if (whoseTurn == COMPUTER)
printf("COMPUTER will win\n");
else
printf("HUMAN will win\n");
}
else
{
if (whoseTurn == COMPUTER)
printf("HUMAN will win\n");
else
printf("COMPUTER will win\n");
}
return;
}
// Driver program to test above functions
int main()
{
// Test Case 1
int piles[] = {3, 4, 5};
int n = sizeof(piles)/sizeof(piles[0]);
// We will predict the results before playing
// The COMPUTER starts first
knowWinnerBeforePlaying(piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame(piles, n, COMPUTER);
/*
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
knowWinnerBeforePlaying (piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame (piles, n, HUMAN); */
return(0);
}
Python3
# A Python3 program to implement Game of Nim. The program
# assumes that both players are playing optimally
import random
COMPUTER = 1
HUMAN = 2
# A Structure to hold the two parameters of a move
# move has two parameters-
# 1) pile_index = The index of pile from which stone is
# going to be removed
# 2) stones_removed = Number of stones removed from the
# pile indexed = pile_index */
class move:
def __init__(self):
self.pile_index = 0
self.stones_removed = 0
# piles[] -> Array having the initial count of stones/coins
# in each piles before the game has started.
# n -> Number of piles
# The piles[] are having 0-based indexing
# A function to output the current game state.
def showPiles(piles, n):
print("Current Game Status -> ")
print(*piles)
# A function that returns True if game has ended and
# False if game is not yet over
def gameOver(piles, n):
for i in range(n):
if (piles[i] != 0):
return False
return True
# A function to declare the winner of the game
def declareWinner(whoseTurn):
if (whoseTurn == COMPUTER):
print("\nHUMAN won")
else:
print("\nCOMPUTER won")
return
# A function to calculate the Nim-Sum at any point
# of the game.
def calculateNimSum(piles, n):
nimsum = piles[0]
for i in range(1, n):
nimsum = nimsum ^ piles[i]
return nimsum
# A function to make moves of the Nim Game
def makeMove(piles, n, moves):
nim_sum = calculateNimSum(piles, n)
# 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 (nim_sum != 0):
for i in range(n):
# If this is not an illegal move
# then make this move.
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
# The player having the current turn is on losing
# position, so he/she/it can only wait for the opponent
# to make a mistake(which doesn't happen in this program
# as both players are playing optimally). He randomly
# choose a non-empty pile and randomly removes few stones
# from it. If the opponent doesn't make a mistake,then it
# doesn't matter which pile this player chooses, as he is
# destined to lose this game.
# 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.
else:
# Create an array to hold indices of non-empty piles
non_zero_indices = [None for _ in range(n)]
count = 0
for i in range(n):
if (piles[i] > 0):
non_zero_indices[count] = i
count += 1
moves.pile_index = int(random.random() * (count))
moves.stones_removed = 1 + \
int(random.random() * (piles[moves.pile_index]))
piles[moves.pile_index] -= moves.stones_removed
if (piles[moves.pile_index] < 0):
piles[moves.pile_index] = 0
return
# A C function to play the Game of Nim
def playGame(piles, n, whoseTurn):
print("\nGAME STARTS")
moves = move()
while (gameOver(piles, n) == False):
showPiles(piles, n)
makeMove(piles, n, moves)
if (whoseTurn == COMPUTER):
print("COMPUTER removes", moves.stones_removed,
"stones from pile at index ", moves.pile_index)
whoseTurn = HUMAN
else:
print("HUMAN removes", moves.stones_removed,
"stones from pile at index", moves.pile_index)
whoseTurn = COMPUTER
showPiles(piles, n)
declareWinner(whoseTurn)
return
def knowWinnerBeforePlaying(piles, n, whoseTurn):
print("Prediction before playing the game -> ", end="")
if (calculateNimSum(piles, n) != 0):
if (whoseTurn == COMPUTER):
print("COMPUTER will win")
else:
print("HUMAN will win")
else:
if (whoseTurn == COMPUTER):
print("HUMAN will win")
else:
print("COMPUTER will win")
return
# Driver program to test above functions
# Test Case 1
piles = [3, 4, 5]
n = len(piles)
# We will predict the results before playing
# The COMPUTER starts first
knowWinnerBeforePlaying(piles, n, COMPUTER)
# Let us play the game with COMPUTER starting first
# and check whether our prediction was right or not
playGame(piles, n, COMPUTER)
# This code is contributed by phasing17
C#
/* A C# program to implement Game of Nim. The program
assumes that both players are playing optimally */
using System;
using System.Collections.Generic;
/* A Class to hold the two parameters of a move
A move has two parameters-
1) pile_index = The index of pile from which stone is
going to be removed
2) stones_removed = Number of stones removed from the
pile indexed = pile_index */
class move {
public int pile_index;
public int stones_removed;
};
class GFG {
static int COMPUTER = 1;
static int HUMAN = 2;
static move moves = new move();
/*
piles[] -> Array having the initial count of
stones/coins in each piles before the game has started.
n -> Number of piles
The piles[] are having 0-based indexing*/
// A C# function to output the current game state.
static void showPiles(int[] piles, int n)
{
int i;
Console.Write("Current Game Status -> ");
for (i = 0; i < n; i++)
Console.Write(" " + piles[i]);
Console.WriteLine();
return;
}
// A C# function that returns True if game has ended and
// False if game is not yet over
static bool gameOver(int[] piles, int n)
{
int i;
for (i = 0; i < n; i++)
if (piles[i] != 0)
return false;
return true;
}
// A C# function to declare the winner of the game
static void declareWinner(int whoseTurn)
{
if (whoseTurn == COMPUTER)
Console.Write("\nHUMAN won\n\n");
else
Console.Write("\nCOMPUTER won\n\n");
return;
}
// A C# function to calculate the Nim-Sum at any point
// of the game.
static int calculateNimSum(int[] piles, int n)
{
int i, nimsum = piles[0];
for (i = 1; i < n; i++)
nimsum = nimsum ^ piles[i];
return (nimsum);
}
// A C# function to make moves of the Nim Game
static void makeMove(int[] piles, int n, move moves)
{
var rand = new Random();
int i, nim_sum = calculateNimSum(piles, n);
// 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 (nim_sum != 0) {
for (i = 0; i < n; i++) {
// If this is not an illegal move
// then make this move.
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;
}
}
}
// The player having the current turn is on losing
// position, so he/she/it can only wait for the
// opponent to make a mistake(which doesn't happen
// in this program as both players are playing
// optimally). He randomly choose a non-empty pile
// and randomly removes few stones from it. If the
// opponent doesn't make a mistake,then it doesn't
// matter which pile this player chooses, as he is
// destined to lose this game.
// 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.
else {
// Create an array to hold indices of non-empty
// piles
int[] non_zero_indices = new int[n];
int count = 0;
for (i = 0; i < n; i++) {
if (piles[i] > 0) {
non_zero_indices[count] = i;
count += 1;
}
}
(moves).pile_index = (rand.Next(count));
(moves).stones_removed
= 1
+ (rand.Next(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;
}
// A C# function to play the Game of Nim
static void playGame(int[] piles, int n, int whoseTurn)
{
Console.Write("\nGAME STARTS\n\n");
while (gameOver(piles, n) == false) {
showPiles(piles, n);
makeMove(piles, n, moves);
if (whoseTurn == COMPUTER) {
Console.WriteLine(
"COMPUTER removes "
+ moves.stones_removed
+ "stones from pile at index "
+ moves.pile_index);
whoseTurn = HUMAN;
}
else {
Console.WriteLine(
"HUMAN removes" + moves.stones_removed
+ "stones from pile at index "
+ moves.pile_index);
whoseTurn = COMPUTER;
}
}
showPiles(piles, n);
declareWinner(whoseTurn);
return;
}
static void knowWinnerBeforePlaying(int[] piles, int n,
int whoseTurn)
{
Console.Write(
"Prediction before playing the game -> ");
if (calculateNimSum(piles, n) != 0) {
if (whoseTurn == COMPUTER)
Console.Write("COMPUTER will win\n");
else
Console.Write("HUMAN will win\n");
}
else {
if (whoseTurn == COMPUTER)
Console.Write("HUMAN will win\n");
else
Console.Write("COMPUTER will win\n");
}
return;
}
// Driver program to test above functions
public static void Main(string[] arg)
{
// Test Case 1
int[] piles = { 3, 4, 5 };
int n = piles.Length;
// We will predict the results before playing
// The COMPUTER starts first
knowWinnerBeforePlaying(piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame(piles, n, COMPUTER);
/*
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
knowWinnerBeforePlaying (piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame (piles, n, HUMAN); */
}
}
// This code is contributed by phasing17
Javascript
/* A JavaScript program to implement Game of Nim. The program
assumes that both players are playing optimally */
let COMPUTER = 1;
let HUMAN = 2;
/* A Structure to hold the two parameters of a move
A move has two parameters-
1) pile_index = The index of pile from which stone is
going to be removed
2) stones_removed = Number of stones removed from the
pile indexed = pile_index */
class move
{
constructor()
{
this.pile_index;
this.stones_removed;
}
};
/*
piles[] -> Array having the initial count of stones/coins
in each piles before the game has started.
n -> Number of piles
The piles[] are having 0-based indexing*/
// A function to output the current game state.
function showPiles (piles, n)
{
let i;
process.stdout.write("Current Game Status -> ");
for (i=0; i<n; i++)
process.stdout.write(" " + piles[i]);
process.stdout.write("\n");
return;
}
// A function that returns True if game has ended and
// False if game is not yet over
function gameOver(piles, n)
{
let i;
for (i=0; i<n; i++)
if (piles[i]!=0)
return false;
return true;
}
// A function to declare the winner of the game
function declareWinner(whoseTurn)
{
if (whoseTurn == COMPUTER)
console.log("\nHUMAN won\n");
else
console.log("\nCOMPUTER won\n");
return;
}
// A function to calculate the Nim-Sum at any point
// of the game.
function calculateNimSum(piles, n)
{
let i, nimsum = piles[0];
for (i=1; i<n; i++)
nimsum = nimsum ^ piles[i];
return nimsum;
}
// A function to make moves of the Nim Game
function makeMove(piles, n, moves)
{
let i, nim_sum = calculateNimSum(piles, n);
// 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 (nim_sum != 0)
{
for (i=0; i<n; i++)
{
// If this is not an illegal move
// then make this move.
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;
}
}
}
// The player having the current turn is on losing
// position, so he/she/it can only wait for the opponent
// to make a mistake(which doesn't happen in this program
// as both players are playing optimally). He randomly
// choose a non-empty pile and randomly removes few stones
// from it. If the opponent doesn't make a mistake,then it
// doesn't matter which pile this player chooses, as he is
// destined to lose this game.
// 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.
else
{
// Create an array to hold indices of non-empty piles
let non_zero_indices = new Array(n);
let count;
for (i=0, count=0; i<n; i++)
if (piles[i] > 0)
non_zero_indices [count++] = i;
moves.pile_index = Math.floor(Math.random() * (count));
moves.stones_removed = 1 + Math.floor(Math.random() * (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;
}
// A C function to play the Game of Nim
function playGame(piles, n, whoseTurn)
{
console.log("\nGAME STARTS\n");
let moves = new move();
while (gameOver (piles, n) == false)
{
showPiles(piles, n);
makeMove(piles, n, moves);
if (whoseTurn == COMPUTER)
{
console.log("COMPUTER removes", moves.stones_removed, "stones from pile at index ", moves.pile_index);
whoseTurn = HUMAN;
}
else
{
console.log("HUMAN removes", moves.stones_removed, "stones from pile at index", moves.pile_index);
whoseTurn = COMPUTER;
}
}
showPiles(piles, n);
declareWinner(whoseTurn);
return;
}
function knowWinnerBeforePlaying(piles, n, whoseTurn)
{
process.stdout.write("Prediction before playing the game -> ");
if (calculateNimSum(piles, n) !=0)
{
if (whoseTurn == COMPUTER)
console.log("COMPUTER will win");
else
console.log("HUMAN will win");
}
else
{
if (whoseTurn == COMPUTER)
console.log("HUMAN will win");
else
console.log("COMPUTER will win");
}
return;
}
// Driver program to test above functions
// Test Case 1
let piles = [3, 4, 5];
let n = piles.length;
// We will predict the results before playing
// The COMPUTER starts first
knowWinnerBeforePlaying(piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame(piles, n, COMPUTER);
/*
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
knowWinnerBeforePlaying (piles, n, COMPUTER);
// Let us play the game with COMPUTER starting first
// and check whether our prediction was right or not
playGame (piles, n, HUMAN); */
// This code is contributed by phasing17
Salida: puede ser diferente en diferentes carreras ya que se utilizan números aleatorios para decidir el próximo movimiento (para el jugador perdedor).
Prediction before playing the game -> COMPUTER will win GAME STARTS Current Game Status -> 3 4 5 COMPUTER removes 2 stones from pile at index 0 Current Game Status -> 1 4 5 HUMAN removes 3 stones from pile at index 1 Current Game Status -> 1 1 5 COMPUTER removes 5 stones from pile at index 2 Current Game Status -> 1 1 0 HUMAN removes 1 stones from pile at index 1 Current Game Status -> 1 0 0 COMPUTER removes 1 stones from pile at index 0 Current Game Status -> 0 0 0 COMPUTER won
Referencias: https://en.wikipedia.org/wiki/Nim Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA