#概要
ガンホー的にはアウトだと思うのですが、やってみたので報告させていただきます
プログラミング楽しいですね
pythonは結構、書きやすいですね
消されたくないのと、計算時間から4*3マスで実現します。
#環境
Anaconda
python2
GPUのないCorei5第6世代NotePC
#方法
全探索を行います。
先人
https://www.nicovideo.jp/watch/sm34071597
はビームサーチを利用していますね
遺伝的アルゴリズムとかも入れれたらすごい面白そうです。
ただ、全探索は時間がかかるので無理がありそうです。
PCの問題かも知れませんが
#パズドラのアルゴリズムを実装
この方の方式を使わせていただきました
https://qiita.com/Nakatomo/items/03c074d9cdce2a0a0ee4
'''
配置変数 field[x][y]
左上 0
赤0
青1
緑2
黄3
紫4
回復5
落ちコン6以降
トスル
インスタンスをどんどん増やす形でいいかな？
クラス関数-------------------
移動によってどう配置が変化するか
ドロップ消去、コンボ数評価関数
落ちコン関数
状態グラフィック表示関数
'''
class Step:
def __init__(self,FirstField,X,Y):
self.field = FirstField
self.X = X
self.Y = Y
self.height = 3
self.width = 4
self.judge = [[0]*self.width for i in range(self.height)]
self.comboN = 0
self.Route =[ [X,Y] ]
self.ElseDrop = 6
def __repr__(self):
return str(self.Route)
def operation(self,direction):
'''
ドロップ移動方向
0
3 1
2
'''
if direction == 0:
if self.Y != 0:
hoge = self.field[self.Y][self.X]
self.field[self.Y][self.X] = self.field[self.Y-1][self.X]
self.field[self.Y-1][self.X] = hoge
self.Y = self.Y - 1
self.Route.append([self.X,self.Y])
return 1
else:
return 0
if direction == 2:
if self.Y != self.height-1:
hoge = self.field[self.Y][self.X]
self.field[self.Y][self.X] = self.field[self.Y+1][self.X]
self.field[self.Y+1][self.X] = hoge
self.Y = self.Y + 1
self.Route.append([self.X,self.Y])
return 1
else:
return 0
if direction == 3:
if self.X != 0:
hoge = self.field[self.Y][self.X]
self.field[self.Y][self.X] = self.field[self.Y][self.X-1]
self.field[self.Y][self.X-1] = hoge
self.X = self.X - 1
self.Route.append([self.X,self.Y])
return 1
else:
return 0
if direction == 1:
if self.X != self.width -1 :
hoge = self.field[self.Y][self.X]
self.field[self.Y][self.X] = self.field[self.Y][self.X+1]
self.field[self.Y][self.X+1] = hoge
self.X = self.X + 1
self.Route.append([self.X,self.Y])
return 1
else:
return 0
return 1
def disp(self): #表示
for i in range(self.height):
print(self.field[i])
def combo(self): #コンボ数計算ーコンボ後field計算
self.n = 0
self.judge = [[0]*self.width for i in range(self.height)]
#横列つながり
for j in range(self.height):
for i in range(1,self.width-1):
if self.field[j][i]== self.field[j][i-1]and \
self.field[j][i] ==self.field[j][i+1]:
hoge = max(self.judge[j][i-1],self.judge[j][i],self.judge[j][i+1])
#print('on1')
if hoge != 0:
self.judge[j][i-1] = hoge
self.judge[j][i]= hoge
self.judge[j][i+1] = hoge
else:
self.n = self.n + 1
self.judge[j][i-1] = self.n
self.judge[j][i]= self.n
self.judge[j][i+1] = self.n
#縦列つながり
for j in range(1,self.height-1):
for i in range(self.width):
if self.field[j][i]== self.field[j-1][i]and \
self.field[j][i] ==self.field[j+1][i]:
hoge = max(self.judge[j-1][i],self.judge[j][i],self.judge[j+1][i])
if hoge != 0:
self.judge[j-1][i] = hoge
self.judge[j][i]= hoge
self.judge[j+1][i] = hoge
else:
self.n = self.n + 1
self.judge[j-1][i] = self.n
self.judge[j][i]= self.n
self.judge[j+1][i] = self.n
self.comboN = self.comboN + self.n
def fall(self): #落ちコンが発生したときに上から降ろす：落ちコン 6 以降
for j in range(self.height):
for i in range(self.width):
if self.judge[j][i] != 0:
k= j
while True:
if k == 0:
self.field[k][i] = self.ElseDrop
self.ElseDrop = self.ElseDrop + 1
break
else:
self.field[k][i] = self.field[k-1][i]
k = k - 1
Step.disp() : field(ドロップ配置)を表示
Step.operation(m) : m= 0なら、上に移動 等 つかんだドロップを移動させる
Step.combo() :成立コンボ判定
Step.judge : 成立している場所を0以外にする変数
Step.fall() : コンボ成立ドロップを消し、上から落とす
計算時間簡略化のために、4×3マスで設計しています。
実装結果
#初期配置
#firstField = [[1,2,3,1],[1,2,1,2],[1,2,3,3]]
firstField = [[1,3,2,1],[1,2,1,2],[3,1,3,1]]
->
[1, 3, 2, 1]
[1, 2, 1, 2]
[3, 1, 3, 1]
step = Step(firstField,1,1) #(1,1)をつかんだ状態
step.operation(2) #下に移動
step.disp()
->
[1, 3, 2, 1]
[1, 1, 1, 2]
[3, 2, 3, 1]
step.combo()
step.fall()
step.disp()
->
[6, 7, 8, 1]
[1, 3, 2, 2]
[3, 2, 3, 1]
無駄な計算は有るかも知れませんが、正しく計算できている事がわかります。
#全探索
アルゴリズムは
全ての最初場所をつかむ場合のインスタンスを生成
↓
そのドロップを4方向全てに移動した場合のインスタンスをさらに増やす
↓
そのドロップを4方向全てに移動した場合のインスタンスをさらに増やす
・
・
・
ドロップの移動回数インスタンスの増加を繰り返す
ドロップの移動回数上限が来たら、全インスタンスに対し
コンボ成立、落ちコン処理を行い
最大のコンボ数のインスタンスを探し出す。
下のプログラムは、Allwayという配列にどんどんインスタンスを追加しています。
Nextステップには次のドロップ移動時に使うインスタンス番号を保存しています。
ただし、上端をつかんだ状態で上に動かす場合は不可能なので、そういった場合のインスタンスはAllwayに追加しません
Allway = []
NextStep = [] #次のステップで動作させるインスタンスの インデックス
for j in range(height):
for i in range(width):
Allway.append( copy.deepcopy(Step(firstField,i,j)))
Allway[i+j*width].combo()
Allway[i+j*width].fall()
NextStep.append(i+j*width)
#------------------動作させた場合を増やしていく
for loop in range(10):
f=len(NextStep)
for k in range(f):
for m in range(4):
Allway.append(copy.deepcopy(Allway[ NextStep[k] ]) ) #追加
end = len(Allway)-1 #追加したインスタンスに対し操作する
hoge = Allway[end].operation(m)
if hoge != 0:
NextStep.append(end) #新しく発生したものをNextStepに追加する
else: #移動しなかった場合削除する
del Allway[end]
del NextStep[0:f]
#生成したインスタンスに対し コンボ判定、落ちコンを計算
for k in range(len(Allway)):
m = 0
while True:
Allway[k].combo()
if Allway[k].comboN == m:
break
m=Allway[k].comboN
Allway[k].fall()
#最良値を出力ーーーーrepr に登録した Routeを出力させる
hogeMax = Allway[0].comboN
maxIndex = 0
for a in range(len(Allway)):
if hogeMax < Allway[a].comboN:
hogeMax = Allway[a].comboN
maxIndex = a
print(maxIndex)
print(hogeMax)
print(Allway[maxIndex].Route)
一応、検索できますが10回ドロップ移動させるだけで時間がすごいかかります（約2分：4×3マス）。
実行結果（5手まで）
#初期配置
[1, 3, 2, 1]
[1, 2, 1, 2]
[3, 1, 3, 1]
#計算結果 ルート
[[1, 1], [1, 2], [1, 1]]
#コンボ結果
[12, 13, 14, 11]
[6, 9, 10, 1]
[1, 7, 8, 1]
'1'でもう一コンボできますが、5手では実現できないようです。
10手までで実行すると
#初期配置
[1, 3, 2, 1]
[1, 2, 1, 2]
[3, 1, 3, 1]
#計算結果 ルート
[[3, 1], [2, 1], [1, 1], [1, 2], [0, 2], [0, 1], [1, 1], [1, 2], [2, 2]]
#コンボ結果
[11, 16, 17, 8]
[10, 14, 15, 7]
[9, 12, 13, 6]
全て消せてますね。縦に3つ並べる形になっていますね。
ただ、10手までの全探索でメモリ3G,5分かかります
まぁ、インスタンスが1.08G個生成されていたので仕方ない気がしますが
落としを使った方が手数が少なくてすむ場合の初期配置では
[4, 1, 1, 4]
[2, 3, 3, 2]
[3, 2, 2, 1]
Route
[[0, 1], [0, 2]]
2combo
コンボ後
[9, 12, 13, 14]
[6, 10, 11, 4]
[4, 7, 8, 2]
次は、高速化と探索方法を探していきたいです。