h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

An interesting idea, but somehow I don't think it'd ever get approved! Perhaps you could put a compiled version around. If it had been written in Basic then maybe people would be able to understand it better and an explaination of how the logic works would possibly help. I haven't looked in depth yet at the code yet, I must confess.

Erm... this wasn't supposed to be an approvable article. If you look at my 'Creating an Artificial Intelligence to Play Minesweeper' page, that *is* supposed to be approvable... no code at all, just the basics of the algorithm. I just posted this when someone asked me if I had the source for a working version...

Actually, I do have a QBASIC version. The only problem being, well, there are two: firstly, I don't know where it is, and secondly, it runs very, very, very slowly indeed . If you're going to take a brute-force approach to Minesweeper, y'really have to use a fast language...

I wouldn't recommend looking in depth at the code... my programming style isn't *exactly* optimal for comprehensibility...

But you're welcome to try.

26199

I did see that... 2seconds after writing the posting
BASIC is far more intuitive than C, though.

Hehe

BASIC is indeed easier to understand than C... although my BASIC programming might not be...

Actually, seeing as I'm writing this from college, I might well have the BASIC version here with me... lessee... got it!

Might as well just stick it in here... it'll get me to the top of the 'longest forum post' table, if nothing else .

CLS
DEFINT A-Z
RANDOMIZE TIMER
BoardW = 15
BoardH = 15
Mines = (15 * 15) / 5
Spec = 26

DIM Board(BoardW + 1, BoardH + 1)
DIM BoardI(BoardW + 1, BoardH + 1)
DIM BoardK(BoardW + 1, BoardH + 1)
DIM BoardS(BoardW + 1, BoardH + 1, Spec)
DIM BoardR(BoardW + 1, BoardH + 1)
DIM BoardC(BoardW + 1, BoardH + 1)
DIM BoardCT(BoardW + 1, BoardH + 1)

GOSUB CreateBoard
GOSUB GenerateInfo
GOSUB DisplayBoard

DO
MadeShortGuess = 1
WHILE MadeShortGuess = 1: GOSUB MakeShortGuess: WEND

FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
BoardCT(Bx, By) = 0
NEXT
NEXT

FOR Sc = 1 TO Spec
GOSUB CreateSpec
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
BoardCT(Bx, By) = BoardCT(Bx, By) + BoardC(Bx, By)
NEXT
NEXT

NEXT
GOSUB AnalyseBoard
GOSUB MakeGuess
GOSUB DisplayBoard
LOOP

CreateSpec:

RestartCount = 0
DO
RestartCount = RestartCount + 1
IF RestartCount = 1 OR RestartCount > 26 THEN
Mc = Mines

FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
BoardS(Bx, By, Sc) = 0
IF BoardK(Bx, By) = 2 THEN
BoardS(Bx, By, Sc) = 1
Mc = Mc - 1
END IF
NEXT
NEXT

FOR Mcc = 1 TO Mc
DO
Bx = INT(RND * BoardW) + 1
By = INT(RND * BoardH) + 1
LOOP UNTIL BoardK(Bx, By) = 0 OR (Board(Bx, By) = 0 AND BoardK(Bx, By) = 1)
BoardS(Bx, By, Sc) = 1
NEXT
RestartCount = 1
END IF


FoundInc = 0
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
BoardC(Bx, By) = 0
NEXT
NEXT

FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH

IF BoardK(Bx, By) = 1 THEN
Ma = BoardI(Bx, By)
Mc = 0
FOR xx = -1 TO 1
FOR yy = -1 TO 1
IF (xx <> 0) OR (yy <> 0) THEN
Mc = Mc + BoardS(Bx + xx, By + yy, Sc)
END IF
NEXT
NEXT

IF Ma > Mc THEN
FoundInc = 1
Reps = Ma - Mc
FOR Rc = 1 TO Reps
DO
x = INT(RND * BoardW) + 1
y = INT(RND * BoardH) + 1
LOOP UNTIL BoardS(x, y, Sc) = 1 AND BoardK(x, y) <> 2
BoardS(x, y, Sc) = 0
Lc = 0
DO
xx = INT(RND * 3) - 1
yy = INT(RND * 3) - 1
Lc = Lc + 1: IF Lc > 15 THEN FoundInc = 1
LOOP UNTIL (Bx + xx >= 1) AND (Bx + xx <= BoardW) AND (By + yy >= 1) AND (By + yy <= BoardH) AND BoardS(Bx + xx, By + yy, Sc) = 0 AND (xx <> 0 OR yy <> 0) AND (BoardC(Bx + xx, By + yy) = 0 OR Lc > 15)
BoardS(Bx + xx, By + yy, Sc) = 1
NEXT
END IF

IF Ma < Mc THEN
FoundInc = 1
Reps = Mc - Ma
FOR Rc = 1 TO Reps
DO
xx = INT(RND * 3) - 1
yy = INT(RND * 3) - 1
LOOP UNTIL BoardS(Bx + xx, By + yy, Sc) = 1 AND BoardK(Bx + xx, By + yy) <> 2 AND (xx <> 0 OR yy <> 0)
BoardS(Bx + xx, By + yy, Sc) = 0
DO
x = INT(RND * BoardW) + 1
y = INT(RND * BoardH) + 1
LOOP UNTIL BoardK(x, y) = 0 OR (Board(x, y) = 0 AND BoardK(x, y) = 1) AND BoardS(x, y, Sc) <> 1 AND BoardC(x, y) = 0
BoardS(x, y, Sc) = 1
NEXT
END IF

IF Ma = Mc THEN
FOR xx = -1 TO 1
FOR yy = -1 TO 1
IF (xx <> 0 OR yy <> 0) AND BoardS(Bx + xx, By + yy, Sc) = 0 THEN
BoardC(Bx + xx, By + yy) = 1
END IF
NEXT
NEXT
END IF

END IF
NEXT
NEXT
IF FoundInc = 1 THEN LOCATE 19, Sc: PRINT CHR$(RestartCount + 64);
LOOP WHILE FoundInc = 1
RETURN


AnalyseBoard:
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
BoardR(Bx, By) = 0
FOR Sc = 1 TO Spec
BoardR(Bx, By) = BoardR(Bx, By) + BoardS(Bx, By, Sc)
NEXT
NEXT
NEXT
RETURN

MakeShortGuess:
MadeShortGuess = 0
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
IF BoardK(Bx, By) = 1 AND BoardI(Bx, By) = 0 THEN
FOR xx = -1 TO 1
FOR yy = -1 TO 1
IF xx <> 0 OR yy <> 0 THEN
IF BoardK(Bx + xx, By + yy) = 0 AND (Bx + xx >= 1) AND (By + yy >= 1) AND (Bx + xx <= BoardW) AND (By + yy <= BoardH) THEN
LOCATE 18, 1: PRINT "Uncovered square. (Short guess) ";
BoardK(Bx + xx, By + yy) = 1
GOSUB DisplayBoard: xx = 2: yy = 2: MadeShortGuess = 1
END IF
END IF
NEXT
NEXT
END IF
NEXT
NEXT
RETURN

MakeGuess:
LowProb = Spec
HighProb = 0
GuessCertain = 0

FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
IF BoardK(Bx, By) = 0 THEN
IF BoardR(Bx, By) < LowProb THEN LowProb = BoardR(Bx, By)
IF BoardR(Bx, By) > HighProb THEN HighProb = BoardR(Bx, By)
IF BoardCT(Bx, By) = Spec THEN LowProb = -1
END IF
NEXT
NEXT

IF HighProb = Spec THEN
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
IF BoardK(Bx, By) = 0 THEN IF BoardR(Bx, By) = HighProb THEN GuessX = Bx: GuessY = By: GuessType = 2
NEXT
NEXT
ELSE
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
IF BoardK(Bx, By) = 0 AND BoardR(Bx, By) = LowProb THEN GuessX = Bx: GuessY = By: GuessType = 1
IF BoardK(Bx, By) = 0 AND BoardCT(Bx, By) = Spec THEN GuessX = Bx: GuessY = By: GuessType = 1: GuessCertain = 1
NEXT
NEXT
END IF

IF GuessType = 1 THEN
IF Board(GuessX, GuessY) = 1 THEN LOCATE 18, 1: PRINT "Stepped on mine. ": BoardK(GuessX, GuessY) = 1: GOSUB DisplayBoard: END
IF Board(GuessX, GuessY) = 0 THEN
IF GuessCertain = 0 THEN LOCATE 18, 1: PRINT "Uncovered square. "; : BoardK(GuessX, GuessY) = 1
IF GuessCertain = 1 THEN LOCATE 18, 1: PRINT "Uncovered square. (Certain) "; : BoardK(GuessX, GuessY) = 1
END IF
END IF

IF GuessType = 2 THEN
IF Board(GuessX, GuessY) = 1 THEN LOCATE 18, 1: PRINT "Flagged mine. "; : BoardK(GuessX, GuessY) = 2
IF Board(GuessX, GuessY) = 0 THEN LOCATE 18, 1: PRINT "Incorrectly flagged mine. "; : BoardK(GuessX, GuessY) = 2
END IF
RETURN

CreateBoard:
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
Board(Bx, By) = 0
BoardK(Bx, By) = 0
NEXT
NEXT
FOR Mc = 1 TO Mines
Bx = INT(RND * BoardW) + 1
By = INT(RND * BoardH) + 1
Board(Bx, By) = 1
NEXT
RETURN

GenerateInfo:
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
MCount = 0
FOR xx = -1 TO 1
FOR yy = -1 TO 1
IF xx <> 0 OR yy <> 0 THEN
MCount = MCount + Board(Bx + xx, By + yy)
END IF
NEXT
NEXT
BoardI(Bx, By) = MCount
IF Board(Bx, By) = 1 THEN BoardI(Bx, By) = -1
NEXT
NEXT
RETURN

DisplayBoard:
FOR Bx = 1 TO BoardW
FOR By = 1 TO BoardH
LOCATE By, Bx * 3
COLOR (15 - BoardK(Bx, By))
PRINT BoardI(Bx, By); " "
NEXT
NEXT
COLOR 15
RETURN