2012/05/06

Javaアプレット(57) 開発を中断

Javaアプレットでのプログラム開発を中断します。

死活問題が煮詰まっていることもあるのですが、先日買った iPad でJavaアプレットが動かない、というのがちょっと寂しくもあり、JavaScript + HTML5 での開発に踏み切ろうと思いました。

Javaアプレットはさまざまな環境で実行できることが売りでしたが、今後の流れは、JavaScript + HTML5 の方向へ動いているように思います。JavaScript + HTML5 で開発すれば、パソコンだけでなく、スマートフォン(携帯電話はちょっとむりですが)でも実行できるプログラムを書くことができます。

実行速度はJavaアプレットのほうが速そうですが、その辺はなんとか工夫してみようと思います。

| | コメント (0) | トラックバック (0)

2012/04/07

Javaアプレット(56) オイラーの公式

石の死活を考えるときの石の部分集合に群という概念があります。同じ色の石が縦横に接続したものをと呼びますが、連同士がつながった集合をといいます。群が死活を判定する単位になります。

ある群の死活を考える上で、まず単純にその群が眼を2つ以上持っていれば無条件に活きです。そこで群の眼を数えることが死活計算の第一歩になるのですが、かの有名な数学者オイラーが発見した頂点と辺と面(領域)の数の関係を示したオイラーの公式が群の眼の数を数えるのに役立つのです。

オイラーの公式とは頂点 (vertex) の数 v 、辺 (edge) の数 e と面 (region) の数 r の間に、

 v - e + r = 2

という関係が成り立つというものです。 面の数を求めるように変形すると、

 r = e - v + 2

となります。例えば3路盤の格子の場合、頂点の数 v = 9 、辺の数 e = 12 なので、面の数は、

 r = e - v + 2 = 12 - 9 + 2 = 5

になります。これは格子のマス目が4つと外側の領域を合わせて5ということです。つまり、外側の領域を除けば、

 r = e - v + 1

が成り立ちます。これを群の眼を数えることに応用するとどうなるでしょうか。下図の局面を例に考えてみましょう。
図:ある局面
【図79 ある局面】

この局面の左上の白石の群を考えてみます。この群をグラフとして表現したのが下図です。
図:群のグラフ表現
【図80 群のグラフ表現】

この図では頂点の数 v = 7 、辺の数 e = 9 なので、面の数は、

 r = e - v + 1 = 9 - 7 + 1 = 3

になります。これがこの群が囲っている閉領域の数になります。

それにしても、オイラーの公式は不思議な公式です。頂点の数と辺の数で面の数が決まってしまうわけですから、同じ数の頂点と辺をどうつないでも面の数は変わらないということになります。ということは同じ頂点の数であれば、辺の数を増やしたほうが面の数が増えるということ。図79の白14手目の隅に打った手は頂点 +1 に対し、辺を +2 にできたために面を +1 できたことになります。

この原理をBWモデルに当てはめたのが、別ページの式になります。また、今回これらの式をプログラムにしました。GraphGo_0_16 として公開します。この中の NumericAnalysis.java で上記局面の計算を実際に行っています。

ただし死活の計算自体にはまだ反映していません。もう少し他の論文も読んでみようと思います。

(つづく)

| | コメント (0) | トラックバック (0)

2012/04/06

Javaアプレット(55) 死活判定の研究

結局、石の死活をどう判定するかがプログラムを左右する、ということで死活判定の研究を続けています。今のところは内外の論文を読んでいるところです。古いところでは1960年代にはすでに囲碁の死活をコンピュータでどう扱うのか研究が始まっています。日本はもちろんアメリカ、オランダなど様々な国で研究されています。

死活の判定方法は大きく分けて2つあります。

1つは静的な判定方法です。盤面のさまざまな要素から計算したり、過去の計算結果を局面のパターンから割り出す方法があります。

もう1つは動的な判定方法です。終局まで打ってみる方法です。ゲーム木(ぎ)を探索するとも言います。大きな盤ではゲーム木が巨大になるため、すべて探索することができないので、いかに効率的に正着を見逃さずに探索するのかが重要になってきます。

まずは静的に判定できるものを組み込もうと思います。現在オイラーの公式を応用して石の眼の数を数えるところを実現しようとしています。関係する式をまとめつつ、サンプルプログラムで確認しているところです。

ベクトルと行列の演算にもようやく慣れてきた感じがします。

TeXはまだ苦労しながら使っています。

(つづく)

| | コメント (0) | トラックバック (0)

2012/03/23

Javaアプレット(54) 数式の見直し

前回の数式の見直しを、プログラムに反映しました。GraphGo_0_15 として公開します。
図:GraphGo v0.15
【図78 GraphGo v0.15】

やはりうまく動作しない式もあり、式自体も修正しました。
特に「石に囲われている」がまたまた違っていて、S∧(lt1)≠~lt(tSl) という式になりました。これは空接点行列 S のなかの空点の行のパターンがすべて同じなら石に囲われていないということを判定しています。

死活の判定が不十分なので6ベクトルに影響があるのですが、それにしてもセキ石が連の途中で切れているのは他にも原因があるかもしれません。

なお、今回パスできるように修正しました。投了やコウの処理はまだできません。終局の処理も入っていないので、お互いがパスになったら実質上の終局です。

前回 GraphGo か、その下のアプレット ImageTestApplet のどちらか、または両方のボタンの位置がずれてしまう問題がありました。これはボタンの位置の拠(よ)り所となるボタンの数を入れる変数 num を GButton クラスの static な変数にしていたためです。static な変数はオブジェクト毎ではなくクラスに共通で使えるため、うまい使い方だと思っていたのですが、他のアプレットともバッティングしてしまうことは想定外でした。GButton を呼び出す GTable の public 変数を使うよう変更しました。

それから、今回 Java Developer Newsletter に Java SE 6 の EOL (end-of-life) が今年の11月のというニュースが載っていたのを受けて、Java SE 7 に乗換えを試みました。しかし、推奨されるランタイムは以前 Java SE 6 なので、ローカルでは動いてもオンライン上では簡単には動かないことが分かり、Java SE 6 に戻しました。

さて、相変わらず手付かずの死活判定に、そろそろメスを入れていきたいと思います。

(つづく)

| | コメント (0) | トラックバック (0)

2012/03/21

Javaアプレット(53) 数式のまとめ

これまで使ってきた数式をまとめました。別ページで公開します。

とりあえずまとめたところなので、式に誤りがあるかもしれません。誤りを見つけた場合は予告なく訂正する予定です。

式(13-1)はまだ完成していません。これは活き石を表す式ですが、求めるのが難しく、盤面が小さい場合は終局まですべての組合せで打ってみて決める、という手がありますが、盤面が大きいといわゆる組合せ爆発がおき、計算できません。次善の手として考えられるのは、モンテカルロ法(乱数を使って)によりいくつかの組合せで終局まで打って(プレイアウトして)みて決めるという方法です。この方法は確率上の活き石を求められますが、完全な解にはなりません。ここが囲碁プログラムの急所と言えるかもしれません。

今回、式をまとめ解説をつけながら、いくつかの式を修正しました。

プログラムの開発でレビューという工程があります。レビューでは開発者がレビュアーに対し作成したプログラムの正しさを言葉で証明します。今回のこの式のまとめは、式自体のレビューに相当する作業となりました。

修正後の式はまだプログラムには反映していません。

次回はこれらの式をプログラムに反映しつつ、Javaの開発環境をJDK 7に完全に移行しようと思います。

(つづく)


| | コメント (0) | トラックバック (0)

2012/03/04

Javaアプレット(52) 6ベクトルの計算と表示

死活のみならず、6ベクトルの計算をできるようにしました。 GraphGo014 として公開します。
図:GraphGo v0.14
【図77 GraphGo v0.14】

死活の計算をなんとかしたい、というところからスタートし、いくつか大きな変更をしました。

  1. 6ベクトルを計算するようにしました。活き石の計算が不十分なので、残りの5つもおかしくなります。
  2. 6ベクトルを碁盤上に明暗として表示できるようにしました。
  3. ベクトルを選ぶため、また、パスや投了、手順番号の表示/非表示の切り替えなどができるようにボタンを設置しました。

今まではSystem.out.println()でベクトルの内容を表示して確認していましたが、今後、その手間は省けます。

ボタンの描画にはGraphics2Dのグラデーションの機能を使いました。また、明暗の表示には色のアルファチャネル(RGB+A)を使い、A=128 (50%)の茶色で網掛けしています。

上図では、死に石を表示していますが、明らかに活き石が死に石と表示されています。活き石vの計算がうまくいっていないようです。そのせいだけではなさそうですが、眼の候補地の計算もうまくいっていません。

それから、6ベクトルを実際に計算してみて、以前の式に誤りがあることが分かりました。目と地の条件式の「石に囲われていて」という部分が正しくは、tSl1 になります。

これで、死に石(活き石)の計算や眼の候補地の計算の結果が簡単に確認できるようになりました。なんとか、改善していきたいと思います。

(つづく)

| | コメント (0) | トラックバック (0)

2012/03/01

Javaアプレット(51) 眼の候補地を広くする

接待として打つ AI をどうするか。なるべく持碁に近くなるようにしてはどうかと考えました。

最初は石の呼吸点の数を比較して同じになるようにしては、と考えたのですが、これだと石をツケないで、やんわり囲まれたときに応手できなくなってしまいます。

次に考えたのは、呼吸点よりもっと広い範囲を見る方法として、眼の候補地を数えて同じになるようにしようと考えました。眼の候補地は白石の場合、次の2つの条件を同時に満たしていることで判定します。

条件1:その空点にツケられている黒石がない。| J1ei - w | = 0
条件2:その空点のコスミに黒石が1つ以下。| D2ei - w | ≦ 1

ここで、J1とD2はツケとコスミの関係を表す行列です。このアイディアで AI を作ってみたのが、GraphGo013 です。
図:GraphGo v0.13
【図76 GraphGo v0.13】

作ってみて白と黒の眼の候補地を同じにしようとすると AI としては弱すぎることが分かり、AI 側(白石)が眼の候補地を最大にするように変更しました。

でも、弱いです。どう弱いのか検討するために、6路盤にし、手順番号を表示するようにしました。眼の候補地の数はSystem.out.println() を使ってコンソールに表示しています。

なんとなく分かってきたのは、上記の条件式の黒石 -w は、活き石であることが前提です。これを正確に表すと、-(w - x) となります。x は死に石です。要するに死活が分かっていないと眼の候補地は正しく判定できないということです。

ということで、やはり死活をなんとかしなければならなくなりました。

(つづく)

| | コメント (0) | トラックバック (0)

2012/02/28

Javaアプレット(50) AIの作成

死活の問題をどうにかしようとしている途中なのですが、ここでちょっと方針を一時修正したいと思います。

3月5日に開催されるJAIST CUP 2012ゲームアルゴリズム大会@品川の囲碁9路盤「接待碁」コンテストに参加できるか、検討してみました。

参加条件としては「9路盤」「コミ 7.5目」「中国ルール」「超コウ」「GTPによる通信」「3つのコマンド追加X-playerlevel、X-gencomment-premove、X-gencomment-aftermove」「手抜きではない手加減、起伏に富んだ展開への誘導、楽しいコメントなど、プレイヤを『接待』する工夫を競う」を満たす必要があります。

9路盤にするのは簡単にできます。人間を相手に対戦するのでAI(思考ルーチン)が必要になります。ということで、最低限この2つを作ってみました。GraphGo012 として公開します。
図:GraphGo v0.12
【図75 GraphGo v0.12】

コミは、スコアを計算するときに白のスコアとして加えればいいだけです。中国ルールは、地だけではなく石を含めてスコアをカウントします。これもなんとかなりそうです。コミ7.5も超コウも中国ルールに由来します。超コウは単にコウの繰り返しのみでなく、同一局面が現れることを禁止するルールです。これはちょっと大変そうです。局面をすべて覚えておく必要があるかもしれません。

GTPはGo Text Protocolというテキストでプログラム同士が碁を打ち合うためのプロトコル(通信手順)です。JavaのプログラムではGoGuiというプログラムがソース込みで公開されているので、参考にできそうです。これに3つのコマンドを追加すればよいということです。

で、結局、このコンテストの根幹となる「手抜きではない手加減、起伏に富んだ展開への誘導、楽しいコメントなど、プレイヤを『接待』する工夫を競う」というアイデアが出るか、というところが肝になってくるようなのですが、なんとか動く9路盤プログラムを作れても、ここが厳しそうな気がしています。

大会目前なので、いずれにせよ厳しそうなのですが、できるところまでがんばってみようかと思います。

(つづく)


| | コメント (0) | トラックバック (0)

2012/02/22

Javaアプレット(49) 6ベクトルの式

さて、6ベクトルの式を書いてみましょう。まずは『日本囲碁規約』の定義にしたがって書いてみます。この定義には依存関係があるので、依存のないものから順番に書いていきます。

(1) 活き石 v = v1v2
 ただし、v1は相手方の着手により取られない石、
 v2は取られても新たに相手方に取られない石を生じうる石

(2) 死に石 x = ~l - v

この2つはいわゆる死活判定の式になっています。実際にこれを求めるのは難しいと思われるのですが、今はこれ以上追及しないことにします。

(3) 目 (y)i = {  1 : (S (+) S0)l ≠ 0 かつ (~(tSei - l)∨(v - w) = 1 または ~(tSei - l)∨(v - b) = 1)↓{ 0 : otherwise

この式はベクトルyのi番目の要素(y)iを定義した式で、それが1になる条件を言葉で表すと、「石に囲われていて かつ (その囲う石が黒の活き石に含まれる または その囲う石が白の活き石に含まれる)」となります。

(4) ダメ m = l - y

(5) セキ石 s = v∧(tSm - l)

この式は「ダメと隣接する活き石」という意味です。

(6) 地 (t)i = {  1 : (S (+) S0)l ≠ 0 かつ (~(tSei - l)∨(v - w - s) = 1 または ~(tSei -l)∨(v - b - s) = 1)↓{ 0 : otherwise

この式はベクトルtのi番目の要素(t)iを定義した式で、それが1になる条件を言葉で表すと、「石に囲われていて かつ (その囲う石がセキ石以外の黒の活き石に含まれる または その囲う石がセキ石以外の白の活き石に含まれる)」となります。

(3)と(6)に関しては、死に石が残っているとうまく計算できないので、死に石を盤上から一時的に取り去って、空点の連接を表すSを計算し直した上で利用する必要があります。

問題は、(1)と(2)の死活判定で囲碁のプログラムにとってはかなり悩ましい部分だと思います。次回は死活についてじっくり考えてみたいと思います。

(つづく)

| | コメント (0) | トラックバック (0)

2012/02/21

Javaアプレット(48) 行列Sの定義

6つのベクトルを計算するために、b, w, Fでは足りない気がしています。石については、Fがつながっている石(連)を記憶しているのでいいのですが、空点についてはそのつながりがすぐに分かりません。局面を表すにはb, wの情報でも十分なのですが、連をいちいち計算するのが大変なのでFを導入していたわけです。空点についても同様な仕組みがあると計算が楽になりそうです。

下図に、ある局面とそのF(iの連接点j)を示してあります。Fを見ると分かるとおり空点に関してはその隣接する点しか表していません。つまり、空点を囲む石を知りたい場合にFからではすぐに分からないのです。そこで、空点について連接点に相当するものを行列Sとして定義しようと思います。
図:行列Fと行列S
【図74 行列Fと行列S】

初期局面におけるSをS0と呼ぶとすると、S0は要素が全て1の行列になります。1手打たれると、その行は隣接関係でクリアされます。つまりFとは逆で石のあるところは隣接関係、ないところが連接関係を表す行列になります。

この行列Sは、行列Fのように少しずつ増えた連接関係を追加していくことが難しいようです。例えば盤面が石で左右に分断されたとき、すべての空白の連接関係が左側の空白に属するか、右側の空白に属するかで2つのパターンに分かれます。その際の連接パターンの抽出は、盤面全体を調べる必要があります。

Fの場合は育っていった(石の)連があるときつながるだけなので、関連する連の論理和を取れば済みます。Sの場合はその逆で、あるとき大きな空白の連が最大4つの小さな空白の連に分かれるのですが、その小さな空白の連の情報を元々持っていないので、そのときに計算しなおす必要があるわけです。

Fの導入のようにスマートにいきませんが、このSを計算することを前提に、6つのベクトルを導く式を検討していこうと思います。

(つづく)

| | コメント (0) | トラックバック (0)

より以前の記事一覧