Advertisement

My attempt at game AI

Started by September 28, 2003 05:37 PM
2 comments, last by darkawakenings 21 years, 2 months ago
Ok, this is minimal, but it seemed good until a dialog box popped up that said the following: The program has encountered a general protection fault. When I tried to run it a second time, it said : This program encounteres an unspecified exception. The first time I ran it, it analyzed between 200,000 and 300,000 positions before crapping out and throwing the dialog box, but the second time, it popped the box right as it began analyzing. Here is the source code, I know it is a lot, (~600 lines) but I have no clue what is causing this

#include<io.h>
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#include<fcntl.h>
#include<time.h>

int long total_pos;
int handle;
int long inc_pos;
time_t first;
struct Layout {
  int board[7][7];
  int turn;
  int comp;
  };

struct Move {
  char dir;
  int xto;
  int yto;
  int xfr;
  int yfr;
  char tpmoves[20];
  };

int MakeMoveList(struct Layout def,struct Move list[80]);
int SetSafes(struct Layout *def);
void ShowLayout(struct Layout def);
void ShowMoves(struct Move list[80]);
int CheckSafe(struct Layout def,int x, int y);
void TPFinder(int x, int y, int endx, int endy, struct Move list[80], int curmove);
int FillMoves(struct Layout def, struct Move list[80],char dir, int cur_integer, int curx, int cury);
void DoMove(struct Move m, struct Layout *def);
void UndoMove(struct Move m, struct Layout *def);
int CheckWin(struct Layout def,int for_player);
int NMSearch(struct Layout def, int curd);
Move FirstNMSearch(struct Layout def, int curd);
void OpenFile();
char convtochar(int i);
																										  //Beginning of Main

void main() {
total_pos= 0;
handle = 0;
int i=0;
Layout def;                                                                     //Declaration of basic data groups

def.turn = 2;
def.comp = 1;																						  //Filling of the Layout with the basic data

def.board[0][0] = 0;
def.board[0][1] = 0;
def.board[0][2] = 0;
def.board[0][3] = 0;
def.board[0][4] = 0;
def.board[0][5] = 0;
def.board[0][6] = 0;
def.board[6][4] = 0;
def.board[6][0] = 0;
def.board[6][1] = 0;
def.board[6][2] = 0;
def.board[6][3] = 0;
def.board[6][4] = 0;
def.board[6][5] = 0;
def.board[6][6] = 0;
def.board[1][6] = 0;
def.board[2][6] = 0;
def.board[3][6] = 0;
def.board[4][6] = 0;
def.board[5][6] = 0;
def.board[1][0] = 0;
def.board[2][0] = 0;
def.board[3][0] = 0;
def.board[4][0] = 0;
def.board[5][0] = 0;
def.board[1][1] = 2;
def.board[1][2] = 2;
def.board[1][3] = 1;
def.board[1][4] = 1;
def.board[1][5] = 1;
def.board[2][1] = 1;
def.board[2][2] = 1;
def.board[2][3] = 1;
def.board[2][4] = 1;
def.board[2][5] = 1;
def.board[3][1] = 1;
def.board[3][2] = 1;
def.board[3][3] = 3;
def.board[3][4] = 1;
def.board[3][5] = 1;
def.board[4][1] = 1;
def.board[4][2] = 1;
def.board[4][3] = 1;
def.board[4][4] = 4;
def.board[4][5] = 1;                                                            //Wrappin'' up the basic data entry...

def.board[5][1] = 1;
def.board[5][2] = 1;
def.board[5][3] = 1;
def.board[5][4] = 2;
def.board[5][5] = 2;
//inc_pos = 0;

cout << "\nBeginning Program\n";

OpenFile();
ShowLayout(def);
cout << "\n\nAbove is the position.  It is player 1''s Move.";
getch();
first = time(&first);
Move bestmove = FirstNMSearch(def,1);

cout << "\n\nBest Move: " << bestmove.dir << " " << bestmove.xfr << bestmove.yfr << "-" << bestmove.xto << bestmove.yto;


cout << "\n\nProgram End";
getch();
close(handle);
}

int MakeMoveList(struct Layout def, struct Move list[80]) {                     //A function to fill the list with all of

																										  //The Possible moves in Layout def.																			  //Only fills moves that lead to safe

																										  //Squares.

int ix=1,iy=1;                                                                  //Code to figure out where the player is.

int ix2=1,iy2=1;
int total_moves = 0;

while(ix<6){
  while(iy<6){                                                                  //Sets player''s position to ix and iy

	 if(def.board[ix][iy]== def.turn+2)
		goto breakloop;
	 iy++;
	 }
  iy=1;
  ix++;
  }
breakloop:
;


if(def.board[ix][iy-1] == 1||def.board[ix][iy-1] == 5){                         //If the spot above  him is open,

  def.board[ix][iy-1] = def.comp+2;                                             //First make that move

  SetSafes(&def);																					  //And then check the rest of the board

																										  //For safe sqaures

  total_moves = FillMoves(def,list,''5'',total_moves,ix,iy-1);                     //Fill up the moves in their list

  def.board[ix][iy-1] = 1;															           //Finally, unmake the move

																										  //And reset safe squares

  while(ix2 < 6) {
	 while(iy2 < 6) {
		if(def.board[ix2][iy2] == 5)
		  def.board[ix2][iy2] = 1;
		iy2++;
		}
	 ix2++;
	 }
  }
ix2 = 1;
iy2 = 1;

if(def.board[ix][iy+1] == 1||def.board[ix][iy+1] == 5){                         //The spot below him

  def.board[ix][iy+1] = def.comp+2;
  SetSafes(&def);

  total_moves = FillMoves(def,list,''2'',total_moves,ix,iy+1);
  def.board[ix][iy+1] = 1;

  while(ix2 < 6) {
	 while(iy2 < 6) {
		if(def.board[ix2][iy2] == 5)
		  def.board[ix2][iy2] = 1;
		iy2++;
		}
	 ix2++;
	 }
  }
ix2 = 1;
iy2 = 1;

if(def.board[ix+1][iy] == 1||def.board[ix+1][iy] == 5){                         //The spot right of him

  def.board[ix+1][iy] = def.comp+2;
  SetSafes(&def);

  total_moves = FillMoves(def,list,''3'',total_moves,ix+1,iy);
  def.board[ix+1][iy] = 1;

  while(ix2 < 6) {
	 while(iy2 < 6) {
		if(def.board[ix2][iy2] == 5)
		  def.board[ix2][iy2] = 1;
		iy2++;
		}
	 ix2++;
	 }
  }
ix2 = 1;
iy2 = 1;

if(def.board[ix-1][iy] == 1||def.board[ix-1][iy] == 5){                         //The spot left of him

  def.board[ix-1][iy] = def.comp+2;
  SetSafes(&def);

  total_moves = FillMoves(def,list,''1'',total_moves,ix-1,iy);
  def.board[ix-1][iy] = 1;

  while(ix2 < 6) {
	 while(iy2 < 6) {
		if(def.board[ix2][iy2] == 5)
		  def.board[ix2][iy2] = 1;
		iy2++;
		}
	 ix2++;
	 }
  }
return total_moves;
}

void ShowLayout(struct Layout def) {                                            //A function to show the contents of any

																										  //Position on the screen.

cout << "\n";
int x=0,y=0;
while(y < 7) {
  while(x < 7) {
	 cout << def.board[x][y];
	 x++;
	 }
  cout << "\n";
  x = 0;
  y++;
  }

}

int SetSafes(struct Layout *def) {                                              //A function to set all of the safe squares

int x=1,y=1; 															                 		  //In a given Layout



while(x<6) {                                                                    //Loop to check every square

  while(y<6) {
	 if(CheckSafe(*def,x,y)==1)
	 def->board[x][y] = 5;
	 y++;
	 }
  y=1;
  x++;
  }

return 0;
}

int CheckSafe(struct Layout def,int x, int y){                                  //A function to check if a single square is

																										  //safe.

char cover = 0;
int enemy = 0;

if(def.comp == 1)
  enemy = 4;
if(def.comp == 2)
  enemy = 3;

char north_open = 0;
char south_open = 0;
char east_open = 0;
char west_open = 0;



if(def.board[x][y-1] == 1||def.board[x][y-1] == 5){                             // If the spot above is empty (Or already

																										  // Called Safe)

  if((def.board[x][y-2] != enemy&&def.board[x-1][y-1] != enemy&&def.board[x+1][y-1]!= enemy)||cover == 1)
  north_open = 1;                                                               //^ And the enemy isn''t around it, or

  else                                                                          // covering another square

  cover = 1;
  }
if(def.board[x][y+1] == 1||def.board[x][y+1] == 5){
  if((def.board[x][y+2] != enemy&&def.board[x-1][y+1] != enemy&&def.board[x+1][y+1]!= enemy)||cover == 1)
  south_open = 1;
  else
  cover = 1;
  }
if(def.board[x-1][y] == 1||def.board[x-1][y] == 5){
  if((def.board[x-2][y] != enemy&&def.board[x-1][y-1] != enemy&&def.board[x-1][y+1]!= enemy)||cover == 1)
  west_open = 1;
  else
  cover = 1;
  }
if(def.board[x+1][y] == 1||def.board[x+1][y] == 5){
  if((def.board[x+2][y] != enemy&&def.board[x+1][y-1] != enemy&&def.board[x+1][y+1]!= enemy)||cover == 1)
  east_open = 1;
  else
  cover = 1;
  }


if(north_open + south_open + west_open + east_open > 1&&(def.board[x][y] == 1||def.board[x][y] == 5))
  return 1;

return 0;
}

void TPFinder(int x, int y, int endx, int endy,struct Move list[80],int curmove){//Function that fills in a list number with

char compile_string[20];																			  //keys to get to a teleporter.




strcpy(compile_string, "");                                                      //Test for Data Overflow

if(strcmp("", compile_string)!= 0){
  cout << "FATAL ERROR:  DATA OVERFLOW";
  exit(1);
  }

while(x > endx){
  strcat(compile_string, "1");                                                  //Fill in keys as 1, 2, 3, and 5 for the

  x--;                                                                          //selection of an open teleporter.

  }
while(x < endx){
  strcat(compile_string, "3");
  x++;
  }
while(y < endy){
  strcat(compile_string, "2");
  y++;
  }
while(y > endy){
  strcat(compile_string, "5");
  y--;
  }
strcat(compile_string, "0");
strcpy(list[curmove].tpmoves,compile_string);
if(strcmp(list[curmove].tpmoves,compile_string)!= 0){
  cout << "\nFATAL ERROR 2: DATA OVERFLOW";
  exit(1);
  }
}

int FillMoves(struct Layout def, struct Move list[80], char dir, int cur_move,int curx, int cury) {
																										  //A function that looks at the Layout, and

int x=1,y=1;																						  //Fills in the possible moves based on the

while(x < 6){																						  //Marked Safe Squares.

  while(y < 6){
	 if(def.board[x][y] == 5){                                                   //Scans through the whole board for safe

		list[cur_move].dir = dir;                                                 //squares, and then puts them on the list as

		list[cur_move].xto = x;
      list[cur_move].yto = y;
		list[cur_move].xfr = curx;
		list[cur_move].yfr = cury;
		TPFinder(curx,cury,x,y,list,cur_move);                                                  //possible moves.

		cur_move++;
		}
	 y++;
	 }
  x++;
  y=1;
  }


return cur_move;
}

void ShowMoves(struct Move list[80]) {
int i = 0;

while(i < 15){
cout << "\n" << list[i].dir << " " << list[i].tpmoves;
i++;
}

getch();

while(i < 35){
cout << "\n" << list[i].dir << " " << list[i].tpmoves;
i++;
}
getch();
while(i < 55){
cout << "\n" << list[i].dir << " " << list[i].tpmoves;
i++;
}


}

void DoMove(struct Move m, struct Layout *def) {                                //Does a move on a layout


int x=1,y=1;                                                                    //Finds where the player is

while(x<6){
  while(y<6){
	 if(def->board[x][y] == def->turn+2)
		goto break_manual;
	 y++;
	 }
  y=1;
  x++;
  }
break_manual:
;

def->board[x][y] = 2;                                                           //Their Current Spot is used

if(m.dir == ''5'')                                                                  //The direction they moved in is used

  def->board[x][y-1] = 2;
if(m.dir == ''1'')
  def->board[x-1][y] = 2;
if(m.dir == ''2'')
  def->board[x][y+1] = 2;
if(m.dir == ''3'')
  def->board[x+1][y] = 2;


def->board[m.xto][m.yto] = def->turn+2;                                         //They come out at their destination

}

void UndoMove(struct Move m, struct Layout *def) {                              //Undoes a move on a layout

def->board[m.xto][m.yto] = 1;
def->board[m.xfr][m.yfr] = 1;
if(m.dir == ''5'')
  def->board[m.xfr][m.yfr+1] = def->turn+2;
if(m.dir == ''2'')
  def->board[m.xfr][m.yfr-1] = def->turn+2;
if(m.dir == ''1'')
  def->board[m.xfr+1][m.yfr] = def->turn+2;
if(m.dir == ''3'')
  def->board[m.xfr-1][m.yfr] = def->turn+2;

}

int CheckWin(struct Layout def,int for_player) {                                //Returns a 1 if the Layout is a win for

int x=1,y=1;   																					  //the player who called it.

char cover=0,NorthOpen=0,EastOpen=0,SouthOpen=0,WestOpen=0;

while(x<6){                                                                     //Sets x and y to the enemies position

  while(y<6){
	 if(def.board[x][y] == 7-for_player)
		goto break_manual2;
	 y++;
	 }
  x++;
  y=1;
  }
break_manual2:
;

if(def.board[x][y-1] == 1||def.board[x][y-1] == 5){                             //Check if the north square is safe

  if((def.board[x][y-2] != for_player&&def.board[x-1][y-1] != for_player&&def.board[x+1][y-1]!= for_player)||cover == 1)
	 NorthOpen = 1;
  else
	 cover = 1;
  }
if(def.board[x][y+1] == 1||def.board[x][y+1] == 5){                             //South

  if((def.board[x][y+2] != for_player&&def.board[x-1][y+1] != for_player&&def.board[x+1][y+1]!= for_player)||cover == 1)
	 SouthOpen = 1;
  else
	 cover = 1;
  }
if(def.board[x+1][y] == 1||def.board[x+1][y] == 5){                             //East

  if((def.board[x+2][y] != for_player&&def.board[x+1][y-1] != for_player&&def.board[x+1][y+1]!= for_player)||cover == 1)
	 EastOpen = 1;
  else
	 cover = 1;
  }
if(def.board[x-1][y] == 1||def.board[x-1][y] == 5){                             //West

  if((def.board[x-2][y] != for_player&&def.board[x-1][y-1] != for_player&&def.board[x-1][y+1]!= for_player)||cover == 1)
	 WestOpen = 1;
  else
	 cover = 1;
  }

if((int)NorthOpen+(int)WestOpen+(int)SouthOpen+(int)EastOpen > 1)
  return 0;
return 1;
}

int NMSearch(struct Layout def, int curd) {                                     //A function to search for a move using the

int i=0,i2=-1;																						  //NegaMax technique

char x=-1, y=-1;
int spaces = curd;
def.turn = 3-def.turn;
struct Move list[80];
int value, n = 0,bestvalue = -100;
while(i<80){                                 
  strcpy(list[i].tpmoves, "");
  list[i].dir = 9;
  list[i].xto = 9;
  list[i].yto = 9;
  list[i].xfr = 9;
  list[i].yfr = 9;
  i++;};

inc_pos++;
if(inc_pos == 100000){
  total_pos++;
  cout << "\n" << total_pos << "00000 Positions Searched";
  inc_pos = 0;
  }

if(CheckWin(def, def.turn+2)==1){                                                //If the position is winning, for this

  while(spaces >0){
	 write(handle, "  ", 2);
	 spaces--;
	 }
  write(handle, "END\n", 4);
  return 100;                                                                   //return 100

  }
n = MakeMoveList(def, list);                                                    //make the list!


if(n==0)
  return -100;

for(i=0;i<n;i++){
  DoMove(list, &def);

  spaces = curd;
  i2 = -1;
  while(spaces&gt;0){
	 write(handle, "</font>  ",  2);
	 spaces–;
	 }

  write(handle, &list[<font color=purple>i</font>].dir, 1);
  write(handle, <font color=darkred>" "</font>, 1);
  x = convtochar(list[<font color=purple>i</font>].xto);
  y = convtochar(list[<font color=purple>i</font>].yto);
  write(handle, &x, 1);
  write(handle, &y, 1);
  write(handle, ",", 1);
  x = convtochar(list[<font color=purple>i</font>].xfr);
  y = convtochar(list[<font color=purple>i</font>].yfr);
  write(handle, &x, 1);
  write(handle, &y, 1);
  write(handle, <font color=darkred><font color=darkred>"\n"</font></font>,  1);

  value = -NMSearch(def,curd+1);
  UndoMove(list[<font color=purple>i</font>], &def);
  bestvalue = max(bestvalue, value);
  }
<font color=blue>return</font> bestvalue;
}

<font color=blue>void</font> OpenFile() {
handle = open("DUMPFILE.TXT<font color=darkred>",O_WRONLY|O_CREAT|O_TRUNC);
}

Move FirstNMSearch(struct Layout def, int curd) {                                     <font color=gray>//A function to search for a move using the
</font>
Move bestmove;
int i=0,i2=-1;																						  <font color=gray><font color=gray>//NegaMax technique
</font></font>
char x=-1, y=-1;
int spaces = curd;
def.turn = 3-def.turn;
struct Move list[80];
int value, n = 0,bestvalue = -100;
while(i&lt;80){
  strcpy(list.tpmoves, "</font><font color=darkred>");
  list.dir = 9;
  list.xto = 9;
  list.yto = 9;
  list.xfr = 9;
  list.yfr = 9;
  i++;};

bestmove.dir = 9;
bestmove.xto = 9;
bestmove.yto = 9;
bestmove.xfr = 9;
bestmove.yfr = 9;

clrscr();
ShowLayout(def);

n = MakeMoveList(def, list);                                                    <font color=gray><font color=gray>//make the list!
</font></font>

for(i=0;i&lt;n;i++){
  DoMove(list, &def);

  spaces = curd;
  i2 = -1;
  while(spaces&gt;0){
	 write(handle, "</font>  ",  2);
	 spaces–;
	 }

<font color=gray>//  write(handle, &list.dir, 1);
</font>
<font color=gray>//  write(handle, " ", 1);
</font>
<font color=gray>//  x = convtochar(list.xto);
</font>
 <font color=gray>// y = convtochar(list.yto);
</font>
 <font color=gray>//// write(handle, &x, 1);
</font>
<font color=gray><font color=gray>//  write(handle, &y, 1);
</font></font>
<font color=gray>//  write(handle, ",", 1);
</font>
<font color=gray>//  x = convtochar(list.xfr);
</font>
<font color=gray>//  y = convtochar(list.yfr);
</font>
<font color=gray>///  write(handle, &x, 1);
</font>
<font color=gray><font color=gray>//  write(handle, &y, 1);
</font></font>
<font color=gray>//  write(handle, "\n",  1);
</font>

  value = -NMSearch(def,curd+1);
  UndoMove(list[<font color=purple>i</font>], &def);
  <font color=blue>if</font>(value == 100){
	 bestmove = list[<font color=purple>i</font>];
	 <font color=blue>goto</font> endd;}
  }
endd:
;
<font color=blue>return</font> bestmove;
}







<font color=blue>char</font> convtochar(<font color=blue>int</font> i){

  <font color=blue>if</font>(i == 0)
  <font color=blue>return</font> ''0'';
  <font color=blue>if</font>(i == 1)
  <font color=blue>return</font> ''1'';
  <font color=blue>if</font>(i == 2)
  <font color=blue>return</font> ''2'';
  <font color=blue>if</font>(i == 3)
  <font color=blue>return</font> ''3'';
  <font color=blue>if</font>(i == 4)
  <font color=blue>return</font> ''4'';
  <font color=blue>if</font>(i == 5)
  <font color=blue>return</font> ''5'';
  <font color=blue>if</font>(i == 6)
  <font color=blue>return</font> ''6'';
  <font color=blue>if</font>(i == 7)
  <font color=blue>return</font> ''7'';
  <font color=blue>if</font>(i == 8)
  <font color=blue>return</font> ''8'';
  <font color=blue>if</font>(i == 9)
  <font color=blue>return</font> ''9'';

<font color=blue>return</font> ''-'';
}

</pre><!–ENDSCRIPT–>    

<A HREF="http://www.geocities.com/jodownhomepage">A Mathematical game developed and played excessively by friends and I</A>   
Some debug info would be nice.. and for some reason I can''t seem to copy and paste into VC??
Advertisement
Gather round children.. the lesson here is to comment your code line by line so others can help you. Also you seem to be mixing c and c++, which while it should still work.. its pretty nasty looking.

Well anyhow, I''m getting two errors when I compile it, complaining about max() and clrscr(), are you compiling in borland or vcpp?

also ditto to psykr, it would be easier if you provided us some debug info, i.e. what line it crashes on.

you can IM me next time i am online and I''ll try and help you cory.
Yes, I''m using Borland, which is probably why your Inadequate compiler''s cant handle it (lol), but yes, im going to delete this post because I fixed the error. Thx for the responses though.

A Mathematical game developed and played excessively by friends and I

This topic is closed to new replies.

Advertisement