Source Code for a Minesweeper AI

2 Conversations

What follows is the Ansi C source for an artificial intelligence whose sole purpose is to play Minesweeper. To compile it, you'll either need to rewrite the display routines (any calls to 'textout' and 'rectfill', plus a few routines in the initiation) or get hold of DJGPP and Allegro.

Enjoy!

(Coded by 26199)

#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <dos.h>
#include <time.h>
#include "allegro.h"
#define BoardW 16
#define BoardH 16
#define Mines 40
#define Spec 30

int Board[BoardW][BoardH];
int BoardI[BoardW][BoardH];
int BoardK[BoardW][BoardH];
int BoardS[BoardW][BoardH][Spec];
int BoardR[BoardW][BoardH];
int BoardC[BoardW][BoardH];
int BoardCT[BoardW][BoardH];
int Bx,By,Sc;
void CreateBoard(void);
void GenerateInfo(void);
void DisplayBoard(void);
void AnalyseBoard(void);
void MakeGuess(void);
void CreateSpec(void);
int MakeShortGuess(void);
int TimeToRestart;
int Attempts=0;
int Successes=0;
int DoneIt;

int WithinBoard(int x,int y)
{
if(x<0) return 0;
if(y<0) return 0;
if(x>=BoardW) return 0;
if(y>=BoardH) return 0;
return 1;
}

int main()
{
int k;
allegro_init();
set_color_depth(24);
set_gfx_mode(GFX_AUTODETECT,640,480,0,0);
while(1)
{
TimeToRestart=0;
CreateBoard();
GenerateInfo();
DisplayBoard();

while (TimeToRestart==0)
{
while (MakeShortGuess()==1);
for(Bx=0; Bx<BoardW; Bx++) for(By=0; By<BoardH; By++) BoardCT[Bx][By]=0;
for(Sc=0; Sc<Spec; Sc++)
{
CreateSpec();
rectfill(screen,(Sc*SCREEN_W)/Spec,450,(((Sc+1)*SCREEN_W)/Spec)-1,460,makecol24(50,50,100));
rectfill(screen,(Sc*SCREEN_W)/Spec+2,452,(((Sc+1)*SCREEN_W)/Spec)-3,458,makecol24(50,50,250));
for(Bx=0; Bx<BoardW; Bx++) for(By=0; By<BoardH; By++) BoardCT[Bx][By]+=BoardC[Bx][By];
}
AnalyseBoard();
MakeGuess();
DisplayBoard();
rectfill(screen,0,450,SCREEN_W-1,460,0);

DoneIt=1;
for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
if(BoardK[Bx][By]==0) DoneIt=0;
}
}
if(DoneIt==1) { Successes=Successes+1; Attempts=Attempts+1; TimeToRestart=1; }
}
}
}

void CreateSpec(void)
{
int RestartCount;
int FoundInc;
int Mc,Mc2,Ma,xx,yy,Reps,Rc,x,y,Lc,Mcc;
int RestartMax=54;

RestartCount=0;
FoundInc=1;

while(FoundInc==1)
{
RestartCount++;
if((RestartCount==1)||(RestartCount>RestartMax))
{
Mc=Mines;
if(RestartMax>4) RestartMax-=10;
for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
BoardS[Bx][By][Sc]=0;
if(BoardK[Bx][By]==2) { BoardS[Bx][By][Sc]=1; Mc--; }
}
}
for(Mcc=0; Mcc<Mc; Mcc++)
{
RLoop1:
Bx=rand()%BoardW;
By=rand()%BoardH;
if(!((BoardK[Bx][By]==0)||((Board[Bx][By]==0)&&(BoardK[Bx][By]==1)))) goto RLoop1;
BoardS[Bx][By][Sc]=1;
}
RestartCount=1;
}

FoundInc=0;
for(Bx=0; Bx<BoardW; Bx++) for(By=0; By<BoardH; By++) BoardC[Bx][By]=0;

for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
if(BoardK[Bx][By]==1)
{
Ma=BoardI[Bx][By];
Mc=0;
for(xx=-1; xx<2; xx++)
{
for(yy=-1; yy<2; yy++)
{
if((xx!=0)||(yy!=0))
{
if(WithinBoard(Bx+xx,By+yy)) Mc+=BoardS[Bx+xx][By+yy][Sc];
}
}
}

if(Ma>Mc)
{
FoundInc=1;
Reps=Ma-Mc;
for(Rc=0; Rc<Reps; Rc++)
{
RLoop2:
x=rand()%BoardW;
y=rand()%BoardH;
if(!((BoardS[x][y][Sc]==1)&&(BoardK[x][y]!=2))) goto RLoop2;
BoardS[x][y][Sc]=0;
Lc=0;
RLoop3:
xx=(rand()%3)-1;
yy=(rand()%3)-1;
Lc++;
if(!((WithinBoard(Bx+xx,By+yy))&&(BoardS[Bx+xx][By+yy][Sc]==0)&&((xx!=0)||(yy!=0))&&((BoardC[Bx+xx][By+yy]==0)||(Lc>20)))) goto RLoop3;
BoardS[Bx+xx][By+yy][Sc]=1;
}
}

if(Ma<Mc)
{
FoundInc=1;
Reps=Mc-Ma;
for(Rc=0; Rc<Reps; Rc++)
{
RLoop4:
xx=(rand()%3)-1;
yy=(rand()%3)-1;
if(!((BoardS[Bx+xx][By+yy][Sc]==1)&&(BoardK[Bx+xx][By+yy]!=2)&&((xx!=0)||(yy!=0)))) goto RLoop4;
if(WithinBoard(Bx+xx,By+yy)==0) goto RLoop4;
BoardS[Bx+xx][By+yy][Sc]=0;
RLoop5:
x=rand()%BoardW;
y=rand()%BoardH;
if(!((BoardK[x][y]==0)||((Board[x][y]==0)&&(BoardK[x][y]==1))&&(BoardS[x][y][Sc]!=1)&&(BoardC[x][y]==0))) goto RLoop5;
BoardS[x][y][Sc]=1;
}
}

if(Ma==Mc)
{
for(xx=-1; xx<2; xx++)
{
for(yy=-1; yy<2; yy++)
{
if(WithinBoard(Bx+xx,By+yy)==1)
{
if(((xx!=0)||(yy!=0))&&(BoardS[Bx+xx][By+yy][Sc]==0))
{
BoardC[Bx+xx][By+yy]=1;
}
}
}
}
}

}
}
}
//if(FoundInc==1) printf("%c",RestartCount+64);
}
//printf(".");
}

void AnalyseBoard(void)
{
for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
BoardR[Bx][By]=0;
for(Sc=0; Sc<Spec; Sc++)
{
BoardR[Bx][By]=BoardR[Bx][By]+BoardS[Bx][By][Sc];
}
}
}
}

int MakeShortGuess(void)
{
int GuessFlag=0;
int xx,yy;
for(Bx=0; (Bx<BoardW)&&(GuessFlag==0); Bx++)
{
for(By=0; (By<BoardH)&&(GuessFlag==0); By++)
{
if((BoardK[Bx][By]==1)&&(BoardI[Bx][By]==0))
{
for(xx=-1; (xx<2)&&(GuessFlag==0); xx++)
{
for(yy=-1; (yy<2)&&(GuessFlag==0); yy++)
{
if(((xx!=0)||(yy!=0))&&(WithinBoard(Bx+xx,By+yy)==1))
{
if(BoardK[Bx+xx][By+yy]==0)
{
//printf("\nUncovered Square (Short guess)\n");
BoardK[Bx+xx][By+yy]=1;
DisplayBoard();
GuessFlag=1;
}
}
}
}
}
}
}
}

void MakeGuess(void)
{
int LowProb,HighProb,GuessCertain;
int GuessX,GuessY,GuessType;
LowProb=Spec;
HighProb=0;
GuessCertain=0;

for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
if(BoardK[Bx][By]==0)
{
if(BoardR[Bx][By]<LowProb) LowProb=BoardR[Bx][By];
if(BoardR[Bx][By]>HighProb) HighProb=BoardR[Bx][By];
if(BoardCT[Bx][By]==Spec) LowProb=-1;
}
}
}

if(HighProb==Spec)
{
for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
if(BoardK[Bx][By]==0) if(BoardR[Bx][By]==HighProb)
{
GuessX=Bx; GuessY=By; GuessType=2;
}
}
}
}
if(HighProb!=Spec)
{
for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
if((BoardK[Bx][By]==0)&&(BoardR[Bx][By]==LowProb)) { GuessX=Bx; GuessY=By; GuessType=1;}
if((BoardK[Bx][By]==0)&&(BoardCT[Bx][By]==Spec)) { GuessX=Bx; GuessY=By; GuessType=1; GuessCertain=1; }
}
}
}

if(GuessType==1)
{
if(Board[GuessX][GuessY]==1)
{
//printf("\nStepped on mine.\n");
BoardK[GuessX][GuessY]=1;
DisplayBoard();
TimeToRestart=1;
Attempts=Attempts+1;
}
if(Board[GuessX][GuessY]==0)
{
if(GuessCertain==0)
{
//printf("\nUncovered Square.\n");
BoardK[GuessX][GuessY]=1;
}
else
{
//printf("\nUncovered Square. (Certain)\n");
BoardK[GuessX][GuessY]=1;
}
}
}

if(GuessType==2)
{
if(Board[GuessX][GuessY]==1)
{
//printf("Flagged mine. ");
BoardK[GuessX][GuessY]=2;
}
if(Board[GuessX][GuessY]==0)
{
//printf("Incorrectly flagged mine. ");
BoardK[GuessX][GuessY]=2;
}
}
}

void CreateBoard(void)
{
int Mc;
for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
Board[Bx][By]=0;
BoardK[Bx][By]=0;
BoardR[Bx][By]=0;
BoardC[Bx][By]=0;
BoardCT[Bx][By]=0;
for(Sc=0; Sc<Spec; Sc++) BoardS[Bx][By][Sc]=0;
}
}

for(Mc=0; Mc<Mines; Mc++)
{
RLoop7:
Bx=rand()%BoardW;
By=rand()%BoardH;
if(Board[Bx][By]==1) goto RLoop7;
Board[Bx][By]=1;
}
}

void GenerateInfo(void)
{
int MCount,xx,yy;
for(Bx=0; Bx<BoardW; Bx++)
{
for(By=0; By<BoardH; By++)
{
MCount=0;
for(xx=-1; xx<2; xx++)
{
for(yy=-1; yy<2; yy++)
{
if(((xx!=0)||(yy!=0))&&(WithinBoard(Bx+xx,By+yy)==1))
{
MCount+=Board[Bx+xx][By+yy];
}
}
}
BoardI[Bx][By]=MCount;
if(Board[Bx][By]==1) BoardI[Bx][By]=-1;
}
}
}

void DisplayBoard(void)
{
char String[64];
char Buffer[64];
int score;
for(By=0; By<BoardH; By++)
{
for(Bx=0; Bx<BoardW; Bx++)
{
if(Board[Bx][By]==0) String[0]='-'; else String[0]='*';
String[1]=NULL;
textout(screen,font,String,Bx*14,By*14,makecol24(255*(BoardK[Bx][By]&1),255*(BoardK[Bx][By]&2),255));
}
}

//if(Attempts>0)
//{
textout(screen,font,"Success Rate: ",0,470,makecol24(255,255,255));
//score=(Successes*100)/Attempts;
itoa(Successes,String,10);
itoa(Attempts,Buffer,10);
strcat(String," / ");
strcat(String,Buffer);
strcat(String," ");
textout(screen,font,String,112,470,makecol24(255,255,255));
//}
}

Bookmark on your Personal Space


Entry

A270703

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry


Written and Edited by

Disclaimer

h2g2 is created by h2g2's users, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the Not Panicking Ltd. Unlike Edited Entries, Entries have not been checked by an Editor. If you consider any Entry to be in breach of the site's House Rules, please register a complaint. For any other comments, please visit the Feedback page.

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more