「 サンプル・プログラムは Python3 で実装して Git hub に置いてある☆
説明が分からなければ 実行してみろだぜ☆」
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
「 囲碁と同じ 19x19 の盤を使うが、他の自然数でも遊べる☆」
# 盤
. [.]
. .
. .
「 いきなり 19x19 だと難しいので、小さな 2x3 の盤で説明する☆」
「 盤には 箱 を置けるものとする☆
赤枠とか レッドゾーンとか 箱とか 好きなように呼べだぜ☆
上図では 右上のマスに 箱の印を付けている☆」
# 四角形の例1
. [.]
. .
# 四角形の例2
. [.]
. .
. .
# 四角形の例3
. . [.]
. . .
# 四角形の例4
. . [.]
. . .
. . .
「 盤に置ける四角形 として認められているのは、次の2条件を満たすものだぜ☆
* 右上の角が箱を踏んでいる
* 左上、右下、左下の角は箱を踏んでいない
」
「 この 盤に置ける四角形 をたくさん造れる盤を探せだぜ☆ ルールはこれだけだぜ☆」
# 盤
. [.]
. .
. .
# 四角形1
<.> <.>
<.> <.>
. .
# 四角形2
<.> <.>
. .
<.> <.>
# 盤
. [.]
<.> <.>
<.> <.>
. [.]
. .
. .
Succeed : 2
Failed : 1
total : 3
Rate : 0.6667
Info : Finished.
「 だから結果は 成功2、失敗1 で レート 0.6667 と表示されるんだぜ☆」
from lib.calculator import Calculator
def is_red_zone(x, y):
"""
右上の足だけが踏めるマス。
"""
return x == y
calculator = Calculator(is_red_zone)
calculator.show_table()
calculator.calculate()
print("Info : Finished.")
「 プレイヤーができることは is_red_zone(x, y) 関数の戻り値を True か False か指定することだけだぜ☆」
return x == y
. . . . . . . . . . . . . . . . . . [.]
. . . . . . . . . . . . . . . . . [.] .
. . . . . . . . . . . . . . . . [.] . .
. . . . . . . . . . . . . . . [.] . . .
. . . . . . . . . . . . . . [.] . . . .
. . . . . . . . . . . . . [.] . . . . .
. . . . . . . . . . . . [.] . . . . . .
. . . . . . . . . . . [.] . . . . . . .
. . . . . . . . . . [.] . . . . . . . .
. . . . . . . . . [.] . . . . . . . . .
. . . . . . . . [.] . . . . . . . . . .
. . . . . . . [.] . . . . . . . . . . .
. . . . . . [.] . . . . . . . . . . . .
. . . . . [.] . . . . . . . . . . . . .
. . . . [.] . . . . . . . . . . . . . .
. . . [.] . . . . . . . . . . . . . . .
. . [.] . . . . . . . . . . . . . . . .
. [.] . . . . . . . . . . . . . . . . .
[.] . . . . . . . . . . . . . . . . . .
Succeed : 1938
Failed : 27303
total : 29241
Rate : 0.0663
Info : Finished.
「 結果は 0.0663 だぜ☆ このレートが1に近づくように競う☆」
return x == y and 9 < x and 9 < y
. . . . . . . . . . . . . . . . . . [.]
. . . . . . . . . . . . . . . . . [.] .
. . . . . . . . . . . . . . . . [.] . .
. . . . . . . . . . . . . . . [.] . . .
. . . . . . . . . . . . . . [.] . . . .
. . . . . . . . . . . . . [.] . . . . .
. . . . . . . . . . . . [.] . . . . . .
. . . . . . . . . . . [.] . . . . . . .
. . . . . . . . . . [.] . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
Succeed : 1788
Failed : 27453
total : 29241
Rate : 0.0611
Info : Finished.
return x == y and 0 < x and 0 < y
. . . . . . . . . . . . . . . . . . [.]
. . . . . . . . . . . . . . . . . [.] .
. . . . . . . . . . . . . . . . [.] . .
. . . . . . . . . . . . . . . [.] . . .
. . . . . . . . . . . . . . [.] . . . .
. . . . . . . . . . . . . [.] . . . . .
. . . . . . . . . . . . [.] . . . . . .
. . . . . . . . . . . [.] . . . . . . .
. . . . . . . . . . [.] . . . . . . . .
. . . . . . . . . [.] . . . . . . . . .
. . . . . . . . [.] . . . . . . . . . .
. . . . . . . [.] . . . . . . . . . . .
. . . . . . [.] . . . . . . . . . . . .
. . . . . [.] . . . . . . . . . . . . .
. . . . [.] . . . . . . . . . . . . . .
. . . [.] . . . . . . . . . . . . . . .
. . [.] . . . . . . . . . . . . . . . .
. [.] . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
Succeed : 1956
Failed : 27285
total : 29241
Rate : 0.0669
Info : Finished.
. . . .
. . . .
. . . .
. . . .
「 4x4 ぐらいのサイズなら ブルートフォース・サーチ で解けるんじゃないか☆?」
「 自分の頭で解かなければ 将棋の観戦記者 に怒られるぜ☆」
# x == 3 and y == 3
. . . [.]
. . . .
. . . .
. . . .
Succeed : 9
Failed : 27
total : 36
Rate : 0.2500
Info : Finished.
「 右上は 箱 にするのが鉄板だろ☆
これを上回る 箱 の置き方は 果たして存在するのか☆?」
「 箱を置くと、 置けなくなる四角形の数 より 置けるようになる四角形の数 が多くなるマスに
置いたらいいんだぜ☆」
# (x == 3 and y == 3) or (x == 2 and y == 3)
. . [.] [.]
. . . .
. . . .
. . . .
Succeed : 12
Failed : 24
total : 36
Rate : 0.3333
Info : Finished.
# (x != 0 and y == 3) or (x == 3 and y != 0)
. [.] [.] [.]
. . . [.]
. . . [.]
. . . .
Succeed : 13
Failed : 23
total : 36
Rate : 0.3611
# (x != 0 and y % 2 == 1) or (x % 2 == 1 and y != 0)
. [.] [.] [.]
. [.] . [.]
. [.] [.] [.]
. . . .
Succeed : 10
Failed : 26
total : 36
Rate : 0.2778
# return x % 2 == 1 and y % 2 == 1
. [.] . [.]
. . . .
. [.] . [.]
. . . .
Succeed : 9
Failed : 27
total : 36
Rate : 0.2500
# (y * 4 + x) % 2 == 1
. [.] . [.]
. [.] . [.]
. [.] . [.]
. [.] . [.]
Succeed : 0
Failed : 36
total : 36
Rate : 0.0000
「 ナナメは x軸とy軸の両方が協力して作るものだぜ☆
片方の軸だけ がんばっても ナナメ は作れない☆
この感覚は 行列 で遊ぶと見に付く☆」
# (x + y) % 2 == 1
[.] . [.] .
. [.] . [.]
[.] . [.] .
. [.] . [.]
Succeed : 0
Failed : 36
total : 36
Rate : 0.0000
「 あっ、簡単に ナナメ になったぜ☆! そして ファンブルした☆」
# (x + y) % 2 == 0 and 2 < (x+y)
. [.] . [.]
. . [.] .
. . . [.]
. . . .
Succeed : 13
Failed : 23
total : 36
Rate : 0.3611
「 対角線を挟んで右上半分に ナナメ に置いても 13個かだぜ☆」
「 もう ナナメ を使いこなしている……☆
わたしのアドバイスは優秀……☆」
. [.] . [.]
. . [.] [.]
. . . [.]
. . . .
Succeed : 14
Failed : 22
total : 36
Rate : 0.3889
「 細かい……☆ 常に他人のアイデアより1点多めに乗せてくる 羽生善治みたいな勝ち方をするよな☆」
# 3 < (x+y)
. [.] [.] [.]
. . [.] [.]
. . . [.]
. . . .
Succeed : 15
Failed : 21
total : 36
Rate : 0.4167
「 じゃあ コンピューターの使い時かだぜ☆?
人の頭は もう十分に使っただろう……☆」
「 問題をコンピューターに解かせるために、必要になる下準備を説明する☆」
# No. 0
. . . .
. . . .
. . . .
. . . .
# No. 1
. . . .
. . . .
. . . .
[.] . . .
# No. 2
. . . .
. . . .
. . . .
. [.] . .
# No. 3
. . . .
. . . .
. . . .
[.] [.] . .
「 例えば このように すべてのケースを網羅する表を作りたいわけだぜ☆
完全解析するなら 2 の 16乗で 65536 パターンある☆」
「 それ以外に、完全解析ではなく そこそこ いい感じの答えが出ればいいケースなら
近似計算や、統計的確率 など 使える道具が増えていき、機械学習の活躍の分野が広がる☆」
「 さっきの 4x4の練習では 10パターン調べただけで 完全攻略法か☆?と 期待できる解法を見つけているが、
それが 完全攻略法かどうかは 検証していないぜ☆ 多分そう思う、というだけで☆」
# x == y
. . . [.]
. . [.] .
. [.] . .
[.] . . .
# 0 == y-x
. . . [.]
. . [.] .
. [.] . .
[.] . . .
「 ところで x == y
と 0 == y-x
は同じことを言っているのが お分かりいただけるであろうか☆?
両辺に -x を足しただけだが、これを 移項 という☆
0 == y-x
の方で 0 が出てきたが、この 0 は誤差を表している☆
あとで 少しの誤差ぐらい許してくれたっていいじゃないか、と気が変わったときは 1 > abs(y-x) といった書き方に 書き換えやすいので、
0 == y-x
の形を使っていくことにするぜ☆」
「 じゃあ 0~65536 の 65536の全パターンに対応した式は どのように立てるだろうか☆?」
# 0b1000010000100001
. . . [.]
. . [.] .
. [.] . .
[.] . . .
# x=0, y=0
. . . .
. . . .
. . . .
[.] . . .
# y // 4 + x
12 13 14 15
8 9 10 11
4 5 6 7
0 1 2 3
「 x は列、y は行で、 1行は4列だから、
y//4+x
で上図のように 番地 を振ることができると思う☆」
# 0b100 == 1 << 2
「 番地は、立てたい桁 に対応する☆
例えば 2進数 100 は 2番地 に対応するが、1の位を0桁目として数え始めて 2桁目に 1 を立てることに対応する☆」
# 100 == 0b1000010000100001 & 0b100
「 2桁目が 0 か 1 かだけ調べたいときは ANDマスク の出番だぜ☆
2桁目以外を 0 に落としてくれるので 100 か 0 かの比較になる☆」
. . . [.]
. . [.] .
. [.] . .
[.] . . .
def is_red_zone(x, y):
"""
右上の足だけが踏めるマス。
"""
address = (y*4)+(x % 4)
binary = 1 << address
return (0b1000010000100001 & binary) == binary
from lib.calculator import Calculator
bitboard = 0b1000010000100001
def is_red_zone(x, y):
"""
右上の足だけが踏めるマス。
"""
address = (y*4)+(x % 4)
binary = 1 << address
return (bitboard & binary) == binary
calculator = Calculator(4, 4)
for i in range(0, 65536):
bitboard = i
calculator.set_red_zone(is_red_zone)
print("#{}".format(i))
calculator.show_table()
calculator.calculate()
calculator.show_report()
print("Info : Finished.")
# 前略
#3459
. . . .
[.] . [.] [.]
. . . [.]
[.] [.] . .
#3460
. . . .
[.] . [.] [.]
. . . [.]
. . [.] .
#3461
. . . .
[.] . [.] [.]
. . . [.]
[.] . [.] .
#3462
. . . .
[.] . [.] [.]
. . . [.]
. [.] [.] .
#3463
. . . .
[.] . [.] [.]
. . . [.]
[.] [.] [.] .
# 後略
「 きふわらべが ビットボードを作ってくれたので
ループで回せるようになったぜ☆」
Succeed : 16
Failed : 20
total : 36
Rate : 0.4444
Info : Finished.
「 わたしは 答えを見てしまったので、考えたかったら お前らで考えろだぜ☆」
「 まったく分からん☆
もっと ごちゃごちゃ した図形なのか、
それとも もっと 答えはシンプルなのか☆? まずは その方向性からだぜ☆」
「 これが このゲームの必勝法なのか 気になるよな☆
19路盤でも試してみようぜ☆?」
「 止めておいた方がいい☆
ブルートフォース・サーチなんで☆」
「 攻略法は見えたわけで、直接 答えを打ち込んでみようぜ☆?」
「 あれっ☆? Python3 動かね☆
2進数361桁は 桁数が多すぎとか あるのかだぜ☆?」
「 5路盤でも Python3 動かね☆
2進数25桁で ダメとか あるのかだぜ☆?」
「 あっ、マジックナンバーを変えてなかったぜ☆ 変数に修正☆」
「 うーん、いい方法ではないか、ということしか分からないな☆
盤がでかいと 調べきれないぜ☆」
「 4路盤では 65536 パターンだったが、
5路盤では 33554432 パターン、
19路盤では 4697085165547666455778961193578674054751365097816639741414581943064418050229216886927397996769537406063869952 パターンになるぜ☆」
「 このゲームは、正解が1個だけで それを当てるしかないのか、
それとも 上位5%ぐらいに入る良い回答を当てに行くのか、
それとも 半分は正解なのか、
のような 分布によって 攻略に向いているアルゴリズムは変わってくるが……☆」
「 多分 正解は 1個 だけ頭1つ抜けていて、
同率2位が少し、同率3位がもうちょっと多い、みたいな ひし形の形をしているのよ」
「 じゃあ 乱択アルゴリズム で ひし形の上半分は 当てに行けるな☆」
「 すでに出た 必勝っぽい攻略法を使えば 上位5% ぐらい当てに行けそうなゲームじゃないか これ☆?」
「 だったら 乱択アルゴリズム と わたしたち で どっちが勝つか やろうぜ☆?」
import random
from lib.calculator import Calculator
# Settings.
width = 5
height = 5
num_of_states = 2 ** (width*height)
def is_red_zone(x, y):
"""
右上の足だけが踏めるマス。
"""
address = (y*height)+(x % width)
binary = 1 << address
return (bitboard & binary) == binary
# Clear.
bitboard = 0
calculator = Calculator(width, height)
best_sum = {"bitboard": 0, "succeed": 0, "failed": 0, "total": 0, "rate": 0}
# 試行回数
try_count = 2 ** 16
if num_of_states < try_count:
try_count = num_of_states
for i in range(0, try_count):
if i % 5000 == 0:
print("Progress: {}/{} ({:>3.0f}%)".format(i,
try_count, i/try_count*100))
# Randomized algorithm.
bitboard = random.randint(0, num_of_states-1)
calculator.set_red_zone(is_red_zone)
# print("#{}".format(bitboard))
# calculator.show_table()
calculator.calculate()
sum = calculator.get_report_sum()
if best_sum["rate"] < sum["rate"]:
best_sum = {
"bitboard": bitboard,
"succeed": sum["succeed"],
"failed": sum["failed"],
"total": sum["total"],
"rate": sum["rate"]
}
# Result.
print("Bitboard : {}".format(best_sum["bitboard"]))
print("Succeed : {}".format(best_sum["succeed"]))
print("Failed : {}".format(best_sum["failed"]))
print("total : {}".format(best_sum["total"]))
print("Rate : {:>.4f}".format(best_sum["rate"]))
print("Info : Finished.")
Bitboard : 25698432
Succeed : 33
Failed : 67
total : 100
Rate : 0.3300
「 なんか ピッタリ 3分の1 というキリのいい数字を出してきてるぜ☆
きっちり有効桁数2桁の Python3 わらう☆」
「 まだ負けたと決まったわけではないぜ☆
ビットボードを表示してくれだぜ☆」
. . . [.] [.]
. . . . [.]
. . . [.] .
. . [.] . .
. . . . .
「 これが答えだと言われても 納得してしまう かっこよさ がある☆」
. . . [.] [.]
. . . . [.]
. . . . .
. . . . .
. . . . .
Succeed : 33
Failed : 67
total : 100
Rate : 0.3300
「 もう1回 コンピューターに反撃のチャンスをやろうかだぜ☆
乱択アルゴリズムは 回数を増やして 良いとこ取りすれば より良い答えが出る☆」
Bitboard : 30146816
. . [.] [.] [.]
. . . [.] [.]
. . . . .
. . . [.] .
. . . . .
Succeed : 36
Failed : 64
total : 100
Rate : 0.3600
. . [.] [.] [.]
. . . [.] [.]
. . . . [.]
. . . . .
. . . . .
Succeed : 41
Failed : 59
total : 100
Rate : 0.4100
「 気持ち3分の1ぐらいの右上角を詰める戦略は 最強なんじゃないか☆?」
Bitboard : 30040320
. . [.] [.] [.]
. . [.] . [.]
. . . [.] [.]
. . . [.] .
. . . . .
Succeed : 37
Failed : 63
total : 100
Rate : 0.3700
「 大きな分岐点に狙いを付けて やってみて、こんなこと やっていても ダメだというルールを見つけることができるからだろ☆
ダメなものの 処分が早い☆」
Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。
また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?
コメント