内容 | 最終更新日 | 執筆開始日 |
---|---|---|
1. はじめに | 2010/5/9 | 2010/5/9 |
2. データ構造/クラス設計 その1 | 2010/5/18 | 2010/5/9 |
2.1 駒 | 2010/5/9 | 2010/5/9 |
2.2 将棋盤 | 2010/5/9 | 2010/5/9 |
2.3 持ち駒 | 2010/5/9 | 2010/5/9 |
2.4 中間のまとめその1 | 2010/5/18 | 2010/5/18 |
3. 着手可能手(合法手) | 2010/5/18 | 2010/5/13 |
3.1 着手可能手(合法手) | 2010/5/13 | 2010/5/13 |
3.2 演習1 | 2010/5/18 | 2010/5/18 |
4. データ構造/クラス設計 その2 | 2010/5/26 | 2010/5/18 |
4.1 指し手 | 2010/5/18 | 2010/5/18 |
4.2 着手可能手(合法手) | 2010/5/18 | 2010/5/18 |
4.3 プレーヤ | 2010/5/26 | 2010/5/26 |
(コラム)どうぶつしょうぎと本将棋 | 2010/5/22 | 2010/5/22 |
5. 評価関数 | 2010/5/31 | 2010/5/26 |
5.1 評価関数とは? | 2010/5/26 | 2010/5/26 |
5.2 評価関数の例 | 2010/5/26 | 2010/5/26 |
5.3 演習2 | 2010/5/26 | 2010/5/26 |
5.4 ゲームの作成 | 2010/5/30 | 2010/5/30 |
5.5 評価関数のデバッグ | 2010/5/31 | 2010/5/31 |
6. 画面と UI その1 | 2010/6/1 | 2010/6/1 |
6.1 画面設計 | 2010/6/1 | 2010/6/1 |
6.2 画面抽象 | 2010/6/2 | 2010/6/2 |
6.3 画面の再描画 | 2010/6/5 | 2010/6/2 |
6.4 入力 | 2010/6/5 | 2010/6/5 |
6.5 演習3 | 2010/6/6 | 2010/6/6 |
7. 先読み | 2010/6/6 | 2010/6/6 |
7.1 ゲーム理論 | 2010/6/6 | 2010/6/6 |
7.2 先読みとは? | 2010/6/7 | 2010/6/6 |
7.3 ミニマックス法からαβ法 | 2010/6/14 | 2010/6/7 |
7.4 再帰と先読み | 2010/6/16 | 2010/6/15 |
8. 枝刈り | 2010/6/16 | 2010/6/16 |
8.1 枝刈りとは? | 2010/6/16 | 2010/6/16 |
8.2 枝刈りの実装とその効果 | 2010/6/20 | 2010/6/20 |
8.3 負けるときも最後までがんばる | 2010/6/27 | 2010/6/27 |
8.4 演習4 | 2010/7/25 | 2010/7/25 |
9. 画面と UI その2 | 2010/7/25 | 2010/7/25 |
9.1 MVC | 2010/7/25 | 2010/7/25 |
9.2 待ち時間制御 | 2010/7/25 | 2010/7/25 |
9.3 イラストの描き方 | 2010/7/25 | 2010/7/25 |
10. 演習 | 2010/5/31 | 2010/5/9 |
10.1 機能と条件 | 2010/5/9 | 2010/5/9 |
10.2 テスト手順 | 2010/6/1 | 2010/5/26 |
10.3 トーナメント | 2010/5/9 | 2010/5/9 |
10.4 評価 | 2010/5/9 | 2010/5/9 |
10.5 作業 | 2010/5/9 | 2010/5/9 |
ここでは、どうぶつしょうぎの作り方を「やさしく」紹介していきます。
プログラミング言語は Java 言語にしています。しかしそれほどオブジェクト指向機能を使わないようにしていますので C 言語でも作成可能です。
参考になれば幸いです。
なお、どうぶつしょうぎのルールはここにあります。
ここでは、どうぶつしょうぎのデータ構造とクラス設計を行います。
どうぶつしょうぎに登場するデータ(オブジェクト)としては、「将棋盤」、「駒」、「持ち駒」、「プレーヤ」などが、現実世界に存在する現物です。これらは直ぐに思いつくかと思います。まずは、これらの現物クラスだけで大丈夫です。最初から完全なクラスとデータ構造を発見する必要はありません。詳細なクラス設計やデータ設計もも必要ではありません。抽象的なクラスも最初から発見する必要もないです。
必要になったときに作り直せばいいのです。気楽に行きましょう!
ここでは、現物のクラスとそのデータ構造を考えていきます。
駒オブジェクトの表現は (1) 駒クラスのオブジェクト、(2) ひよこなど各々の駒クラス、(3) int で駒を表現、 (4) char、(5)
String などが考えられます。
これらを Java プログラムで表現すれば、以下のようになります。
(1) class Piece { private String name; Piece (String name) { this.name = name; } } Piece hiyoko = new Piece("hiyoko"); Piece zou = new Piece("zou"); (2) class Piece {} class Hiyoko extends Piece {} class Zou extends Piece {} (3) int hiyoko = 2; int zou = 4; (4) char hiyoko = 'h'; char zou = 'z'; (5) String hiyoko = "hiyoko"; String zou = "zou";
どうぶつしょうぎの将棋盤のデータ構造を考えていきます。
どうぶつしょうぎは縦4マス×横3マスの盤です。これを2次元配列で表現するか、1次元配列で表現するかを選択します。
2次元配列で表現する場合は人間の直感に近いデータ構造になりますが、コンピュータの処理はやや複雑になります。
次に配列に格納するオブジェクトを何にするかを検討します。
値型にしろ参照型にしろ、配列の要素としては大きさは同じになりますが、その扱いやすさがやや異なります。
「駒」オブジェクトの配列にすると、如何にもオブジェクト指向ぽく便利な面も多いですが、盤に配置された駒がどんな駒であるかを分かるためには、特別な関数を経由しなくてはいけなくなり、不便です。また、そのコストも高くなります。
一方、駒を int で表現し、盤を int 配列にすると、駒の配置を人間が読むことは簡単にできます。特別な関数を通すことなくできますので、余分なコストも掛りません。例えば、{4,
8, 6, 0, 2, 0, 0, 3, 0, 7, 9, 5}のように盤を表現することができます。
これから将棋盤 board のデータ構造を以下のようなものが考えられます。
(1),(2) 駒クラスの配列 int column = 3; int row = 4; Piece[] board = new Piece[column * row]; (3) int 配列 int column = 3; int row = 4; int[] board = new int[column * row]; (4) char 配列 int column = 3; int row = 4; char[] board = new char[column * row]; (5) String 配列 int column = 3; int row = 4; String[] board = new String[column * row];
持ち駒も将棋盤とほぼ同様のデータ構造になります。
どうぶつしょうぎでは持ち駒の種類が少なく、その駒数も最大2枚までという制約があるため、効率の良いデータ構造を考えることもできるでしょう。
持ち駒は先手、後手ともライオンも含めても最大7枚になります。
先手と後手の持ち駒を別個に管理するために、以下の2次元配列を考えます。
(1),(2) 駒型配列 Piece[][] pieces = new Piece[2][7]; (3) int 配列 int[][] pieces = new int[2][7]; (4) char 配列 char[][] pieces = new char[2][7]; (5) String 配列 String[] pieces = new String[2][7];
ここまでで、駒と将棋盤、持ち駒のクラスとそのデータ構造を考えてきました。 駒クラスをどうするのかは、その操作を決めるときにも悩むことになります。つまり駒クラスにどのようなメソッドを定義するかです。 例えば、駒の着手可能手(合法手)を探すメソッドを駒特有のメソッドにするか、共通的なものにするかなどになります。
でも楽しく気楽に考えてください。もし作っていて不便だと感じたら、作り直せばいいのです。 作り直したときは、きっと前のプログラムよりもエレガントになっているでしょう。
他にも必要になってくるデータ構造やクラスは多々ありますが、とりあえず、ここまでのものでどうぶつしょうぎは作れます。
プログラムを楽しく作るコツは少しずつ作っていくというものがあります。
ここまでのものを使って、初期画面を配置して、それを表示するものを作ってみましょう。
最初は動作確認のためにキャラクタで表示するものでもいいでしょう。実は私の作ったどうぶつしょうぎの JavaApplet 版にもキャラクタ表示するモードが残っています。
以下のような感じで作ってみましょう。
(1), (2) 駒配列 class Board { Piece[] board; ... void display() { // A4から横方向優先で C0までをキャラクタで表示する for (int i = row; i > 0; i--) { for (int j = 0; i < column; j++) { // キャラクタで将棋盤と駒を表示する System.out.println(board[(i - 1) * column + j].toString()); } System.out.println(); } } } (3) int配列 System.out.println(board[(i - 1) * column + j].toString()); の部分が System.out.println(name[board[(i - 1) * column + j]]); のように実装します。 toString()のメソッドや name[]の配列の実装については自分で考えてみてください。
コンソール版のどうぶつしょうぎの例を以下に示します。
----------------------- 後手持ち駒: |A|B|C| 1|キ|ラ|ゾ| 2| |ヒ| | 3| |ひ| | 4|ぞ|ら|き| 先手持ち駒: 指し手: 先手 ----------------------- コード 着手可能手(合法手) 13a A3らいおん 15a C3らいおん 258 C3きりん 472 B2ひよこ 指し手?(コードを入力)>
着手可能手(合法手)とは、ある駒が指せる手のことを指します。
例えば、図の B3 にいるキリンであれば、着手可能手は、B2, A3, C3, B4になります。 この図では、着手可能手を赤枠で囲っています。
将棋盤を一次元配列で左下のA4, B4, C4, A3, ..., A1, B1, C1のように順に表現しているものを考えます。 つまり A4
が board[0]で C1 を board[11]で表現します。 このとき、キリンのいる B3 は board[5]になります。
キリンが動ける場所は 1, 3, 5, 7になります。 盤の境界を考えなければ、キリンのいる位置を x とすれば、x - 3, x - 1, x + 1, x + 3 となります。 しかし、どうぶつしょうぎは盤が小さく境界を考えなくていい場所は12マスのうち、たった2マス(B2, B3)だけになります。 つまり、境界の判定をしなければいけない位置の方が圧倒的に多いのです。 着手可能手を見つけるプログラムは以下のようなものが考えられます。
この方法が一番、オブジェクト指向的で、オーソドックスなものになります。
以下のような関数を考えます。どの関数も実装表現は異なりますが意味は同じです。
・search(駒, 盤上の位置) → その駒が動かせる盤上の位置の集合
・Positions search(Piece piece, Position position);
・int[] search(Piece piece, int position);
この関数の結果を計算して実行時に求めるのではなく、あらかじめ解をエンコーディングしておきます。 例えば、配列 search に解を格納しておきます。
例. search[キリン][B3] = {B4, A3, C3, B2} → search[キリン][4] = {1, 3, 5, 7} (位置情報を int に変換したもの)
人間の手でエンコーディングすると間違いますので、通常は上記のデータを生成するためのメタプログラムを組みます。
しかし、どうぶつしょうぎは小さい将棋盤ですので、手動でコーディングしても大丈夫でしょう。
上記で得た着手可能手の行き先に、自分の駒がある場合は、着手可能手から外します。相手の駒がある場合と駒がない場合が着手可能手となります。
どうぶつしょうぎの場合は、不成りということがありませんので、着手可能手では気にする必要がありません。
(参考)本将棋を作るときには、不成りも考慮して作る必要があります。
持ち駒はすべての空き場所に打てますので、着手可能手に加えるようにします。
但し、同じ駒が持ち駒にあるときは全く同じ着手候補手になりますので、一種類にします。
(1) 以下の図で示される局面を表現するデータを作成してください。
このためにはクラス設計とデータ構造設計が必要になることに注意してください。
(2) 次に着手可能手を求めるプログラムを作成してください。
どうぶつしょうぎのデータ構造とクラス設計その 2 です。
その 1 では駒と将棋盤、持ち駒を考えてきましたが、ここではまず、指し手のクラスを考えていきます。
例えば、B3 にいたひよこが B2 に移動することを「B2ひよこ」と言います。この動きをどのようなデータ構造にするかを考えます。 この指し手は(1)元いた場所と(2)動く行き先の場所、そして(3)動かす駒の情報があれば、大丈夫でしょう。
但し(1)の元いた場所の情報から(3)の動かす駒の情報は将棋盤から取り出すことはできますので、(3)は必須ではありません。
以下のような実装が考えられます。
class Hand { int from; // 元いた場所 int to; // 動かす場所 int piece; // 動かす駒 (駒の実装によって Piece piece となる) }
前節で求めた着手可能手を保管するためのデータ構造を考えます。着手可能手は指し手の集合になりますから、Java での実装では指し手のコレクションクラスにするのがいいでしょう。
(1) コレクションクラスを作成 class Hands { List<Hand> hands; Hands(int size) { hands = new ArrayList<Hand>(size); } } (2) コレクションフィールドを作成 List<Hand> hands = new ArrayList<Hand>(size);
もし Java 以上の機能を持つ言語で作成するのであれば、この実装でいいでしょう。 しかし、JavaMe の低レベルのプロファイルや C、JavaScript、 さらにアセンブラで実装する予定があるのであれば、移植性を考慮して、配列で実装するのがいいでしょう。
(3) 配列で作成 class Hands { Hand[] hands; hp = 0; Hands(int size) { hands = new Hand[size]; hp = 0; } }
ここではどうぶつしょうぎのプレーヤについて書いていきます。
プレーヤの機能はどうぶつしょうぎを「指す」ことです。人間プレーヤであろうが、コンピュータプレーヤであろうが指すことが使命になります。
現状の局面を判断して指すことになります。
人間プレーヤもコンピュータプレーヤもプレーヤのサブクラスとして実装します。
プレーヤクラスをインタフェースにするか抽象クラスにするかは実装依存になりますが、抽象度の高い抽象クラスにまずはしておきます。
/** プレーヤクラス */ abstract class Player { protected Result play(){ return null; } } /** 人間プレーヤ */ class Human extends Player { protected Result play(){ return null; } } /** コンピュータプレーヤ */ class Computer extends Player { protected Result play() { return null; } }
ここで Result は試合状況を返すものです。勝ったや負けたなどを返すようにします。int でもいいでしょう。
人間プレーヤは GUI を作成するまでは、コンソール入力があるとデバッグに便利でしょう。
以下にサンプルプログラムを紹介します。試合結果は int で返すようにしています。
public class Human extends Player { private BufferedReader in; /** * 人間クラスのコンストラクタ * 手動で指す * @param phase 局面 */ Human(Phase phase) { super(phase); in = new BufferedReader(new InputStreamReader(System.in)); } /** * コンソール画面から指す * @return その指し手の結果 */ protected int play() { Hand hand; int victory = ingame; try { System.out.print("指し手?> "); String input = in.readLine(); hand = string2hand(input); victory = phase.play(hand); } catch (IOException e) { e.printStackTrace(); } return victory; } ... }
実際の実装では、以下のようにコンソール入力の前に着手可能手を表示し、その中から選択させるようにした方がいいでしょう。
コード 着手可能手 13a A3らいおん 15a C3らいおん 258 C3きりん 472 B2ひよこ 指し手?(コードを入力)>
コンピュータプレーヤについては、後日、紹介します。
コンピュータ将棋を作るときに、どうぶつしょうぎを作るアルゴリズムと本将棋のとは同じになるのでしょうか。それとも違うものになるのでしょうか?
両者を作成してみましたが
「考え方も異なり、作り方も異なります」
というように感じています。
もちろん、本将棋のプログラムをどうぶつしょうぎに転用することは可能です。 しかし、これは
「近所のコンビニへ買い物に行くのに、宇宙ロケットで行くようなものです」
となります。決して大げさな表現ではありません。
実装は可能ですが、実装するのは非常識です。開発コストも悪いです。
そして肝心なことは「実行が遅い」ということです。
例えば、既に説明した着手可能手を見つけるアルゴリズム一つを取ってみても、本将棋でやりがちな駒単位の検索はどうぶつしょうぎでは効率的にはありません。
実行が遅いのです。
また細かい話になりますが、本将棋ではスタックに余計に1個積んでも無視できる程度ですが、アルゴリズムが簡単なのでどうぶつしょうぎでは勿体ないのです。 特にどうぶつしょうぎをアセンブラで作成することを考えるとこれは勿体ないです。
やや言い過ぎていますが、どうぶつしょうぎは「組込ソフトウェア開発」と同じ技術が必要になります。
つまり「どうぶつしょうぎは本将棋の夢を見るか?」に対するコメントは、どうぶつしょうぎは本将棋の夢を見ないのです。リバーシの夢を見るのです(意味不明?コラムですから・・・許してください)。
ここでは評価関数を考えていきます。評価関数とは現状の局面が有利かどうかの評価を行う関数です。この評価関数が返す評価値を元に、その局面が有利か不利かを判断します。
そして、この評価関数を使って、各々の着手可能手を指した局面の評価を行い、着手可能手から一番有利な局面となる指し手を探し、その手を指すようにします。
さらに、現在の着手可能手で指した局面だけでなく、さらに次の着手可能手、さらに次の手と進めた局面の評価を行うことがあります。
これを「先読み」と言い、何手先読みするかで、例えば、5手先読みと言います。
先読みについては後日、書くことにします。
ここでは評価関数の例を見ていきます。
まずは評価関数を使わないときの指し手の選択の例を考えます。これには以下のものが考えられます。
次に局面から評価する評価関数の例を考えていきます。
もちろん、この評価関数を全部実装する必要はありません。また逆に上記以外の評価関数も考えられるでしょう。
少なくとも王手逃れとトライ逃れの評価関数は必須でしょう。王手やトライを高くすると、どうぶつしょうぎに多い引き分けの確率が小さくなり、面白いゲームが期待できます。
評価関数は本将棋のものとは異なってくるでしょう。パラメータが違うのは当然ですが、考え方が違う評価関数もあります。 例えば、上で挙げたライオンの位置などはどうぶつしょうぎの独特の評価関数の考え方になるでしょう。 どうぶつしょうぎに合った評価関数を考えていくのは面白いでしょう。
(1) 与えられた局面の評価を行う評価関数を作成してください。
(2) 作成した評価関数で、左図の局面を評価してください。
注意: 後手番であることに注意してください。つまり、評価関数は後手側で行ってください。
(3) 他の局面も想定して、その局面の評価関数を作成してください。
この演習2には、どうぶつしょうぎを作成するときの多くのヒントがあります。
例えば、常に評価関数の評価をします。そして、それがしやすい作りにしていくのが重要となります。
その部分をホットスポットとして作成する必要があります。そのようにクラス設計をします。
評価関数を作成しましたので、ここでどうぶつしょうぎのゲーム本体を作ってみましょう。
ここでは、まだユーザインタフェースはコンソール画面での入出力にします。 プレーヤは固定でも構いません。
例えば、先手を人間、後手をコンピュータにしてみてください。 ゲームの終了判定が無くても構いません。
無限ループにしておいてもいいでしょう。
以下にゲーム本体のプログラムの最初の方のサンプルプログラムを示します。
/** * ゲームループ * returns 試合結果 */ private int mainloop() { int victory = ingame; // 試合結果 for (int i = 1;; i++) { // 結果が出るまで無限に指す victory = play(); if (victory == victoryfirst || victory == victorysecond || victory == victorydraw) break; phase.changeSide(); // 手番の交代 } return victory; } /** * 一手指す * @returns 試合結果 */ private int play() { Player player = phase.getSidePlayer(); // 現在の手番のプレーヤ return player.play(); // 現在の手番側が1手指す }
ここまでで、評価関数を作成し、ゲームを作成してきました。 ゲームをしてみるとコンピュータが予想もしない手を指してくることがあります。 これは自分が作った評価関数に対する考慮が足らないのか、または評価関数のバグです。
ここではその評価関数のデバッグの方法について考えてみます。 評価関数のデバッグを効率的に行うためには、バグだと予想している指し手が出る直前の局面にする必要があります。 これを一手ずつ指しているのは・・・全く非効率です。
評価関数のデバッグを効率的に行うためには、盤、持ち駒、手番の設定が簡単にできるようにしておくと良いでしょう。 また、これはデバッグのためだけでなく、テストケースの実施のときにも役立つでしょう。 以下に局面設定の例を示します。
// 盤面配置 int[]inboard = new int[]{zou1, lion2, kirin1, nil, nil, nil, nil, zou2, nil, kirin2, lion1, nil}; // 持ち駒 int[][]inpieces = new int[][]{{hiyoko1, nil, nil, nil, nil, nil, nil, nil}, {hiyoko2, nil, nil, nil, nil, nil, nil, nil}}; // 手番 int inside = PieceConst.first;
ここでは GUI を作成していきます。最初に画面設計をして画面を作成していきます。 次に入力部分を作成、動作モデルを完成させます。
GUI の画面を作成していきます。
画面は、論理的な部品で作成し配置もシステムに任せるものと、物理的な画面部品(原始的な画面部品)を使って配置も原始的にすべて行う方法があります。
さらに両者の組み合わせもあります。
どうぶつしょうぎは、画面制御を細かく行うことが多いので、原始的な方法になることが多いでしょう。
つまり、画面設計は配置も含めて、すべて自分で制御するようにします。
このため、画面部品の大きさや位置、配置を後から変更するときにコストが掛る危険性があります。 後で(1)調整が少なくなるように画面設計は将来を見越して行い、また(2)画面設計が変わっても変更量が少なくて済むように設計する必要があります。 どんなに(1)で将来を見越しても必ず画面変更は生じます。(2)も重要です。でも(1)を疎かにすると(2)で痛い目に会いますので、両方とも大事です。 次に(1)と(2)を実施するためのやり方を見ていきます。
画面設計を行う方法としては、(a) プロトタイピングによる画面設計の方法と、(b) 方眼紙で設計する必要があります。 これはどちらでもいいでしょう。プログラマの人は当然(a)になるかと思いますが、何回もプロトタイピングをしてしまう人は一度、方眼紙に書いてみてください。 プロトタイピングが効率的に実行できます。
どうぶつしょうぎでは、以下のものを画面に配置してみます。
・ゲームタイトル
・サブタイトル
・将棋盤
・駒台
・棋譜表示ボックス
・手番表示
・直前の指し手
・システムメッセージ
・各種のボタン
これらをセンス良く、作成し、配置していきます。
左図はその例ですが、例えば、持ち駒は小さくてもいいでしょう。
どうぶつしょうぎでは、持ち駒はライオンも入れれば最大7枚になりますので、配置にはそれを考慮してください。ライオンを入れないときは6枚になります。
ここで画面設計のコツを伝授します。
原始的な画面設計を行うときは1ピクセル単位で設定できますが、それをせずに、抽象的な画面単位を考えるのがいいでしょう。どうぶつしょうぎでは駒のサイズを1基本単位として制御することが考えられます。駒のサイズが大きすぎるときはその半分を基本単位にすることでやや細かな制御ができます。
画面設計は、プログラミングの楽しみの一つです。楽しみながら、画面設計をしていってください。
ここでは画面の抽象化について考えていきます。
画面の抽象化とは何でしょうか?
それは画面を原始的な方法で作成していくときにも、画面部品のサイズや配置を抽象化する方法です。
以下のプログラムを見てください。
private void paintPiece(Graphics g, int piece, int x, int y) { if (images[nil] != null) images[nil].paintIcon(this, g, x, y); if (piece == nil) return; if (images[piece] != null) images[piece].paintIcon(this, g, x + 3, y + 3); }
上のプログラムは、座標は直接な x と y で与えています。また 3 という厚さをハードコーディングしています。
それと比較して、下のプログラムを見てください。
private void paintPiece(Graphics g, int piece, int index) { int x = getXposition(index); int y = getYposition(index); if (images[nil] != null) images[nil].paintIcon(this, g, x, y); if (piece == nil) return; if (images[piece] != null) images[piece].paintIcon(this, g, x + bold, y + bold); }
上のプログラムは、座標は index から求める位置になっています。例えば、index は抽象的な盤上の位置を示しているでしょう。
また、厚さを bold という変数の値で抽象化しています。
さらに PC 画面版と携帯電話の画面版との共通化を行う抽象化も考えることができます。
事実、どうぶつしょうぎ・携帯アプリ版は、同じプログラムで複数の画面サイズをサポートしています。
ここでは画面の再描画について考えていきます。
Java の Swing では、再描画は repaint() で行います。 この repaint は描画の要求を JavaVM に出すだけで、直ぐに表示されるとは限りません。
そこでゲームプログラムでは、この repaint を使わずに直接描画するアクティブレンダリング active rendering を行います。
しかし、どうぶつしょうぎのような画面描画がゆっくりなものでいいときは、アクティブレンダリングを使うまでもないでしょう。
そこでどうぶつしょうぎでは、paintImmediately(x, y, width, height) を使います。但し、これはコストが高いので、直ぐに描画してほしいところのみで使用します。
例えば、指し手を描画するところで使うといいでしょう。
(注意)Swing はシングルキューの簡単な実装をしています。このため、画面制御は細かな優先制御や真の意味の並列動作はできません。
疑似的な並列動作をしていますので、細かな制御をしたいときは自分でスケジューリングする必要があります。
この部分は、この連載の範囲外になりますので、別にしたいと思います。
画面表示の次は、いよいよ GUI の作成になります。
Swing は他の GUI 動作モデルと同様に、イベント−ハンドラ型の動作になります。
マウスのクリック動作などのイベントが Swing(JavaVM)に到達したら、それに対応するハンドラが呼び出される動作モデルです。
どのイベントを動作対象にするかは、リスナーと呼ばれるプログラムに登録します。
ユーザはハンドラのみを定義することで GUI を作成していきます。
ハンドラはSwingから呼び出されますので「コールバック」とも呼ばれています。
つまり、メインループはユーザが作成するのではなく Swing が持っているメインループを使い、そのメインループから自動的に呼び出されるハンドラのみを記述します。
これはユーザのプログラミングが容易になるというメリットがあります。逆に細かな制御ができないというデメリットもあります。
以下にボタンをマウスクリックしたときのサンプルプログラムを挙げます。
/** * マウスがクリックされたとき * @param mouse マウスイベント */ public void mouseClicked(MouseEvent mouse) { int x = mouse.getPoint().x; int y = mouse.getPoint().y; // 以下、省略 }
上記は、どうぶつしょうぎのゲーム盤で、マウスクリックされたときに Swing から呼び出されるメソッドです。
最初は、現在のマウスがクリックされた位置を mouse.getPoint()で取得しています。
その後、マウスがクリックされた位置でどの駒が動作対象になったかを判定するようにしていきます。
ゲーム盤だけでなく、各種のボタンなどのハンドラも作成していきます。
画面部品の配置やリスナーの定義は以下のようにします。
/** * 画面コンポーネントの初期配置 */ private void initComponents() { message = messageInStart = "開始ボタンを押してください"; messageInGame = "動かしたい駒をクリックして次に動かす場所をクリックしてね"; this.setSize(width, height); this.setVisible(true); button1 = new JButton("開始"); button1.setActionCommand("start"); add(button1); button1.setBounds(xorigin + 0 * (pieceSize + bold), yorigin - 48, pieceSize, 20); button1.setVisible(true); button1.addActionListener(this); // 他のボタン類は省略 scoreBoard = new JTextArea("棋譜"); scoreBoard.setFont(new Font("Default", Font.PLAIN, 11)); scrollScoreBoard = new JScrollPane(scoreBoard); add(scrollScoreBoard); scrollScoreBoard.setBounds(xorigin + 10 + 6 * (pieceSize + bold), yorigin, (pieceSize + bold) * 2 - 56, (pieceSize + bold) * 4); scrollScoreBoard.setVisible(true); scrollScoreBoard.addMouseListener(this); this.addMouseListener(this); this.setLayout(null); }
上記は開始ボタンと棋譜表示エリアの配置をして、そのリスナーを設定しています。 また最後に this.addMouseListener(this) と書くことで、マウスリスナーを全体(実は JPanel)に設定することをしています。
演習として、以下の仕様で、どうぶつしょうぎの GUI を作成してください。
(1) 開始ボタンを押すと、ゲームがスタートします。
(2) 対戦は先手人間、後手コンピュータを実装してください。
(3) 現在の手番を明示してください。
(4) 直前の指し手や動かす駒、着手候補手の明示、棋譜表示などはこれから作成するようにしますので、その予定にしておいてください。
これから、先読みによる評価関数の適用について書いていきます。 その前に、ここではその基となる「ゲーム理論」を紹介します。
ゲーム理論とは数学の一分野で、文字通り、ゲームで勝利するための理論になっています。
ゲームには色々なものがあり、その適用としては、株式売買やネットワーク機器の割り当て、将棋などのゲームなどがあります。
どうぶつしょうぎは、(1) 完全情報であり、 (2) 二人零和、(3) 有限確定ゲームとして、分類されます。
つまり、(1) ゲームに関する情報は乱数などを使わずに完全に公開されていて、(2) 二人のうち、どちらかが勝って、どちらかが負けるゲームです。
零和なので、相手をやっつければ自分が勝てるゲームです。そして勝敗が有限回で決まる、確定できるゲームです。
ゲーム理論はこのような「二人零和有限確定完全情報ゲーム」に関しても色々な有用な結果を与えています。
以前に作成した評価関数を作成して、その中で1番良い手を指すのもゲーム理論の教えの一つになっています。
これから紹介する先読みの考えも、指し手を限定するために行うα−β刈りもゲーム理論の教えの一つになっています。
ゲーム理論に興味をもたれた方は専門書をお読みください。きっと他のところでも役に立つでしょう。
人間が実際にどうぶつしょうぎを指すときにも、きっと先読みをしています。
「私がこの手を指したら、相手はたぶんこのように指してくるだろう。このときはこの手を指そう。」
このようなイメージでどうぶつしょうぎを指していると思います。これは自分の指し手、相手の指し手、さらに自分の指し手を読んでいますので、「3手先読み」になります。
これをコンピュータの思考ルーティンにも入れるようにします。
この3手先読みは頭の中ではどのように考えているのでしょうか?
最初の手は今の局面で一番良さそうな手を想定しているでしょう。
次に相手の立場になって、一番良さそうな指し手を考えるでしょう。
そしてさらに一番良さそうな手を探して、その指し手の結果が良さそうであれば、最初に考えた手はいい手だと思うでしょう。
これだけを考えると3手先読みは簡単に思えるかも知れませんが、最初に良さそうと考えた手に対する相手の指し手が逆転するくらいのいい手があったときが問題になります。
そのときはその先を考えるのも止めて、第一手を考えることに戻るでしょう。
また、最初に良さそうと思った手でもさらに良い手があるかも知れません。可能性のある手を全部探すようになるかも知れません。
このような考えをプログラムで表現する必要があります。しかし実はそれほど難しいことではありません。
ゲーム理論ではこれを実装するために、「ミニマックス法」や「αβ法(α-β刈り)」の考えが用意されています。
つまり、ミニマックス法とは、上で述べたように、「自分は最大限の評価値を得るように手を指し、相手は自分にとって最小限の評価値になるように手を指す」というものです。
このミニマックス法がすべての手を考えるのに対し、αβ法は閾値を超えた手、自分にとってはもうこれ以上望まなくてもいい評価値、
相手のときはひどい評価値でこれ以上考えても仕方がないくらいの悪い評価値になれば、その場で考えるのを止めることにして、その思考範囲を絞り込むことです。
それではここでミニマックス法と考えていきます。
ミニマックス法とは前の節でも述べたように、
自分の手番のときは最大限の評価値になるように探索し、
相手の手番のときは自分の評価値が最小限になるように指すように考えることです。
もう少し、詳細に考えていきます。ここでは簡単化のために2手だけを考えます。
つまり、自分の手番のときに指す手 h1(1), ..., h1(n) とそれに対して相手が指す手 h2(h1(1),1), ..., h2(h1(1),n1),
h2(h1(2),1), ..., h2(h1(2),n2), h2(h1(n),1), ..., h2(h1(n),nn)を考えます。
但し、h1(m)は先手の着手可能手の m 番目の手とします。 また h2(h1(m),l)は h1(m)の手を指した後の盤面の着手可能手の l
番目の手とします。
手に対する評価関数 e を考えます。
このときに、h1(1)の手を指したときに、相手の指す手は e(h2(h1(1),1)), ..., e(h2(h1(1),n1))の中で最大値となる手を指します。
同様に h1(2)の手を指したときは、 e(h2(h1(2),1)), ..., e(h2(h1(2),n2))の中で最大値となる手を指します。
このように考えると h1(1)からh1(n)までで相手の指す最大値の評価値を最小にする手を考えればいいことになります。
つまり、以下のようになります。
指し手は h1(i)となります。
但し、h2(h1(i), nj) = min(max(h2(h1(1),1), ..., h2(h1(1),n1)), max(h2(h1(2),1), ..., h2(h1(2),n2)), ..., max(h2(h1(n),1), ..., h2(h1(n),nn)))となります。
ミニマックス法は全探索で、途中の枝刈り(考えるのを止めること)は考慮していません。 このままでは使い物になりませんので、少なくとも勝ちが確定したときや負けが確定したときは、その先を読まないようにする必要があります。
αβ法は、ミニマックス法の改良版で、探索が必要ないときは、探索を途中で止めるものです。 マックス(最大値)を計算するときはα値(下限値)以下になっているときは、探索をしなくても、ミニマックス法と同じ結果が得られます。 これをαカットと呼びます。以下の図を参照してください。
βカットも同様にできます。以下の図を参照してください。
上記のαカットとβカットを使うαβ法は、後ろ向き枝刈りの一つで、ミニマックス法と同じ結果が得られます。
次に前向き枝刈りを見ていきます。
前向き枝借りはミニマックス法の近似解を得るものです。
色々な方法がありますが、ここでは閾値によるウィンドウ制御を見ていきます。
この方法ではn手先読みするまでの途中の手順での評価値を計算し、
上限または下限の閾値を超えていたときにはそれ以上の先読みをしない方法です。
これはあまりにも悪くなった局面では数手では逆転はされないだろうということと、その逆にあまりにもいい局面のときはしばらくは逆転されないだろうという考えに基づいています。
もちろん、勝ちや負けが確定したときには逆転はありえませんから、これ以上の先読みを止めるようにします。
しかし、どうぶつしょうぎでは本将棋よりも逆転は日常茶飯事に起きます。このために閾値は大きくせざるを得ず、結果的には勝ち負けが確定しているときを先読みしない程度になりがちです。
ここでは、ミニマックス法やαβ法による先読みの実装を考えていきます。
7.3 節で紹介したミニマックス法を見ていきますと、先手と後手が入れ替わっても、結局は同じことをしていることに気付くはずです。
このようなことを実装するときは、繰り返しを使うか、再帰を使います。
両者に本質的な差はありませんが、再帰の方はローカル変数やリターンアドレスが自動的にスタックに積まれるために手間が少なくなる可能性があります。
しかし逆に不要なローカル変数やリターンアドレスを積んでしまい、遅くなることもあります。
今回は再帰を使って、先読みを実装してみます。以下にサンプルプログラムを掲載します。
n手先読みの MinMax法アルゴリズムの概要 1. 着手可能手(合法手)から以下を繰り返す。 1.1 局面情報(盤面、持ち駒、手番)を保存する 1.2 着手可能手から1手選ぶ 1.3 選んだ手で1手指し、局面を1手進める 1.4a 指し手が n手目のとき 評価関数で現在の局面の評価値を計算する 1.4b 指し手が n-1 手目以前のとき 手番を交代し、手数を1手進め、このアルゴリズムを再帰呼び出しする 1.5 再帰呼び出しから返ってきた評価値を今までの評価値と比較する 奇数手(自分の手番のとき)は大きい方を選択し、偶数手(相手の手番)のときは小さい方を選択する 1.6 選択した評価値を記録する。1手目のときは指し手も記録する(グローバル変数でも可)。 1.7 保存していた局面情報を元に戻す 1.8a 着手可能手が残っているとき 次の指し手をチェックするために1.1に戻る 1.8b 着手可能手が残っていないとき 奇数番目(自分の指し手)のときは評価値の最大値を返し、偶数番目のときは最小値を返す
/** * N手先まで読んで指す(枝刈りはなし) * @param deep 先読みする手数 * @return 評価値 */ protected int play(int deep) { int max = this.initmax; // 最大評価値の初期値(小さい値) int min = this.initmin; // 最小評価値の初期値(大きい値) boolean maxp = ((this.deep - deep) % 2) == 0; // 現在の手が自分の手(α)か相手の手(β)かをチェックする int point = 0; // 評価値 List<Hand> hands = phase.search(); // すべての着手可能手を得る for (int i = 0; i < hands.size(); i++){ phases.push(phase.clone()); // 現在の局面をスタックにプッシュして保存 Hand hand = hands.get(i); // 着手可能手の一手を得る phase.play(hand); // 一手指す if (deep < 0) { // n手目かどうか point = eval.eval(phase); // 現在の局面の評価値を得る } else { phase.changeSide(); // 手番の交代 point = play(deep - 1); // 再帰呼び出しして、さらに1手先読みする if (maxp) { // どちらの手番か if (max <= point) { // 自分の手番 max = point; // 自分の手番のときは評価値の最大値をセットする if (deep == this.deep) this.bestHand = hand; // 1手目のときは指し手も記録する } } else { if (min >= point) min = point; // 相手の手番のときは評価値の最小値をセットする } phase.recover(phases.pop()); // 局面を戻す } return maxp ? max : min; // 自分の手番のときは評価値の最大値を返し、そうでなければ最小値を返す }
/** * N手先まで読んで指す(前向き枝刈りあり) * @param deep 先読みする手数 * @return 評価値 */ protected int play(int deep) { int arfa = this.arfa; // this.arfa --- α閾値(大きい方の閾値) int beta = this.beta; // this.beta --- β閾値(小さい方の閾値) int max = this.initmax; // 最大評価値の初期値(小さい値) int min = this.initmin; // 最小評価値の初期値(大きい値) boolean maxp = ((this.deep - deep) % 2) == 0; // 現在の手が自分の手(α)か相手の手(β)かをチェックする List<Hand> hands = phase.search(); // すべての着手可能手を得る for (int i = 0; i < hands.size(); i++){ phases.push(phase.clone()); // 現在の局面をスタックにプッシュ Hand hand = hands.get(i); // 着手可能手の一手を得る int victory = phase.play(hand, false); // 手を指す int point = eval.eval(phase); // 現在の局面の評価値を得る if (point < arfa && point > beta) { // α以上か、β以下のときは先読みをしない if (deep >= 0) { phase.changeSide(); // 手番の交代 point = play(deep - 1); // 1手先読み } } else if (point >= arfa) { // 枝刈りするときに相手の手番のときは評価値を逆に調整する if (!maxp) point = beta; // 相手が枝刈りするくらいにいい評価値のときは、悪い評価値にする else if (!maxp) point = arfa; // 相手が枝刈りするくらいに悪い評価値のときは、いい評価値にする } if (maxp) { if (max <= point){ max = point; // 自分の手番のとき(αのとき)は評価値の最大値をセットする if (deep == this.deep) this.bestHand = hand; // 1手目のときは指し手も記録する } } else { if (min >= point) min = point; // 相手の手番のとき(βのとき)は評価値の最小値をセットする } phase.recover(phases.pop()); // 局面を戻す } return maxp ? max : min; // αのときは評価値の最大値を返し、βのときは最小値を返す } // プログラムの簡略化のために、枝刈りした後で先読みはしないが、勝ちが確定している場合でも、次の手は読んでいる // 次の手も高速化のために枝刈りするのが望ましい
枝刈りについてはαβ法の箇所でも紹介しましたが、ここでもう一度まとめてみます。
先読みをするときに、指し手を読んでいるときに、その評価値があまりにも高くなったときか低くなったときは、深く読んでも、この先に逆転はないだろうと考えることです。
これで、それ以上の先読みをしないようにするのが、枝刈りです。
枝刈りの実装そのものは難しくはありません。しかし、その枝刈りをする閾値のパラメータ調整は大変です。
これがどうぶつしょうぎのノウハウです。
本将棋では、序盤、中盤、終盤で閾値を変化させることもあります。しかし、どうぶつしょうぎではその区別が難しいため、この方法を実際に使うのは難しいでしょう。
ここでは、枝刈りの実装について考えていきたいと思います。
評価関数の調整とともに、枝刈りの調整は困難です。
これは、これらを調整をするには先読みも含めた評価関数の表示が必要になり、かつどうぶつしょうぎと言えども、その枝の数は莫大な量になるからです。
評価関数の実装では、一般的にゲームツリー(先読みした手とそれに対応する評価関数をノードとするツリー)はメモリ上に保存するのではなく、α値またはβ値を取りだすために、最大値または最小値のみを注目するだけです。
しかし、これでは評価関数や枝刈りの調整が困難になります。
これから、調整段階ではメモリ上にゲームツリーを保存し、ゲームの本番の時には保存しないようにします。
また、勝ち確定や負け確定を評価関数の一部として実装している場合は、枝刈りの閾値とは別に、勝ち負け確定の閾値が必要になることに注意してください。
枝刈りの効果は大きいと言えます。枝刈りの結果、思考ルーティンが高速になり、先読みの深さが大きくなると、その分だけ「将棋の神様」になり、強くなります。 しかし、どうぶつしょうぎは逆転が多い将棋ですので、枝刈りの閾値には十分注意する必要があります。
先読みをしていると、コンピュータ側が負けることが分かる場合があります。
例えば、n 手先読みするときに、すべての探索したゲームツリーで、負けるというときがそれです。
このときは、どんな手を指しても同じです。負けるだけですから。
でもなるべく、いい手を指すようにします。つまり、「負ける時も最後までがんばる」です。
もしかしたら、相手が間違った手を指して、逆転勝ちになる可能性もありますから。
「最後までがんばる」とは、どういう手でしょうか。
一番いいのは、「紛れ」のある局面にする手がいいです。
相手の人間または、完全先読みをまだしていないコンピュータ相手に、間違わせるような紛れのある局面にするのがいいです。
この紛れの局面のためには、それ用の評価関数が必要になります。今までの勝つための評価関数とは異なるでしょう。
この紛れの実装は困難ですので、普通は「最長手順」になるように指します。
このためには、負けが分かったときに選ぶ手の判断が今までと違ってきますので、調整するようにします。
今日は負けることが分かったときの指し手の話でしたが、勝つことが分かったときも同様に評価関数を変えることも考えられます。
でも、どのような手を指しても勝つのは保証されますので、負けるときよりも優先度は低いでしょう。
それでは演習として、枝刈りを作ってみてください。
ここで必要条件としては、勝ち負けが確定したときは、それ以上の先読みをしないようにすることがあります。
これは本来的には枝刈りではありませんが、枝刈りの一部として実装すると便利です。
勝ち負けの確定以上の枝刈りを実装してください。評価関数が高低でどの程度の閾値になったかのみで枝刈りをするといいでしょう。
枝刈り自身はシンプルは判断にし、評価関数で調整する方が、調整を一元化できて便利です。
ここでは、前回の画面と UI に続いての紹介になります。MVC のアーキテクチャ、待ち時間制御そしてイラストの書き方などを紹介していきます。
(この項、未完)
MVC とは、M (Model データ)と V (View 表示)、C (Control (入力)制御)の先頭文字を集めたものであり、この M, V, C の関係に注目したアーキテクチャの一つです。
MVC のアーキテクチャは GUI(グラフィックユーザインタフェース)設計の基本的なアーキテクチャであり、Small Talk-80 によって提唱され、現在ではそれが GUI 設計の基本になっています。
MVC の教えでは、M と V, C は疎結合にして作成するようにし、ごっちゃまぜに作るのはよくないというのがあります。
これは肝に銘じて作成してください。少なくともクラスは、M と V, C は別に作成するようにしてください。
パッケージも別にするのも一つの手です。どうぶつしょうぎのプログラムそのものは小さいですので、パッケージに分けるほどではないかも知れませんが、それを妨げるものではありません。
もし、MVC がごっちゃまぜになったと思ったときは、勇気を持って、「リファクタリング」してください。
これはきっといい影響をプログラムに与えます。
(この項、未完)
どうぶつしょうぎなどの対戦型ゲームでは、人間が考えている間、つまり次の手を入力をするまでは、コンピュータ側はただ待っていることが多いです。
この待ち時間を有効に使うことが考えられます。つまり、マルチスレッド制御にして、コンピュータの思考ルーティンを入力待ちの間にも実行することが考えられます。
これを実装するためには、MVC の制御をマルチスレッドで行う必要があり、全体の変更を必要とします。
ただプログラムの実装が抽象的になっていれば、マルチスレッド化してもそれほど変更量は少ないでしょう。
変更量を少なくするために、シングルスレッド(単純入力待ち)の実装でも、排他制御を考慮して、抽象的に作成するようにしてください。
簡単に言えば、「グローバル変数の禁止」です。Java ではフィールド変数の禁止になります。
禁止は言い過ぎなのですが、シングルスレッドのときでもフィールド変数の操作アクセス(セッタ)で同期制御に注意してください。
待ち時間中に実行する思考ルーティンですが、ユーザからいつ入力割り込みが入るか分かりませんので、どこまで思考したかを細切れに保管する必要があります。
細切れにするところが腕の見せ所です。楽しみながら苦労してみてください。
(この項、未完)
どうぶつしょうぎの駒や盤のイラストを描くときのコツです。
専用のタブレットを持っている人は少ないでしょうから、普通の白い紙に自分の得意なペンで描きます。
鉛筆でもクレヨンでもいいでしょう。色塗りを手描きすると味が出ますが、コンピュータで色を塗るのもいいでしょう。
色をコンピュータで塗る時は輪郭線もしっかりと閉じます。
手描きしたイラストをコンピュータに読み込ませます。スキャナを持っているひとはそれで読み込ませますが、持っていない人はデジカメで撮影します。
斜め補正ができるレタッチツールを持っている人はツールで補正することができますから、適当に光が映りこまないように撮影してください。
そのようなツールを持っていない人は真正面から撮影するようにしてください。
コンピュータに読み込ませたイラスト画像に色を塗ります。レタッチソフトがなければ、Windows 付属のペイントでも十分可能です。
SuperPaint などのフリーツールも便利です。
イラストに残さない輪郭線を塗りつぶした色に変えれば完成です。輪郭線の色を変えるのは最後にしてください。
イラスト作りは感性の問題が大きいですので、何回かリトライしてみてください。楽しんでイラストを描いてください。
どうぶつしょうぎのイラストは、「素材屋じゅん」様の素材を始め、 他の方から提供していただいたイラストを使わせていただいております。
Copyright © 2010 GOMI Hiroshi All Rights Reserved