「世界初、来店不要のフルオーダーメイド靴」のプレスリリースを行いました。

20-3. vcoptでライツアウトを解く

やること

ライツアウト(lights out)というパズルがあります。ライトを消せ!的な意味です。

Lights Out - confetti - Apps on Google Play
A remake of the classic Lights Out game. Clicking a light will toggle its state and all its adjacent neighbour's light states as well. Turn off all the lights t...

例題1

マスをクリックすると、そのマスを含む十字型の5マスがひっくり返ります。マスをすべて消灯させればクリアです。

解答は一意に定まりませんが、最少手数の答えがこちらです。

同じマスを2回以上クリックすることには意味がないため、各マスとも「1回クリックする」か「クリックしない」の2択しかありません。よって解の組み合わせは225=約3000万通りあります。

今日は、このパズルをGA(遺伝的アルゴリズム)を用いて解いてみます。

解法

解の一つを見つける方法はこちらをご参照ください。5*5サイズは特別に難しいそうです。

ライツアウト攻略! - 人生ってそういうものなんだと思います
驚異のライツアウト解法ロジック
Puzzle DE Programming / ライツアウトの解法
Puzzle,パズル,プログラミング,解法

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net
Portable Scientific Python 2/3 32/64bit Distribution for Windows

vcoptの使い方についてはチュートリアルをご参照ください。

vcoptの仕様については最新の仕様書をご参照ください。本記事執筆時とは仕様が異なる場合があります。

考え方

長さ25の遺伝子配列を用意し、各遺伝子は0か1をとることにします。これを5*5の2次元配列にリサイズし、1をクリックするマスとしてプレイします。

評価関数では、プレイ後の盤面を見て「点灯しているマス(=1のマス)」の総数を返すことにします。このスコアが0に近づくように最適化を行います。

pip, import

まだvcoptをpipしていない場合はpipします。

pip install vcopt

必要なパッケージをimportします。

import numpy as np
import numpy.random as nr
from copy import deepcopy
from vcopt import vcopt

パズル問題

パズル問題は ‘-‘ と ‘#’ で表現します。’#’が点灯しているマスです。

#============================
# パズルの記述
#============================
lights = ['---#-',
          '---##',
          '--##-',
          '#-###',
          '##-##']

前処理でnumpy配列に変換し、パズルのサイズを取得します。

#============================
# パズルの変換
#============================
#変換
lights_tmp = []
for line in lights:
    line = line.replace('-', '0')
    line = line.replace('#', '1')
    lights_tmp.append(list(line))
lights = np.array(lights_tmp, dtype=int)
print('lights\n{}'.format(lights))

#サイズ
h, w = lights.shape
print('h, w\n{}, {}'.format(h, w ))
lights
[[0 0 0 1 0]
 [0 0 0 1 1]
 [0 0 1 1 0]
 [1 0 1 1 1]
 [1 1 0 1 1]]
h, w
5, 5

プレイする関数

答え盤面(クリックするマス)を入力してパズルをプレイし、結果の盤面を返す関数を作ります。

#============================
# パズルをプレイする関数
#============================
#答えにしたがってプレイする関数
def play(lights, ans):
    #盤面をコピー
    lights_copy = deepcopy(lights)
    
    #盤面に対して答えを十字型に足し込む
    lights_copy[:, :] += ans[:, :]
    lights_copy[1:, :] += ans[:-1, :]
    lights_copy[:-1, :] += ans[1:, :]
    lights_copy[:, 1:] += ans[:, :-1]
    lights_copy[:, :-1] += ans[:, 1:]
    
    #偶数回返されたマスは0、奇数回は1とする
    lights_copy = lights_copy % 2
    
    return lights_copy

#適当な答えを生成(1:クリックするマス)
ans = nr.randint(0, 2, (h, w))
print('ans:\n{}'.format(ans))

#適当な答えでプレイ
result = play(lights, ans)
print('result:\n{}'.format(result))
ans:
[[0 1 1 0 1]
 [1 1 1 1 1]
 [1 0 0 1 0]
 [0 0 0 0 1]
 [0 1 1 0 0]]
result:
[[0 1 1 0 0]
 [1 0 0 1 0]
 [0 0 1 1 1]
 [0 1 0 1 0]
 [0 1 0 0 0]]

適当な答え盤面を生成してプレイしてみると、10マスが点灯している状態になりました。

評価関数

遺伝子配列(para)を入力し、これを答え盤面に変換してパズルをプレイし、プレイ後の点灯数を返す関数を作ります。途中経過が気になる方はコメントアウトを解除して詳しく見てみてください。

#============================
# 評価関数
#============================
def lights_score(para):
    #paraを答え盤面に変形
    ans = para.reshape((h, w))
    #print('ans:\n{}'.format(ans))
    
    #それでプレイ
    result = play(lights, ans)
    #print('result:\n{}'.format(result))
    
    #点灯マス(=1)の総数をスコアとして返す
    return np.sum(result)

#適当なparaを生成
para = nr.randint(0, 2, h*w)
print('para:\n{}'.format(para))

#適当なparaでプレイしてスコアを返す()
score = lights_score(para)
print('score:\n{}'.format(score))
para:
[1 1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1]
score:
13

適当なparaを生成して入れたところ、スコア(残り点灯数)=13が返ってきました。

GAで最適化

離散的なGAができる vcopt().dcGA() を用います。para_range は各遺伝子が取り得る [0, 1] という選択肢が25個並んだ2次元配列です。評価値は0を目指します。

#===============================================
# GA
#===============================================
#パラメータ範囲
para_range = [[0, 1] for _ in range(h*w)]
print('para_range:\n{}'.format(para_range))

#GAで最適化
para, score = vcopt().dcGA(para_range,             #パラメータ範囲
                           lights_score,           #評価関数
                           0,                      #目標値
                           pool_num=h*w*50,        #個体数を通常の5倍に増やす
                           show_pool_func='print') #簡易出力機能を使う


#結果の確認
ans = para.reshape((h, w))
print('ans:\n{}'.format(ans))

result = play(lights, ans)
print('result:\n{}'.format(result))
para_range:
[[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1]]
___________________ info ___________________
para_range : n=25
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 1250
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 1250/1250        
gen=0, best_score=4.0, mean_score=12.4656, mean_gap=12.4656, time=0.4
gen=1250, best_score=4.0, mean_score=10.2448, mean_gap=10.2448, time=0.9
gen=2500, best_score=4.0, mean_score=9.168, mean_gap=9.168, time=1.3
・・・
gen=47500, best_score=1.0, mean_score=3.9704, mean_gap=3.9704, time=13.0
gen=48750, best_score=1.0, mean_score=3.9256, mean_gap=3.9256, time=13.3
gen=50000, best_score=0.0, mean_score=3.8672, mean_gap=3.8672, time=13.7
__________________ results _________________
para : [0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0]
score : 0.0
____________________ end ___________________
ans:
[[0 0 1 0 1]
 [0 1 1 1 1]
 [1 0 0 0 0]
 [1 0 0 0 1]
 [1 1 1 0 0]]
result:
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]

14秒でスコア0が見つかりました。このように11マスをクリックするとすべて消灯しますが、どうやら最短の解ではないようです。(赤い点が最短の解です)

評価関数の工夫

評価関数において、点灯マスの総数を1の位、クリックしたマスの総数を0.1の位とする小数を返すように修正しました。例えばスコア=0.5は、すべてのマスが消灯しており、クリック数が5であることを意味します。

#============================
# 評価関数
#============================
def lights_score(para):
    #paraを答え盤面に変形
    ans = para.reshape((h, w))
    #print('ans:\n{}'.format(ans))
    
    #それでプレイ
    result = play(lights, ans)
    #print('result:\n{}'.format(result))
    
    #点灯マス(=1)の総数を1の位、クリックしたマスの総数を0.1の位としてスコアを返す
    return np.sum(result) + 0.1 * np.sum(ans)
para_range:
[[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1]]
___________________ info ___________________
para_range : n=25
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 1250
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 1250/1250        
gen=0, best_score=6.2, mean_score=13.7808, mean_gap=13.7808, time=0.5
gen=1250, best_score=5.2, mean_score=11.4683, mean_gap=11.4683, time=0.9
gen=2500, best_score=4.2, mean_score=10.3748, mean_gap=10.3748, time=1.4
・・・
gen=48750, best_score=1.2, mean_score=4.7123, mean_gap=4.7123, time=16.1
gen=50000, best_score=1.2, mean_score=4.6365, mean_gap=4.6365, time=16.6
gen=51250, best_score=0.8, mean_score=4.563, mean_gap=4.563, time=17.0
gen=52500, best_score=0.8, mean_score=4.4944, mean_gap=4.4944, time=17.4
・・・
gen=168750, best_score=0.8, mean_score=0.8496, mean_gap=0.8496, time=53.8
gen=170000, best_score=0.8, mean_score=0.8474, mean_gap=0.8474, time=54.2
gen=171250, best_score=0.8, mean_score=0.8474, mean_gap=0.8474, time=54.6
__________________ results _________________
para : [1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1]
score : 0.8
____________________ end ___________________
ans:
[[1 0 0 0 0]
 [1 1 0 1 0]
 [1 0 0 0 0]
 [0 0 1 0 0]
 [0 1 0 0 1]]
result:
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]

収束に55秒かかりましたが、17秒で最少手数の解を見つけました。

例題2

こちらの問題もなかなか難しいです。「え、そこクリックするの?」という感じです。

#============================
# パズルの記述
#============================
lights = ['----#',
          '-#--#',
          '-#--#',
          '##-#-',
          '--##-']
___________________ info ___________________
para_range : n=25
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 1250
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 1250/1250        
gen=0, best_score=4.7, mean_score=13.7857, mean_gap=13.7857, time=0.5
gen=1250, best_score=4.7, mean_score=11.3924, mean_gap=11.3924, time=1.0
gen=2500, best_score=3.8, mean_score=10.2861, mean_gap=10.2861, time=1.4
・・・
gen=21250, best_score=3.1, mean_score=6.6331, mean_gap=6.6331, time=7.5
gen=22500, best_score=3.1, mean_score=6.5265, mean_gap=6.5265, time=8.2
gen=23750, best_score=0.6, mean_score=6.4251, mean_gap=6.4251, time=8.5
gen=25000, best_score=0.6, mean_score=6.325, mean_gap=6.325, time=8.9
・・・
gen=153750, best_score=0.6, mean_score=0.7071, mean_gap=0.7071, time=49.4
gen=155000, best_score=0.6, mean_score=0.7024, mean_gap=0.7024, time=49.9
gen=156250, best_score=0.6, mean_score=0.7024, mean_gap=0.7024, time=50.4
__________________ results _________________
para : [0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0]
score : 0.6000000000000001
____________________ end ___________________
ans:
[[0 0 0 1 0]
 [0 0 1 1 0]
 [0 0 0 1 0]
 [0 1 0 0 0]
 [0 0 1 0 0]]
result:
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]

8秒で最少手数が見つかり、50秒で収束しました。ちなみに、事前にクリック数が分かっていれば8秒で止めることも可能です。

感想

一つの解を見つけるのはさほど難しくありません(解法の記事を参照ください)。しかし、最小手数の解を見つけるのは大変です。今回はGAの威力が発揮できたのではないでしょうか。(え、このサイズなら全探索のほうが早いだろうって?聞こえないですアーアー)

タイトルとURLをコピーしました