オセロの全手順を出力する

オセロの全手順を出力

オセロの全手順を出力

オセロの全手順を出力するシェルスクリプトとCソースを作りました。というか、AIに作らせました。

https://hasera.net/othello/archive/search-all.zip

・初手は f5 固定

・MAX_DEPTH が探索の深さで、初手 f5 を打った状態からの深さなので、MAX_DEPTH + 1 手までの全手順を出力します。

シェルスクリプト

#!/bin/bash

# オセロの全手順出力
# 初手 f5 固定
# MAX_DEPTH + 1手まで
# パスは手数にも文字列にも含めない
# 終局したら、その時点で探索終了
#
# 出力例:
# f5d6c3d3c4

# ——————————–
# 設定
# ——————————–

MAX_DEPTH=2

declare -a board

# ——————————–
# 初期盤面
#
# d4 = W
# e4 = B
# d5 = B
# e5 = W
# ——————————–

init_board() {
for i in {0..63}; do
board[$i]=”.”
done

board[27]=”W” # d4
board[28]=”B” # e4
board[35]=”B” # d5
board[36]=”W” # e5
}

# ——————————–
# 座標文字
# ——————————–

files=(a b c d e f g h)

coord() {
local r=$1
local c=$2

echo -n “${files[$c]}$((r+1))”
}

# ——————————–
# 合法手判定
# ——————————–

legal() {
local r=$1
local c=$2
local p=$3

local o

if [[ “$p” == “B” ]]; then
o=”W”
else
o=”B”
fi

# 空きマスでなければ不可
[[ “${board[$((r*8+c))]}” != “.” ]] && return 1

local dr dc rr cc n

for dr in -1 0 1; do
for dc in -1 0 1; do

[[ $dr -eq 0 && $dc -eq 0 ]] && continue

rr=$((r+dr))
cc=$((c+dc))
n=0

# 相手石が連続しているか
while ((rr>=0 && rr<8 && cc>=0 && cc<8)) &&
[[ “${board[$((rr*8+cc))]}” == “$o” ]]; do

n=$((n+1))
rr=$((rr+dr))
cc=$((cc+dc))
done

# 相手石の先に自分の石があれば合法
if ((n>0)) &&
((rr>=0 && rr<8 && cc>=0 && cc<8)) &&
[[ “${board[$((rr*8+cc))]}” == “$p” ]]; then

return 0
fi

done
done

return 1
}

# ——————————–
# 着手＋石を反転
# ——————————–

put() {
local r=$1
local c=$2
local p=$3

local o

if [[ “$p” == “B” ]]; then
o=”W”
else
o=”B”
fi

board[$((r*8+c))]=”$p”

local dr dc rr cc n

for dr in -1 0 1; do
for dc in -1 0 1; do

[[ $dr -eq 0 && $dc -eq 0 ]] && continue

rr=$((r+dr))
cc=$((c+dc))
n=0

# 相手石を数える
while ((rr>=0 && rr<8 && cc>=0 && cc<8)) &&
[[ “${board[$((rr*8+cc))]}” == “$o” ]]; do

n=$((n+1))
rr=$((rr+dr))
cc=$((cc+dc))
done

# 自分の石で挟めている
if ((n>0)) &&
((rr>=0 && rr<8 && cc>=0 && cc<8)) &&
[[ “${board[$((rr*8+cc))]}” == “$p” ]]; then

# 挟んだ相手石を反転
rr=$((r+dr))
cc=$((c+dc))

while [[ “${board[$((rr*8+cc))]}” == “$o” ]]; do

board[$((rr*8+cc))]=”$p”

rr=$((rr+dr))
cc=$((cc+dc))
done
fi

done
done
}

# ——————————–
# 合法手が1つでもあるか
# ——————————–

has_legal_move() {
local player=$1
local r c

for r in {0..7}; do
for c in {0..7}; do

if legal “$r” “$c” “$player”; then
return 0
fi

done
done

return 1
}

# ——————————–
# 再帰探索
# ——————————–

search() {
local depth=$1
local player=$2
local sequence=$3

local next

if [[ “$player” == “B” ]]; then
next=”W”
else
next=”B”
fi

# ——————————–
# 現在のプレイヤーの合法手を探索
# ——————————–

local found=0
local r c m

for r in {0..7}; do
for c in {0..7}; do

if legal “$r” “$c” “$player”; then

found=1

# 最大手数に到達したら、
# この手順を出力して終了
if (( depth == MAX_DEPTH )); then

echo “${sequence}$(coord “$r” “$c”)”

continue
fi

# 盤面保存
local -a saved
saved=(“${board[@]}”)

# 着手
put “$r” “$c” “$player”

# 座標追加
m=”${files[$c]}$((r+1))”

# 次の手
search \
$((depth+1)) \
“$next” \
“${sequence}${m}”

# 盤面復元
board=(“${saved[@]}”)

fi

done
done

# ——————————–
# 合法手がない
# ——————————–

if (( found == 0 )); then

# 相手にも合法手がない
# → 完全に終局
if ! has_legal_move “$next”; then

echo “$sequence”
return
fi

# ——————————–
# 相手には合法手がある
# → パス
#
# パスなので
# depth も sequence も変更しない
# ——————————–

search “$depth” “$next” “$sequence”
fi
}

# ——————————–
# メイン
# ——————————–

init_board

# 黒の初手 f5
put 4 5 B

# 白の2手目から探索
search 1 W “f5”

Cソース

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BOARD_SIZE 8

char board[64];

const char files[] = “abcdefgh”;

/*
* Othello 全手順出力
*
* 初手 f5 固定
* 最大 depth + 1 手まで
*
* 例:
* ./othello 2
*
* 出力:
* f5d6c3
* f5d6c4
* …
*
* パスは手数にも文字列にも含めない。
* 終局したら、その時点で探索終了。
*/

/* ——————————–
* 座標文字
* ——————————– */

void coord(int r, int c, char *buf)
{
buf[0] = files[c];
buf[1] = ‘1’ + r;
buf[2] = ‘\0’;
}

/* ——————————–
* 初期盤面
*
* d4 = W
* e4 = B
* d5 = B
* e5 = W
* ——————————– */

void init_board(void)
{
int i;

for (i = 0; i < 64; i++)
board[i] = ‘.’;

board[27] = ‘W’; /* d4 */
board[28] = ‘B’; /* e4 */
board[35] = ‘B’; /* d5 */
board[36] = ‘W’; /* e5 */
}

/* ——————————–
* 合法手判定
* ——————————– */

int legal(int r, int c, char player)
{
char opponent;
int dr, dc;
int rr, cc;
int n;

opponent = (player == ‘B’) ? ‘W’ : ‘B’;

/* 空きマスでなければ不可 */
if (board[r * 8 + c] != ‘.’)
return 0;

for (dr = -1; dr <= 1; dr++) {
for (dc = -1; dc <= 1; dc++) {

if (dr == 0 && dc == 0)
continue;

rr = r + dr;
cc = c + dc;
n = 0;

/* 相手石が連続しているか */
while (rr >= 0 && rr < 8 &&
cc >= 0 && cc < 8 &&
board[rr * 8 + cc] == opponent) {

n++;
rr += dr;
cc += dc;
}

/* 相手石の先に自分の石があれば合法 */
if (n > 0 &&
rr >= 0 && rr < 8 &&
cc >= 0 && cc < 8 &&
board[rr * 8 + cc] == player) {

return 1;
}
}
}

return 0;
}

/* ——————————–
* 着手＋石を反転
* ——————————– */

void put(int r, int c, char player)
{
char opponent;
int dr, dc;
int rr, cc;
int n;

opponent = (player == ‘B’) ? ‘W’ : ‘B’;

board[r * 8 + c] = player;

for (dr = -1; dr <= 1; dr++) {
for (dc = -1; dc <= 1; dc++) {

if (dr == 0 && dc == 0)
continue;

rr = r + dr;
cc = c + dc;
n = 0;

/* 相手石を数える */
while (rr >= 0 && rr < 8 &&
cc >= 0 && cc < 8 &&
board[rr * 8 + cc] == opponent) {

n++;
rr += dr;
cc += dc;
}

/* 自分の石で挟めている */
if (n > 0 &&
rr >= 0 && rr < 8 &&
cc >= 0 && cc < 8 &&
board[rr * 8 + cc] == player) {

/* 最初の相手石へ戻る */
rr = r + dr;
cc = c + dc;

/* 挟んだ相手石を反転 */
while (rr >= 0 && rr < 8 &&
cc >= 0 && cc < 8 &&
board[rr * 8 + cc] == opponent) {

board[rr * 8 + cc] = player;

rr += dr;
cc += dc;
}
}
}
}
}

/* ——————————–
* 合法手が1つでもあるか
* ——————————– */

int has_legal_move(char player)
{
int r, c;

for (r = 0; r < 8; r++) {
for (c = 0; c < 8; c++) {

if (legal(r, c, player))
return 1;
}
}

return 0;
}

/* ——————————–
* 再帰探索
* ——————————– */

void search(int depth, char player, const char *sequence,
int max_depth)
{
char next;
int found = 0;
int r, c;

char new_sequence[1024];
char move[3];

next = (player == ‘B’) ? ‘W’ : ‘B’;

/* ——————————–
* 現在のプレイヤーの合法手を探索
* ——————————– */

for (r = 0; r < 8; r++) {
for (c = 0; c < 8; c++) {

if (!legal(r, c, player))
continue;

found = 1;

/*
* 最大手数に到達したら、
* この手順を出力して終了
*/
if (depth == max_depth) {

coord(r, c, move);

printf(“%s%s\n”, sequence, move);

continue;
}

/* 盤面保存 */
char saved[64];
memcpy(saved, board, sizeof(board));

/* 着手 */
put(r, c, player);

/* 座標追加 */
coord(r, c, move);

snprintf(new_sequence,
sizeof(new_sequence),
“%s%s”,
sequence,
move);

/* 次の手 */
search(depth + 1,
next,
new_sequence,
max_depth);

/* 盤面復元 */
memcpy(board, saved, sizeof(board));
}
}

/* ——————————–
* 合法手がない
* ——————————– */

if (!found) {

/*
* 相手にも合法手がない
* → 完全に終局
*/
if (!has_legal_move(next)) {

printf(“%s\n”, sequence);
return;
}

/*
* 相手には合法手がある
* → パス
*
* パスなので
* depth も sequence も変更しない
*/
search(depth,
next,
sequence,
max_depth);
}
}

/* ——————————–
* メイン
* ——————————– */

int main(int argc, char *argv[])
{
int max_depth;

if (argc != 2) {
fprintf(stderr,
“使い方: %s <探索深さ>\n”,
argv[0]);
return 1;
}

max_depth = atoi(argv[1]);

if (max_depth < 1) {
fprintf(stderr,
“探索深さは1以上を指定してください。\n”);
return 1;
}

init_board();

/* 黒の初手 f5 */
put(4, 5, ‘B’);

/* 白の2手目から探索 */
search(1, ‘W’, “f5”, max_depth);

return 0;
}

結果

2手までの全手順 3通り
3手までの全手順 14通り
4手までの全手順 61通り
5手までの全手順 349通り
6手までの全手順 2050通り
7手までの全手順 13773通り
8手までの全手順 97554通り
9手までの全手順 751330通り
10手までの全手順 6142855通り
11手までの全手順 53065220通り
12手までの全手順は 484974802通り

「60手までの全手順」も動きますが、最後まで動かすには余りにも莫大な時間がかかり、実質不可能だと思います。

月	火	水	木	金	土	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31