さて、面倒なのは3の判定です。単に縦、横、対角線のいずれかに
同じ石が3つ並んでいるだけではだめです。片方が止められている可能性もあります。
また、飛び3という場合もあります。これは、昔から判定法が決まっていて
「6つの並びで両端が空き、中4つに空き1つ、残り3つが同じ石」(3の法則)
というのがあります。
いろいろな場合を考えると、なるほど3が出来るのはこの法則以外の場合にはありません。 しかし、ちょっと困った事もあります。次のような場合を考えてみましょう。
黒の「飛び3」が出来ました。
白が止めました。
黒が「4」を作りました。
この場合、「6つの並びで両端が空き、中4つに空き1つ、残り3つが同じ石」となる
部分があるため「3」と判定されてしまいます。従って、この法則で3を発見したら
もう1つ外側を調べて同じ色の石があれば、「止め4」の可能性があることを
検査しなくてはいけません。他にも誤判定をする場合があるかも知れません。
次に「4」の判定も昔から定石があります。
「5つの並びに同じ石が4つと空き1つ」
これは、プログラムは比較的簡単でしょう。
次に、「3」や「4」がどこにあるかを調べる方法を考えます。 多分、効率が良いのは石を置いたらその石の位置を中心に検査すればよいでしょう。 しかし、かなり面倒くさいです。ここでは、盤面を片っ端から調べるという荒技を 使うことにします。実際にはこのようなプログラムを書いても実行時にかなりの非力なパソコンでも 遅さを感じることはありません。また、このような関数を作っておくと、コンピュータと対戦する プログラムでコンピュータが置く位置を調べる時に流用できるかもしれません(希望的観測)。
次に「3」や「4」を調べる関数を作り、戻り値にその数を返すようにしてみます。 もし「3」を調べる関数が2を返すと「33」の禁じ手が出来たことになります。 「4」を調べる関数が2を返すと「44」が出来たということになります。 それぞれが1を返したときは「43」と判定します。
また、「43」が出来てもそれで勝ちとは言い切れません。この4を止めた石で、止めた方に4 が出来ると勝敗はわかりません。 (注:ここでは、前章のルールで行います)
では、プログラムを見てみましょう。
gomoku03.rcに変更はありません。
// gomoku03.cpp #ifndef STRICT #define STRICT #endif #include <windows.h> #include "resource.h" #define SHUI 30 //碁盤の周囲の幅 #define KANKAKU 20 //碁盤のマス目の間隔 #define STONESIZE 10 //碁石の半径 LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM); ATOM InitApp(HINSTANCE); BOOL InitInstance(HINSTANCE, int); BOOL MyMakeBan(HDC); BOOL MyCircle(HDC, int, int, int); //盤(X,Y)に半径Rの円を描画 BOOL SetStone(HWND, int, int); BOOL MyStoneDraw(HDC); int Is5(HWND, int, int); int Is4(HWND); //4があるかどうか調べその数を返す int Is3(HWND); //3があるかどうか調べその数を返す char szClassName[] = "gomoku03"; //ウィンドウクラス HINSTANCE hInst; BOOL bSente = TRUE; //現在の差し手 先手:TRUE 後手:FALSE BOOL bStart = FALSE; //対戦中かどうか int ban[15][15]; //0:石無し 1:先手 2:後手Is3,Is4の関数が増えました。
int WINAPI WinMain(HINSTANCE hCurInst, HINSTANCE hPrevInst, LPSTR lpsCmdLine, int nCmdShow) { MSG msg; hInst = hCurInst; if (!InitApp(hCurInst)) return FALSE; if (!InitInstance(hCurInst, nCmdShow)) return FALSE; while (GetMessage(&msg, NULL, 0, 0)) { TranslateMessage(&msg); DispatchMessage(&msg); } return msg.wParam; } //ウィンドウ・クラスの登録 ATOM InitApp(HINSTANCE hInst) { WNDCLASSEX wc; wc.cbSize = sizeof(WNDCLASSEX); wc.style = CS_HREDRAW | CS_VREDRAW; wc.lpfnWndProc = WndProc; //プロシージャ名 wc.cbClsExtra = 0; wc.cbWndExtra = 0; wc.hInstance = hInst;//インスタンス wc.hIcon = LoadIcon(hInst, "MYICON"); wc.hCursor = LoadCursor(NULL, IDC_ARROW); wc.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH); wc.lpszMenuName = "MYMENU"; //メニュー名 wc.lpszClassName = (LPCSTR)szClassName; wc.hIconSm = LoadIcon(hInst, "MYICON"); return (RegisterClassEx(&wc)); } //ウィンドウの生成 BOOL InitInstance(HINSTANCE hInst, int nCmdShow) { HWND hWnd; hWnd = CreateWindow(szClassName, "猫でもわかる五目並べ", //タイトルバーにこの名前が表示されます WS_OVERLAPPEDWINDOW, //ウィンドウの種類 CW_USEDEFAULT, //X座標 CW_USEDEFAULT, //Y座標 CW_USEDEFAULT, //幅 CW_USEDEFAULT, //高さ NULL, //親ウィンドウのハンドル、親を作るときはNULL NULL, //メニューハンドル、クラスメニューを使うときはNULL hInst, //インスタンスハンドル NULL); if (!hWnd) return FALSE; ShowWindow(hWnd, nCmdShow); UpdateWindow(hWnd); return TRUE; } //ウィンドウプロシージャ LRESULT CALLBACK WndProc(HWND hWnd, UINT msg, WPARAM wp, LPARAM lp) { int id, x, y; static int nTe = 0; PAINTSTRUCT ps; HDC hdc; char szBuf[64], szSashite[16]; static HMENU hMenu; switch (msg) { case WM_CREATE: hMenu = GetMenu(hWnd); break; case WM_PAINT: hdc = BeginPaint(hWnd, &ps); MyMakeBan(hdc); MyStoneDraw(hdc); if (bSente) strcpy(szSashite, "先手●"); else strcpy(szSashite, "後手○"); wsprintf(szBuf, "差し手 = %s", szSashite); TextOut(hdc, 30, SHUI + KANKAKU * 14 + 30, szBuf, strlen(szBuf)); wsprintf(szBuf, "第 %02d 手終了 現在 %02d 手目待ち", nTe, nTe + 1); TextOut(hdc, 30, SHUI + KANKAKU * 14 + 50, szBuf, strlen(szBuf)); EndPaint(hWnd, &ps); break; case WM_LBUTTONDOWN: if (bStart == FALSE) break; x = LOWORD(lp); y = HIWORD(lp); if (x >= SHUI && y >= SHUI && x <= KANKAKU * 14 + SHUI && y <= KANKAKU * 14 + SHUI) { SetStone(hWnd, x, y); nTe++; } break; case WM_MENUSELECT: if (bStart) { EnableMenuItem(hMenu, IDM_START, MF_BYCOMMAND | MF_GRAYED); DrawMenuBar(hWnd); } else { EnableMenuItem(hMenu, IDM_START, MF_BYCOMMAND | MF_ENABLED); DrawMenuBar(hWnd); } break; case WM_COMMAND: switch (LOWORD(wp)) { case IDM_START: bStart = TRUE; nTe = 0; memset(ban, 0, sizeof(ban)); bSente = TRUE; InvalidateRect(hWnd, NULL, TRUE); break; case IDM_END: SendMessage(hWnd, WM_CLOSE, 0, 0); break; } break; case WM_CLOSE: id = MessageBox(hWnd, "終了してもよいですか", "終了確認", MB_YESNO | MB_ICONQUESTION); if (id == IDYES) { DestroyWindow(hWnd); } break; case WM_DESTROY: PostQuitMessage(0); break; default: return (DefWindowProc(hWnd, msg, wp, lp)); } return 0; } BOOL MyMakeBan(HDC hdc) { int i; HBRUSH hBrush, hOldBrush; for (i = 0; i < 15; i++) { MoveToEx(hdc, SHUI, i * KANKAKU + SHUI, NULL); LineTo(hdc, KANKAKU * (15 - 1) + SHUI, i * KANKAKU + SHUI); } for (i = 0; i < 15; i++) { MoveToEx(hdc, KANKAKU * i + SHUI, SHUI, NULL); LineTo(hdc, KANKAKU * i + SHUI, KANKAKU * (15 - 1) + SHUI); } hBrush = (HBRUSH)GetStockObject(BLACK_BRUSH); hOldBrush = (HBRUSH)SelectObject(hdc, hBrush); MyCircle(hdc, 3, 3, 3); MyCircle(hdc, 11, 3, 3); MyCircle(hdc, 3, 11, 3); MyCircle(hdc, 11, 11, 3); MyCircle(hdc, 7, 7, 3); SelectObject(hdc, hOldBrush); return TRUE; } BOOL MyCircle(HDC hdc, int x, int y, int r) { int x1, x2, y1, y2; x1 = x * KANKAKU + SHUI - r; x2 = x * KANKAKU + SHUI + r + 1; y1 = y * KANKAKU + SHUI - r; y2 = y * KANKAKU + SHUI + r + 1; Ellipse(hdc, x1, y1, x2, y2); return TRUE; }これらの関数に変更はありません。
BOOL SetStone(HWND hWnd, int x, int y) { int banx, bany, n4, n3; char szSashite[8], szStr[64]; if (bSente) strcpy(szSashite, "先手"); else strcpy(szSashite, "後手"); banx = (x - SHUI + KANKAKU / 2) / KANKAKU; bany = (y - SHUI + KANKAKU / 2) / KANKAKU; if (ban[banx][bany] != 0) { MessageBox(hWnd, "そこは置けません", "注意", MB_OK); return TRUE; } if (bSente) { ban[banx][bany] = 1; } else { ban[banx][bany] = 2; } InvalidateRect(hWnd, NULL, FALSE); if (Is5(hWnd, banx, bany) != -1) { bStart = FALSE; return FALSE; } n4 = Is4(hWnd); if (n4 != 0) { if (n4 > 1) { wsprintf(szStr, "%sに44が出来ました。\nまだ対戦を続けますか", szSashite); if (MessageBox(hWnd, szStr, "確認", MB_YESNO | MB_ICONQUESTION) == IDNO) { bStart = FALSE; return FALSE; } } wsprintf(szStr, "%sに4が出来ました", szSashite); MessageBox(hWnd, szStr, "警告", MB_OK); } n3 = Is3(hWnd); if (n3 == 1 && n4 == 1) { wsprintf(szStr, "%sに43が出来ました\nまだ対戦を続けますか", szSashite); if (MessageBox(hWnd, szStr, "確認", MB_YESNO | MB_ICONQUESTION) == IDNO) { bStart = FALSE; return FALSE; } } if (n3 != 0) { if (n3 > 1) { wsprintf(szStr, "%sの反則負けです", szSashite); MessageBox(hWnd, szStr, "33", MB_OK); bStart = FALSE; return FALSE; } wsprintf(szStr, "%sに3が出来ました", szSashite); MessageBox(hWnd, szStr, "警告", MB_OK); } bSente = !bSente; InvalidateRect(hWnd, NULL, FALSE); return TRUE; }石を置いたら、まず「5」の判定を行うところは同じです。
「5」が出来ていないときはIs4関数を呼んで「4」の数を調べます。 これが2以上(実際は最大でも2です)あれば、44で勝ちです。
1個または0個の時は次の「3」の判定に進みます。
Is3関数を呼んで「3」の数が2以上であれば「33」で直ちに負けです。 (後手は33でも良いというルールもありますが、ここでは先手でも後手でも負けです)
「3」や「4」が出来た場合相手が見逃して勝ったのではつまらないので、 その旨メッセージボックスを出して知らせます。
その後bSenteのTRUE/FALSEを入れ替えます。
さて、ここで注意しなくてはいけないことがあります。このあと、 もう一度InvalidateRect関数を呼ぶ必要があります。なぜかというと 実験すればすぐわかりますが、「3」や「4」を知らせるメッセージボックスが 出た場合、表示がおかしくなってしまいます。理由は考えてみてください。
BOOL MyStoneDraw(HDC hdc) { int i, j; HBRUSH hBrush, hOldBrush; for (i = 0; i < 15; i++) { for (j = 0; j < 15; j++) { if (ban[i][j] != 0) { if (ban[i][j] == 1) { hBrush = (HBRUSH)GetStockObject(BLACK_BRUSH); hOldBrush = (HBRUSH)SelectObject(hdc, hBrush); } if (ban[i][j] == 2) { hBrush = (HBRUSH)GetStockObject(WHITE_BRUSH); hOldBrush = (HBRUSH)SelectObject(hdc, hBrush); } MyCircle(hdc, i, j, STONESIZE); SelectObject(hdc, hOldBrush); } } } return TRUE; } int Is5(HWND hWnd, int x, int y) { int nCount = 1, nJibun, i = 1; char szSashite[8], szBuf[32]; if (bSente) { nJibun = 1; strcpy(szSashite, "先手"); } else { nJibun = 2; strcpy(szSashite, "後手"); } while (x - i >= 0) { if (ban[x - i][y] == nJibun) { nCount++; i++; } else break; } i = 1; while (x + i < 15) { if (ban[x + i][y] == nJibun) { nCount++; i++; } else break; } if (nCount == 5) { wsprintf(szBuf, "%sの勝ち!", szSashite); MessageBox(hWnd, szBuf, "5連", MB_OK); return 1; } else if (nCount > 5) { wsprintf(szBuf, "%sの反則負け", szSashite); MessageBox(hWnd, szBuf, "多連", MB_OK); return 0; } nCount = 1, i = 1; while (y - i >= 0) { if (ban[x][y - i] == nJibun) { nCount++; i++; } else break; } i = 1; while (y + i < 15) { if (ban[x][y + i] == nJibun) { nCount++; i++; } else break; } if (nCount == 5) { wsprintf(szBuf, "%sの勝ち!", szSashite); MessageBox(hWnd, szBuf, "5連", MB_OK); return 1; } else if (nCount > 5) { wsprintf(szBuf, "%sの反則負け", szSashite); MessageBox(hWnd, szBuf, "多連", MB_OK); return 0; } nCount = 1; i = 1; while (x - i >= 0 && y - i >= 0) { if (ban[x - i][y - i] == nJibun) { nCount++; i++; } else break; } i = 1; while(x + i < 15 && y + i < 15) { if (ban[x + i][y + i] == nJibun) { nCount++; i++; } else break; } if (nCount == 5) { wsprintf(szBuf, "%sの勝ち!", szSashite); MessageBox(hWnd, szBuf, "5連", MB_OK); return 1; } else if (nCount > 5) { wsprintf(szBuf, "%sの反則負け", szSashite); MessageBox(hWnd, szBuf, "多連", MB_OK); return 0; } nCount = 1, i = 1; while (x - i >= 0 && y + i < 15) { if (ban[x - i][y + i] == nJibun) { nCount++; i++; } else break; } i = 1; while (x + i < 15 && y - i >= 0) { if (ban[x + i][y - i] == nJibun) { nCount++; i++; } else break; } if (nCount == 5) { wsprintf(szBuf, "%sの勝ち!", szSashite); MessageBox(hWnd, szBuf, "5連", MB_OK); return 1; } else if (nCount > 5) { wsprintf(szBuf, "%sの反則負け", szSashite); MessageBox(hWnd, szBuf, "多連", MB_OK); return 0; } return -1; }これらの関数に変更はありません。
int Is4(HWND hWnd) //4になっていないか調べる { int i, j, k, wa = 0, nCount0 = 0, nCount4 = 0, nJibunwa; BOOL bLoop = TRUE; if (bSente) nJibunwa = 4; else nJibunwa = 8; for (i = 0; i < 11; i++) { for (j = 0; j < 15; j++) { nCount0 = 0; wa = 0; for (k = 0; k < 5; k++) { if (ban[i + k][j] == 0) { nCount0++; } wa = wa + ban[i + k][j]; } if (nCount0 == 1 && wa == nJibunwa) { nCount4++; bLoop = FALSE; break; } } if (bLoop != TRUE) break; } bLoop = TRUE; for (i = 0; i < 15; i++) { for (j = 0; j < 11; j++) { nCount0 = 0; wa = 0; for (k = 0; k < 5; k++) { if (ban[i][j + k] == 0) nCount0++; wa += ban[i][j + k]; } if (nCount0 == 1 && wa == nJibunwa) { nCount4++; bLoop = FALSE; break; } } if (bLoop != TRUE) break; } bLoop = TRUE; for (i = 0; i < 11; i++) { for (j = 0; j < 11; j++) { nCount0 = 0; wa = 0; for (k = 0; k < 5; k++) { if (ban[i + k][j + k] == 0) nCount0++; wa += ban[i + k][j + k]; } if (nCount0 == 1 && wa == nJibunwa) { nCount4++; bLoop = FALSE; break; } } if (bLoop != TRUE) break; } bLoop = TRUE; for (i = 4; i < 15; i++) { for (j = 0; j < 11; j++) { nCount0 = 0; wa = 0; for (k = 0; k < 5; k++) { if (ban[i - k][j + k] == 0) nCount0++; wa += ban[i - k][j + k]; } if (nCount0 == 1 && wa == nJibunwa) { nCount4++; bLoop = FALSE; break; } } if (bLoop != TRUE) break; } return nCount4; }「4」を判定し、その数を返す関数です。
変数の名前付けがへんてこなのでわかりにくいと思いますが、 waは「調べる区間でのban[x][y]の和」です。ban[x][y]には先手なら1,後手なら2, 空きなら0が代入されています。
nCount0は「調べる区間でのban[x][y]に0が代入されている数」です。
nCount4は「4」の数です。
nJibunwaはwaがこの値になったら「4」が出来ているという値です。 先手の検査中であれば調べる区間のban[x][y]の合計は4,後手なら8ということになります。
さて、次がかなり荒っぽいのですが碁盤を片端から調べていきます。
まずは水平方向です。
ban[0][0]からban[4][0]について、この和を求めます。もし「4」が出来ていればnCount4を1増やします。 「4」を発見した場合はループを抜けてこの方向の検査を終了します。
次にban[0][1]からban[4][1]についても、同様に検査します。
次はban[0][2]からban[4][2]です。
...
というように検査を進めます。同じ方向に「4」が同時に2つ以上できることはあり得ないので 「4」を見つけたらその方向での検査をやめます。(相手とグルになって意図的に作ることは出来ます。 「4」が出来ても相手がこれを止めず、さらに自分も「5」にして勝たない場合など・・)
他の方向についても同様に検査します。この場合i,jの範囲に注意してください。全部の方向について プログラムを書いてからエラーが見つかっても修正が面倒なので、1つの方向について プログラムが出来たらそのテストを行ってみたほうがよいようです。
また、「4」が見つかってループを抜けるときはgotoを使った方が簡単ですが、ここではあえて 面倒くさい方法をとっています。それと、当たり前ですがnCount0やwaを適切なときに0にすることを 忘れないでください(疲れてくると、こんな初歩的なミスを犯すこともよくあります)。
int Is3(HWND hWnd) { int i, j, k, nCount0 = 0, nCount3 = 0, wa = 0, nJibunwa, nJibun, nAite; BOOL bLoop = TRUE, bTome4 = FALSE; if (bSente) { nJibunwa = 3; nJibun = 1; nAite = 2; } else { nJibunwa = 6; nJibun = 2; nAite = 1; } for (i = 0; i < 10; i++) { for (j = 0; j < 15; j++) { nCount0 = 0; wa = 0; if (ban[i][j] == 0 && ban[i + 5][j] == 0) { for (k = 1; k <= 4; k++) { wa += ban[i + k][j]; if (ban[i + k][j] == 0) nCount0++; } if (nCount0 == 1 && wa == nJibunwa) { if (i + 6 < 15) { if (ban[i + 6][j] == nJibun) { bTome4 = TRUE; } } if (i - 1 > 0) { if (ban[i - 1][j] == nJibun) { bTome4 = TRUE; } } if (!bTome4) { nCount3++; bLoop = FALSE; break; } } } } if (bLoop != TRUE) break; } bLoop = TRUE; bTome4 = FALSE; for (i = 0; i < 15; i++){ for (j = 0; j < 10; j++) { nCount0 = 0; wa = 0; if (ban[i][j] == 0 && ban[i][j + 5] == 0) { for (k = 1; k <= 4; k++) { wa += ban[i][j + k]; if (ban[i][j + k] == 0) nCount0++; } if (nCount0 == 1 && wa == nJibunwa) { if (j + 6 < 15) { if (ban[i][j + 6] == nJibun) { bTome4 = TRUE; } } if (j - 1 > 0) { if (ban[i][j - 1] == nJibun) { bTome4 = TRUE; } } if (!bTome4) { nCount3++; bLoop = FALSE; break; } } } } if (bLoop != TRUE) break; } bLoop = TRUE; for (i = 0; i < 10; i++) { for (j = 0; j < 10; j++) { nCount0 = 0; wa = 0; if (ban[i][j] == 0 && ban[i + 5][j + 5] == 0) { for (k = 1; k <= 4; k++) { wa += ban[i + k][j + k]; if (ban[i + k][j + k] == 0) nCount0++; } if (nCount0 == 1 && wa == nJibunwa) { if (i + 6 < 15 && j + 6 < 15) { if (ban[i + 6][j + 6] == nJibun) { bTome4 = TRUE; } } if (i - 1 > 0 && j - 1 > 0) { if (ban[i - 1][j - 1] == nJibun) { bTome4 = TRUE; } } if (!bTome4) { nCount3++; bLoop = FALSE; break; } } } } if (bLoop != TRUE) break; } bLoop = TRUE; for (i = 5; i < 15; i++) { for (j = 0; j < 10; j++) { nCount0 = 0; wa = 0; if (ban[i][j] == 0 && ban[i - 5][j + 5] == 0) { for (k = 1; k <= 4; k++) { wa += ban[i - k][j + k]; if (ban[i - k][j + k] == 0) nCount0++; } if (nCount0 == 1 && wa == nJibunwa) { if (i - 6 > 0 && j + 6 < 15) { if (ban[i - 6][j + 6] == nJibun) { bTome4 = TRUE; } } if (j - 1 > 0) { if (ban[i + 1][j - 1] == nJibun) { bTome4 = TRUE; } } if (!bTome4) { nCount3++; bLoop = FALSE; break; } } } } if (bLoop != TRUE) break; } return nCount3; }「3」を判定してその数を返す関数です。
「4」の時と同じです。条件がちょっと複雑になっています。 「3の法則」に従って「3」を見つけた場合、これが 最初に説明した「止め4」の一部でないかを検査します。「止め4」でないときに 初めてnCount3を1増やします。
さて、ここでは、「止め4」を調べるのに6の区間の外側にさらに自分の石がないかを 調べていますが、これで完璧かどうかは不明です。もしかすると不十分かも知れません。 (だめな場合があれば教えてください。)
一応これで、「43」や「44」も判定できます。「43」や「44」を発見しても 直ちに勝ちとせず、メッセージボックスを出して最後まで続けるかどうかを尋ねています (SetStone関数のところで)。
いろいろ試してみて、誤判定がないか確認してみてください。(ここでは五目並べの アルゴリズムを調べるのが目的ではないのであまり深く追求しません)
Update 08/Jan/2002 By Y.Kumei