2011年10月19日水曜日

コンピュータにラストワンを解かせてみた

このブログ記事をはてなブックマークに追加

先日、地元のまつりがあった。そこの会場となっている区民館では子供用ボーリングやプラ板遊びなどの催しが開かれていたのだが、その中の一つに「ひとりぼっち」というゲームを行なっているのを見つけたので、一緒にいた小4の自分の娘に「このゲーム面白そうだね」と言ったところ、「ラストワンでしょ」と返され、よく知っているゲームとのことだった。遊び方は次の通り。全部で33のマスがあり、真ん中以外の32個のマスにコマを置く。コマは縦・横方向に隣のコマを一つ飛び越えて進むことができる。飛び越えられたコマは取り除かれる。これを繰り返して、最後のコマを真ん中のマスに置けばクリアとなる。32コマを使うステージ以外にもT字型やピラミッド型にコマを配置するなど、さまざまなバリエーションがある。


ネットで調べたところ、1985年にバンダイから同名の電子ゲームが出ていたようだ。リンク先では動画もあるのでそれを見てもらえば遊び方は一目瞭然だろう。普通に解いても面白そうだが、コンピュータを使って解かせたくなったので、早速プログラムを作ってみた。

余談だが、子供のころ、コンピュータは何でも解いてくれる魔法の箱だと思っていた。円周率を何桁まで解いたと聞いて、ワクワクしたものだ。ラストワンのようなゲームをコンピュータに解かせたいという気持ちは、子供のころのコンピュータに対する憧れから来るのかもしれない。

閑話休題。ラストワンは33マスあり、コマが「ある」「ない」の2状態のみを持つので、33ビットを使って盤面の状態を表すことができる。そして、ある状態から取り得る次の状態をすべて求めて、それを優先順位付きキューに入れて探索した。キューが空になるか、ゴールの状態が見つかるまで探索を行う。優先順位付きキューにしたのは探索を短縮するためにヒューリスティックな関数でスコアを決めようと思ったからなんだけど、32コマあるステージも含め、どれも一瞬で解けてしまうので、どうやら高度なヒューリスティック関数を用意しなくても問題なかったらしい。


上図のように初期配置としてT字型にコマを置く場合、以下に示すような入力データを用意して、これをプログラムに渡す。o (オー)でコマのあるマスを表し、. (ドット)で空のマスを表している。

lastone.dat

... ... ....... ..ooo.. ...o... .o. ...

入力データのファイル名が lastone.dat であれば、以下のように実行すればよい。

% ./lastone lastone.dat

実行結果は以下のようになる。

... ... ....... ..ooo.. ...o... .o. ... ... ... ....... .o..o.. ...o... .o. ... ... ... ....... .o.oo.. ....... ... ... ... ... ....... .oo.... ....... ... ... ... ... ....... ...o... ....... ... ...

最後に作成したコードを示す。

lastone.cpp

// Last One solver by nox, 14 Oct. 2011 #include <iostream> #include <fstream> #include <string> #include <vector> #include <queue> #include <algorithm> #include <utility> using namespace std; typedef unsigned long long state_t; typedef int score_t; const int N = 33; // number of cells class LastOne { private: vector<vector<pair<int, int> > > D; // table of directions state_t start, goal; vector<state_t> ans; // solution public: LastOne(const string datafile=""); ~LastOne() { } void read(const string datafile); int movable(state_t state); void next(state_t state, vector<state_t>& neighbors); bool search(); void show(state_t state); void answer(); }; // initialize and make table LastOne::LastOne(const string datafile) { if (!datafile.empty()) read(datafile); vector<pair<int, int> > v; v.push_back(make_pair(1, 2)); v.push_back(make_pair(3, 8)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 9)); D.push_back(v); v.clear(); v.push_back(make_pair(1, 0)); v.push_back(make_pair(5, 10)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 5)); v.push_back(make_pair(8, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 3)); v.push_back(make_pair(10, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(7, 8)); v.push_back(make_pair(13, 20)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 9)); v.push_back(make_pair(14, 21)); D.push_back(v); v.clear(); v.push_back(make_pair(3, 0)); v.push_back(make_pair(7, 6)); v.push_back(make_pair(9, 10)); v.push_back(make_pair(15, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(4, 1)); v.push_back(make_pair(8, 7)); v.push_back(make_pair(10, 11)); v.push_back(make_pair(16, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(5, 2)); v.push_back(make_pair(9, 8)); v.push_back(make_pair(11, 12)); v.push_back(make_pair(17, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 9)); v.push_back(make_pair(18, 25)); D.push_back(v); v.clear(); v.push_back(make_pair(11, 10)); v.push_back(make_pair(19, 26)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 15)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(8, 3)); v.push_back(make_pair(14, 13)); v.push_back(make_pair(16, 17)); v.push_back(make_pair(22, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(9, 4)); v.push_back(make_pair(15, 14)); v.push_back(make_pair(17, 18)); v.push_back(make_pair(23, 28)); D.push_back(v); v.clear(); v.push_back(make_pair(10, 5)); v.push_back(make_pair(16, 15)); v.push_back(make_pair(18, 19)); v.push_back(make_pair(24, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 17)); D.push_back(v); v.clear(); v.push_back(make_pair(13, 6)); v.push_back(make_pair(21, 22)); D.push_back(v); v.clear(); v.push_back(make_pair(14, 7)); v.push_back(make_pair(22, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(15, 8)); v.push_back(make_pair(21, 20)); v.push_back(make_pair(23, 24)); v.push_back(make_pair(27, 30)); D.push_back(v); v.clear(); v.push_back(make_pair(16, 9)); v.push_back(make_pair(22, 21)); v.push_back(make_pair(24, 25)); v.push_back(make_pair(28, 31)); D.push_back(v); v.clear(); v.push_back(make_pair(17, 10)); v.push_back(make_pair(23, 22)); v.push_back(make_pair(25, 26)); v.push_back(make_pair(29, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(18, 11)); v.push_back(make_pair(24, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(19, 12)); v.push_back(make_pair(25, 24)); D.push_back(v); v.clear(); v.push_back(make_pair(22, 15)); v.push_back(make_pair(28, 29)); D.push_back(v); v.clear(); v.push_back(make_pair(23, 16)); D.push_back(v); v.clear(); v.push_back(make_pair(24, 17)); v.push_back(make_pair(28, 27)); D.push_back(v); v.clear(); v.push_back(make_pair(27, 22)); v.push_back(make_pair(31, 32)); D.push_back(v); v.clear(); v.push_back(make_pair(28, 23)); D.push_back(v); v.clear(); v.push_back(make_pair(29, 24)); v.push_back(make_pair(31, 20)); D.push_back(v); } // read LastOne data void LastOne::read(const string datafile) { fstream fs(datafile.c_str(), ios_base::in); string line; goal = 0x10000; start = 0ULL; while (getline(fs, line)) { for (string::iterator p = line.begin(); p != line.end(); ++p) { if (*p == 'o') { start <<= 1; start |= 1ULL; } else if (*p == '.') start <<= 1; } } fs.close(); } // number of movable pieces int LastOne::movable(state_t state) { int s = 0; for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) s += ((state >> p->first) & 1) & !((state >> p->second) & 1); return s; } // next states void LastOne::next(state_t state, vector<state_t>& neighbors) { neighbors.clear(); for (int i = 0; i < N; i++) if ((state >> i) & 1) for (vector<pair<int, int> >::iterator p = D[i].begin(); p != D[i].end(); ++p) if (((state >> p->first) & 1) & !((state >> p->second) & 1)) neighbors.push_back(state ^ (1ULL << p->first) ^ (1ULL << p->second) ^ (1ULL << i)); } // search solution bool LastOne::search() { vector<state_t> checked(1, start); priority_queue<pair<score_t, vector<state_t> > > queue; queue.push(make_pair(1, checked)); vector<state_t> neighbors; while (!queue.empty()) { pair<score_t, vector<state_t> > q(queue.top()); queue.pop(); state_t last = q.second.back(); if (last == goal) { ans = q.second; return true; } next(last, neighbors); for (vector<state_t>::iterator p = neighbors.begin(); p != neighbors.end(); ++p) { if (binary_search(checked.begin(), checked.end(), *p)) continue; if (movable(*p) == 0 && *p != goal) continue; checked.insert(upper_bound(checked.begin(), checked.end(), *p), *p); vector<state_t> path(q.second); path.push_back(*p); queue.push(make_pair(static_cast<score_t>(path.size()), path)); } } return false; } // show state void LastOne::show(state_t state) { string line; while (state) { if (state & 1ULL) line.push_back('o'); else line.push_back('.'); state >>= 1; } int n = N - line.size(); for (int i = 0; i < n; i++) line.push_back('.'); reverse(line.begin(), line.end()); cout << " " << line.substr(0, 3) << endl; cout << " " << line.substr(3, 3) << endl; cout << line.substr(6, 7) << endl; cout << line.substr(13, 7) << endl; cout << line.substr(20, 7) << endl; cout << " " << line.substr(27, 3) << endl; cout << " " << line.substr(30, 3) << endl; } // show solution void LastOne::answer() { for (vector<state_t>::iterator p = ans.begin(); p != ans.end(); ++p) { show(*p); cout << endl; } } int main(int argc, char* argv[]) { if (argc < 2) { cerr << "Usage: " << argv[0] << " datafile" << endl; exit(1); } LastOne lastone(argv[1]); if (lastone.search()) lastone.answer(); else cout << "No solution." << endl; return 0; }

続きを読む...

2011年10月14日金曜日

オフィスビル内の最短経路

このブログ記事をはてなブックマークに追加

現在のオフィスでは、エントランスからどの通路を通るのが最も近いのか、未だに話題になることがある。エントランスからオフィスにつながるエレベータまでの道が二通りあり、どちらも似たような距離なので同じオフィスに行く人達なのにそこで別々になってしまうこともしばしば。左の図が問題のフロアなんだけど、エントランスから青丸で示したエレベータまで行く必要がある。だったらコンピュータに解かせてしまえばいいじゃない、ということでプログラムを作って最短経路と正確な距離を調べてみた。定規で測ったほうが早いという意見は聞こえません。

以前、Python: 画像で与えられた迷路に対し2点間の最短経路を求めるというブログ記事で、画像から直接最短距離を求めるプログラムを書いたことがあるので、まずはそれを使って調べてみた。図面の邪魔な文字だけ消して、あとはスタート地点とゴール地点の座標を引数で指定するだけだから簡単なんだけど、これだと問題があることに気がついた。というのはCCL (connected component labeling; 連結成分ラベリング)で移動できる領域を調べて、それをA*で解いているのだけど、隣接するノード(ピクセル)を上下左右斜めの8方向のみで調べているから正しい距離を出すことができないのだ。実際に作成した図は以下のようにギザギザになってしまい最短ルートを通らない。なので通り道の分岐や方向が変化する箇所をノードにしてそれをA*で求めることにした。


全部で10個のノード(画像のピクセル座標で指定)を作って調べたところ、以下のような結果になった。左側を通る通路の距離が324.53、右側を通る通路の距離が322.51となり僅かに右側の通路のほうが近かった。ただし、右側の方は途中でフロア案内と少し重なるし、6つあるエレベータのどれを使うかによっても結果が変わってしまうぐらいなので、実質的には同じ距離といってしまっても差し支えないと思う。



結局、それぞれの距離にはほとんど差がないので、結論としては「好きな方を使え」ということになるだろう。自分は広い通路の方が好みなので右側の通路を利用している。最後にソースコードとその使い方を示しておく。

nodes.datに、一行を"ピクセルX座標 ピクセルY座標 隣接ノード番号リスト"としてノード数の分だけ記述する。ノード番号は0から始まり、先頭行と最終行のノードはそれぞれスタート地点、ゴール地点を表している。また、フロアの図面画像をinput.pngとして渡すと、最短距離のルートが書きこまれた画像をoutput.pngとして出力する。

% ./route_solver.py nodes.dat input.png output.png

nodes.dat

27 273 1 3 6 21 128 0 2 125 23 1 9 117 221 0 4 5 6 141 178 3 7 167 178 3 7 195 178 0 3 7 192 110 4 5 6 8 193 91 7 9 151 41 2 8

route_solver.py

#!/usr/bin/env python # -*- coding: utf-8 -*- import sys, os, math, heapq, Image, ImageDraw class Node: def __init__(self): self.pos = (0, 0) self.neighbors = [] self.dist = float("inf") self.path = [] # A* Search Algorithm class AStar: def __init__(self, start, goal): self.start, self.goal = start, goal self.start.dist = 0.0 self.start.path = [self.start] def distance(self, node1, node2): return math.sqrt((node1.pos[0] - node2.pos[0])**2 + (node1.pos[1] - node2.pos[1])**2) def heuristic(self, node): return self.distance(node, self.goal) def search(self): queue = [] heapq.heappush(queue, (self.heuristic(self.start), self.start)) while queue: score, last = heapq.heappop(queue) if last == self.goal: return last.path, last.dist for nb in last.neighbors: newdist = last.dist + self.distance(last, nb) if nb.dist < newdist: continue nb.dist = newdist nb.path = last.path + [nb] heapq.heappush(queue, (nb.dist + self.heuristic(nb), nb)) return [], 0.0 def draw_path(in_image, out_image, path): im = Image.open(in_image) im = im.convert("RGB") draw = ImageDraw.Draw(im) draw.line([(int(p.pos[0]), int(p.pos[1])) for p in path], fill=255, width=2) im.save(out_image) def main(args): if len(args) < 4: print >>sys.stderr, "Usage: %s datafile in_image out_image" % os.path.basename(args[0]) sys.exit(1) datafile, in_image, out_image = args[1:4]; print "Reading nodes data..." data = [map(int, l.strip().split()) for l in file(datafile).readlines()] nodes = [Node() for i in range(len(data))] for i, node in enumerate(nodes): node.pos = tuple(data[i][:2]) for j in data[i][2:]: node.neighbors.append(nodes[j]) print " Number of nodes: %d" % len(nodes) print "A* searching phase..." start, goal = nodes[0], nodes[-1] print " Start: (%d, %d), Goal: (%d, %d)" % (start.pos + goal.pos) astar = AStar(start, goal) path, dist = astar.search() if path: print " Found route:" for p in path: print " (%d, %d)" % p.pos print " Distance: %f" % dist else: print " No route." print "Drawing path on the imagefile..." draw_path(in_image, out_image, path) if __name__ == "__main__": main(sys.argv)

追記 (2011/10/17): ソースコードが間違っていたので修正。今回の結果には影響なし。

続きを読む...