nim.cpp

This is a program to simulate the Nim game

/*
 - Chuong trinh Tro choi NIM
 - Compiler: Borland C 5.02
 - Written by: Ha Long & Phu Duy
*/
/*=============================================*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <dos.h>

//Khai bao cac bien toan cuc
const int maxpile = 10;		  // so dong lon nhat co the tao ra
const int maxstone = 30;     //so soi lon nhat trong 1 dong
const int khungcl = 10;      //mau cua bang
const int socl = 14;         //mau cua so
const int zerocl = 12;		  //mau cua so 0
int status;			//luot di, =0->may di||A di, =1->nguoi di||B di
int piles_at_fisrt, piles_at_pre;         //so dong ban dau va so dong hien tai

//Khai bao cau truc du lieu
struct stone_pile {
	int	stone;             // stone = soi
   stone_pile *next;
};
typedef stone_pile *list;
list root = NULL;
/*=============================================*/
void write(char *s, int c)
{
  textcolor(c);
  cprintf("%s",s);
}
/*=============================================*/
void put_piles(int &m)          // ham nhap vao so dong soi
{
	do {
   	write("\n Nhap so dong soi muon choi: ",2);       //2 = GREEN
      scanf("%d", &m);
   } while (m<=0 || m > maxpile);
}
/*============================================*/
void title(int i)
{
	clrscr();
   gotoxy(34,2);
   write("NIM GAME",13);
   gotoxy(43,2);
   switch (i) {
   	case 1:
      	write("- MISERE",13); break;
      case 2:
      	write("- NORMAL",13); break;
      case 3:
      	write("- GUIDE",13); break;
      default: break;
   }
}
/*=============================================*/
void create(list &root, int n)		//tao ra n dong soi voi so soi ngau nhien
{
	list cur, temp;
	int i;
   temp = new stone_pile;       		//tao dong dau tien
   temp->stone = random(maxstone)+1;  //de tranh tao ra dong co 0 vien soi
   temp->next = NULL;
   root = temp;
   cur = root;
   for (i=1; i<n; i++)        	//tao cac dong tiep theo
   {
   	temp = new stone_pile;
   	temp->stone = random(maxstone)+1;
      temp->next = NULL;
      cur->next = temp;
      cur = temp;
   }
}
/*===========================================*/
void display_table(list root)
{
	int i = 1, x1 = 5, x2 = 13, y = 6 ;
   list cur;
   cur = root;
   textcolor(khungcl);
   printf("\n"); cprintf(" +------+--------+");
   printf("\n"); cprintf(" | Dong | So soi |");
   printf("\n"); cprintf(" +------+--------+");
   while (cur != NULL){
      textcolor(khungcl);
      gotoxy(1, y);
	   cprintf(" |      |        |"); printf("\n");
      cprintf(" +------+--------+");
      if (cur->stone ==0) textcolor(zerocl);
      else textcolor(socl);
      gotoxy(x1, y); cprintf("%2d", i);
      gotoxy(x2, y); cprintf("%2d", cur->stone);
      i++;  y +=2;
      cur = cur->next;
   }
}
/*===========================================*/
int check_stone(list root, int k)  //kiem tra dong muon boc co hop le ko
{
	int i;
   list tmp = root;
   for(i=1; i<k; i++) tmp = tmp->next;
   if (tmp->stone) return 1;
   else return 0;
}
/*=============================================*/
void player(list &root)
{
	int  k, n, i;
   list tmp = root;
   do
   {
   	gotoxy(30,7);
   	printf(" Moi ban chon dong :              ");
   	gotoxy(51,7);
   	scanf("%d",&k);
   } while (k<=0 || k > piles_at_fisrt || check_stone(root, k)==0);

   for(i=1;i<k; i++) tmp = tmp->next;
   do {
      gotoxy(30,9);
      printf(" Va so soi muon boc:              ");
      gotoxy(51,9);
      scanf("%d", &n);
   } while (n<=0 || n > tmp->stone);
   tmp->stone = tmp->stone - n;
   if (tmp->stone ==0) piles_at_pre--;  //neu boc het thi giam so dong soi
}
/*=============================================*/
int nimsum(list root)
{
	int s;
   list cur = root;
   s = cur->stone;
   while (cur->next !=NULL) {
      cur = cur->next;
      s = s ^ cur->stone;
   }
   return s;
}
/*=============================================*/
int special_case(list root)  //kiem tra truong hop dac biet:
//neu dung tra ve vi tri dong co soi >1 ; neu sai tra ve 0
{
	int i=0, i1=0;    //bien dem so dong 1
	int pos;     // bien chi vi tri dong soi hien tai
	list cur;
	cur = root;
	while(cur!=NULL)
	{
		if(cur->stone ==1) i1++;
		else if (cur->stone >1) pos = i+1;
		cur= cur->next;
      i++;
	}
	if (i1== (piles_at_pre-1)) return pos;
	else return 0;
}
/*=============================================*/
int pile_max(list root, list &max) //tim ra dong co so soi lon nhat
{
	list  cur;
   int imax, i;
   max = root;
   imax=1;            //vi tri cua dong max
   cur = root->next;
   i = 2;
   while(cur !=NULL)
   {
   	if (cur->stone > max->stone) { max = cur; imax =i;}
      cur = cur->next;
		i ++;
   }
   return imax;
}
/*=============================================*/
void misere_stragety(list &root)          //chien thuat misere cua may'
{
	list tmp = root;
   int take, s, i;
   i=special_case(root);         //vi tri cua dong co nhieu vien soi
   if (i) {    				//roi vao truong hop dac biet
		for(int j=1; j< i; j++) tmp = tmp->next;

		if(piles_at_pre%2)                  //neu so dong soi hien tai la le?
			take = tmp->stone -1;       // thi de lai 1 vien trong dong do
		else                               //neu so dong hien tai la chan
			take = tmp->stone;         // thi boc het dong do
	}
   else {   
		s = nimsum(root);
      i=1;
		if (s)        //nimsum != 0
		{
			while((tmp->stone ^ s) >= tmp->stone) {
				tmp= tmp->next;
				i++;
			}
		take = tmp->stone - (tmp->stone ^ s);
		}
		else       // nimsum == 0
		{
			i = pile_max(root, tmp);
			take = random(tmp->stone)+1;
		}
	}
   tmp->stone -= take;
   if (tmp->stone==0) piles_at_pre --;

   gotoxy(30,7);
   printf(" Computer boc %d vien o dong %d.", take,i);
   getch();
}
/*=============================================*/
void normal_stragety(list &root)          //chien thuat normal cua may'
{
   list tmp = root;
   int take, s, i;       // take = so soi muon boc di
   s = nimsum(root);
   i=1;
	if(s)        //nimsum != 0
	{
		while((tmp->stone ^ s) >= tmp->stone) {
		tmp= tmp->next;
		i++;
		}
	take = tmp->stone - (tmp->stone ^ s);
	tmp->stone -= take;
	}
	else       // nimsum == 0
	{
		i = pile_max(root, tmp);
		take = random(tmp->stone)+1;
		tmp->stone -=take;
	}
   gotoxy(30,7);
   printf(" Computer boc %d vien o dong %d.", take,i);
   getch();
}
/*=============================================*/
int gieoxucxac()
{
   int k,i;
   clrscr();
   gotoxy(30,5);
   write(" Xin cho may gieo xuc xac: ",2);
   for(i=0; i<5; i++)
   {
      cprintf(".");
		sleep(1);
   }
   k =random(6);
   return(k%2);
}
/*=============================================*/
void start_game()
{
   clrscr();
   put_piles(piles_at_fisrt);
   randomize();          //khoi dong bo tao so ngau nhien
   create(root, piles_at_fisrt);
   piles_at_pre = piles_at_fisrt;
   status = gieoxucxac();
   gotoxy(30,7);
   if (status) write(" (=.=) Ban duoc di truoc!!!",11);
   else write(" (^_^) Computer di truoc!!!",14);
   gotoxy(30,9);
   printf(" Press any key to continue...");
   getch();
}
/*=============================================*/
int end_game(list root)
{
	list tmp;
   tmp = root;
   while(tmp != NULL && tmp->stone==0) tmp = tmp->next;
   if (tmp == NULL) return 1;
   else return 0;
}
/*=============================================*/
void misere_game()
{
   int end;
   start_game();
   do
   {
      title(1);
      display_table(root);
	   if (status) player(root);
      else misere_stragety(root);
      end = end_game(root);
      if (!end) status = !status;
   } while (!end);
   clrscr();title(1); display_table(root);
   gotoxy(33,7);
   if (status) write(" Sorry! You lose!!!",12);  //neu nguoi boc cuoi cung thi nguoi thua
   else write(" Congratulation! You win!!!",11); //neu may boc cuoi cung thi may thua => nguoi thang
   getch();
}
/*============================================*/
void normal_game()
{
   int end;
   start_game();
   do
   {
	   title(2);
      display_table(root);
      if (status) player(root);
      else normal_stragety(root);
      end = end_game(root);
      if (!end) status = !status;
   } while (!end);
   clrscr();title(2); display_table(root);
   gotoxy(33,7);
   if(status) write(" Congratulation! You win!!!",11);      //neu nguoi boc cuoi thi nguoi thang
   else  write(" Sorry! You lose!!!",12);            //neu nguoi boc cuoi thi nguoi thua
   getch();
}
/*============================================*/
void two_player(int mode)
{
   int end;
   clrscr();
   put_piles(piles_at_fisrt);
   randomize();          //khoi dong bo tao so ngau nhien
   create(root, piles_at_fisrt);
   piles_at_pre = piles_at_fisrt;
   status = gieoxucxac();
   gotoxy(30,7);
   if (status) write(" B duoc di truoc",14);
   else write(" A duoc di truoc",11);
   getch();
	do {
   	title(mode); display_table(root);
      gotoxy(27,5);
      if (status==0)  write("Luot cua A :",11);
      else 	write("Luot cua B :",14);
      player(root);
      end = end_game(root);
      if(!end) status= !status;
      } while (!end);
   clrscr();title(mode); display_table(root);
   if (mode==1)		//che do misere
   	status = !status;
   gotoxy(33,7);
   if (status ==0)	// nguoi A thang
  		write(" Congratulation! Player A win!!!",11);
   else write(" Congratulation! Player B win!!!",14);
   getch();
}
/*==============================================*/
void box(int x1,int y1,int x2,int y2)    // ham tao 1 hop vien quanh text
{
  int i;
  gotoxy(x1,y1);
  putch(201);
  for(i=x1+1;i<=x2-1;putch(205),i++);
  putch(187);
  gotoxy(x1,y2);
  putch(200);
  for(i=x1+1;i<=x2-1;putch(205),i++);
  putch(188);
  for(i=y1+1;i<=y2-1;i++)
     {
        gotoxy(x1,i);
        putch(186);
        gotoxy(x2,i);
        putch(186);
     }
}
/*============================================*/
void welcome_scr()
{
  char ch;
  do{
    clrscr();
    textcolor(YELLOW);
    box(29,6,53,14);
    gotoxy(36,9);
    write(" WELCOME TO",10);	//10 = LIGHTGREEN
    gotoxy(37,11);
    write(" NIM GAME ",10);
    gotoxy(29,23);
    write(" Author: Ha Long & Phu Duy ",9);    //9 = LIGHTBLUE
    gotoxy(36,24);
    write(" version 1.0 ",11);            //11 = LIGHTCYAN
    gotoxy(33,25);
    write(" Copyright 11/2008 ",11);
    gotoxy(28,17);
    printf(" Press ENTER to start game ");
    ch=getch();
    }while(ch!=0x0D);
}
/*=============================================*/
int mainmenu()
{
   int k;
   do{
      clrscr();
	   title(0);
      printf("\n\n\t");
      textcolor(14);		//yellow
      cprintf(" Main menu:");
      textcolor(11);    //lightcyan
      printf("\n\t\t");
      cprintf("\n1. One player");  printf("\n\t\t");
      cprintf("\n2. Two players"); printf("\n\t\t");
      cprintf("\n3. Guide");		  printf("\n\t\t");
      cprintf("\n0. Exit game");   printf("\n\t\t");
      printf("\n\t Choose: "); scanf("%d",&k);
   } while (k<0 || k>3);
   return k;
}
/*==============================================*/
int play_mode()                      // chon che do choi
{
  	int t;
   do{
      clrscr();
	   title(0);
      printf("\n\n\t");
      write(" Choose a play mode:",14);         //14 = yellow
      printf("\n\t\t");
      write("\n1. Misere mode ",11); printf("\n\t\t");     //11 = lightcyan
      write("\n2. Normal mode ",11); printf("\n\t\t");
      write("\n0. Back",11);	printf("\n\t\t");
      printf("\n\t Choose: "); scanf("%d",&t);
     } while (t<0 || t>2);
   return t;
}
/*==============================================*/
void help()                         // muc huong dan nguoi choi
{
  char ch[256];
  FILE *fp;
  fp = fopen("help.txt","r");      // doc file huong dan
  clrscr();
  title(3);
  while (!feof(fp))
    {
      fgets(ch,70,fp);
      printf("%s",ch);
    }
  fclose(fp);
  write("\n\r\n Press any key to return main menu...",6);
  getch();
}
/*============================================*/
void main()
{
   int cmd , mode;
   welcome_scr();
   do {
      cmd = mainmenu();
      switch (cmd) {
      	case 1:
         	mode = play_mode();
            if(mode==1) misere_game();
            else if (mode ==2) normal_game();
            break;
         case 2:
         	mode = play_mode();
         	if (mode) two_player(mode);
         	break;
         case 3:
            help();
         	break;
         case 0: break;
      }
   } while (cmd);
}