掃雷中，你需要在不點(diǎn)錯(cuò)雷的情況下盡可能快的將所有的雷都標(biāo)記出來，如果你點(diǎn)錯(cuò)，就得重新開始，所以掃雷也有一定的運(yùn)氣成分。但是在botzone中，你點(diǎn)錯(cuò)并不重新開始，而是只是在最后的分中扣分。
掃雷中數(shù)字的含義表示九宮格內(nèi)雷的數(shù)目。
這就是掃雷規(guī)則。
實(shí)際游戲中還有操作技巧問題，例如雙擊和定式。我們寫bot不考慮這一點(diǎn)，我們采取盲掃的方式來實(shí)現(xiàn)一個(gè)輕量級(jí)的掃雷bot。這很適合初學(xué)者來練習(xí)。
首先給大家推薦一下botzone，botzone平臺(tái)為很多種游戲bot對(duì)戰(zhàn)提供了技術(shù)支持，使用json實(shí)現(xiàn)交互。例如北大計(jì)算概論(A)的黑白棋就是在這個(gè)平臺(tái)上完成的。最后我給出的完整代碼可以提交在botzone上直接運(yùn)行。
首先掃雷的規(guī)則大家都很清楚了。我們平時(shí)玩掃雷的時(shí)候關(guān)鍵是背定式。但是我們的bot可以直接枚舉不考慮時(shí)間代價(jià)。
那么我們先想一個(gè)粗放的框架:先計(jì)算出每個(gè)點(diǎn)是空白的概率，然后挑選一個(gè)概率最大的點(diǎn)點(diǎn)擊。事實(shí)上其實(shí)在游戲的大部分情況下幾乎每一步都不需要猜，甚至都不需要考慮剩余雷的問題，直到最后才需要猜一下。所以既然是掃雷的簡(jiǎn)易bot，我們可以做以下簡(jiǎn)化:我們僅僅挑選出一定不是雷的地點(diǎn)點(diǎn)擊，如果不存在這樣的地點(diǎn)，我們?cè)诳赡懿皇抢椎牡攸c(diǎn)任意挑選一個(gè)點(diǎn)擊。
那么為了完成以上功能，我們至少要做以下幾步:1.在地圖中找到一定是雷的地方，2.在地圖中找到一定不是雷的地方。
也就是說，首先要實(shí)現(xiàn)在以下格式求解1.2.兩個(gè)問題的函數(shù)，數(shù)據(jù)格式為:
int fieldHeight, fieldWidth;int mineField[MAX_HEIGHT][MAX_WIDTH]; //[row][col]/* * 0-8: digits * 9: mine * 10: unrevealed */這個(gè)問題其實(shí)十分簡(jiǎn)單，可以作為初學(xué)者的思考題，但是很有意思。下面是一個(gè)簡(jiǎn)單的解答，但不是很美妙:
int surround_min_mines(int row, int col){ int r, c, dr, dc, count = 0; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && ((dr!= 0) || (dc!= 0))) { if (mineField[r][c] == 9) count++; } } return count;}int surround_max_mines(int row, int col){ int r, c, dr, dc, count = 0; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && ((dr!= 0) || (dc!= 0))) { if ((mineField[r][c] == 9) or (mineField[r][c] == 10)) count++; } } return count;}bool must_not_a_mine(int row, int col){ int r, c, dr, dc; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && (mineField[r][c] < 9) && ((dr!= 0) || (dc!= 0))) { if (surround_min_mines(r, c) == mineField[r][c]) return true; } } return false;}bool must_be_a_mine(int row, int col){ int r, c, dr, dc; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && (mineField[r][c] < 9) && ((dr!= 0) || (dc!= 0))) { if (surround_max_mines(r, c) == mineField[r][c]) return true; } } return false;}有了這兩個(gè)函數(shù)就很簡(jiǎn)單了，我們可以寫出函數(shù)decide()決定點(diǎn)擊位置，這是decide()的一個(gè)解答:
void decide(int& decidedRow, int& decidedCol){ int unrevealedPos[MAX_HEIGHT * MAX_WIDTH][2], unrevealedScore[MAX_HEIGHT * MAX_WIDTH]; int unrevealedCount = 0; int row, col; for (row = 0; row < fieldHeight; row++) for (col = 0; col < fieldWidth; col++) if ((mineField[row][col] == 10) && must_be_a_mine(row, col)) { mineField[row][col] = 9; unrevealedPos[unrevealedCount][0] = row; unrevealedPos[unrevealedCount][1] = col; unrevealedScore[unrevealedCount] = -1; unrevealedCount++; } for (row = 0; row < fieldHeight; row++) { for (col = 0; col < fieldWidth; col++) { if (mineField[row][col] == 10) { unrevealedPos[unrevealedCount][0] = row; unrevealedPos[unrevealedCount][1] = col; unrevealedScore[unrevealedCount] = must_not_a_mine(row, col); unrevealedCount++; } } } int myChoice = 0; for (int i = 1; i < unrevealedCount; i++) if (unrevealedScore[i] > unrevealedScore[myChoice]) myChoice = i; decidedRow = unrevealedPos[myChoice][0]; decidedCol = unrevealedPos[myChoice][1]; return;}綜合上面的函數(shù)，外加調(diào)試模塊，我們可以寫出最終解答，這個(gè)解答就是我的bot版本，經(jīng)過測(cè)試，效果不錯(cuò)，基本只會(huì)在首雷或者最后要猜的情況下觸雷，而這是不可避免的。以下為完整的最終bot，供參考。如果調(diào)試不對(duì)可以去botzone上跑一跑，還有圖形界面。
/* * minesweeper(botzone) * naive */#define TESTx//TEST is test mode#include <iostream>#include <string>#include <cstdlib>#include <cstdio>#ifndef TEST#include "jsoncpp/json.h"#endif#define MAX_WIDTH 80#define MAX_HEIGHT 40using namespace std;int mineCount;#ifdef TESTint fieldHeight = 3, fieldWidth = 3;int mineField[MAX_HEIGHT][MAX_WIDTH] = { { 10, 10, 10, 10}, { 10, 8, 10, 4}, { 10, 10, 10, 2}, };#elseint fieldHeight, fieldWidth;int mineField[MAX_HEIGHT][MAX_WIDTH]; //[row][col]#endif/* * 0-8: digits * 9: mine * 10: unrevealed */int surround_min_mines(int row, int col){ int r, c, dr, dc, count = 0; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && ((dr!= 0) || (dc!= 0))) { if (mineField[r][c] == 9) count++; } } return count;}int surround_max_mines(int row, int col){ int r, c, dr, dc, count = 0; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && ((dr!= 0) || (dc!= 0))) { if ((mineField[r][c] == 9) or (mineField[r][c] == 10)) count++; } } return count;}bool must_not_a_mine(int row, int col){ int r, c, dr, dc; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && (mineField[r][c] < 9) && ((dr!= 0) || (dc!= 0))) { if (surround_min_mines(r, c) == mineField[r][c]) return true; } } return false;}bool must_be_a_mine(int row, int col){ int r, c, dr, dc; for (dr = -1; dr <= 1; dr++) for (dc = -1; dc <= 1; dc++) { r = row + dr; c = col + dc; if ((r >= 0) && (r < fieldHeight) && (c >= 0) && (c < fieldWidth) && (mineField[r][c] < 9) && ((dr!= 0) || (dc!= 0))) { if (surround_max_mines(r, c) == mineField[r][c]) return true; } } return false;}void decide(int& decidedRow, int& decidedCol){ int unrevealedPos[MAX_HEIGHT * MAX_WIDTH][2], unrevealedScore[MAX_HEIGHT * MAX_WIDTH]; int unrevealedCount = 0; int row, col; for (row = 0; row < fieldHeight; row++) for (col = 0; col < fieldWidth; col++) if ((mineField[row][col] == 10) && must_be_a_mine(row, col)) { mineField[row][col] = 9; unrevealedPos[unrevealedCount][0] = row; unrevealedPos[unrevealedCount][1] = col; unrevealedScore[unrevealedCount] = -1; unrevealedCount++; } for (row = 0; row < fieldHeight; row++) { for (col = 0; col < fieldWidth; col++) { if (mineField[row][col] == 10) { unrevealedPos[unrevealedCount][0] = row; unrevealedPos[unrevealedCount][1] = col; unrevealedScore[unrevealedCount] = must_not_a_mine(row, col); unrevealedCount++; } } } int myChoice = 0; for (int i = 1; i < unrevealedCount; i++) if (unrevealedScore[i] > unrevealedScore[myChoice]) myChoice = i; decidedRow = unrevealedPos[myChoice][0]; decidedCol = unrevealedPos[myChoice][1]; return;}#ifdef TESTint main(){ int row, col;新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
