このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
本講義の前半部分では以下のことを学びました。
Java の言語仕様に含まれている java.util.regex パッケージの活用を考えま す。
プログラム中に含まれる単語の頻度をアルファベット順に並べることを考えま す。
これは、単語ごとに集計を行うので、連想配列として使用できる Map 系のデー タ構造を使います。 さらに、アルファベット順に整列するので java.util.TreeMap を使用します。
プログラムは単語を取り出すごとに、その単語の連想配列を呼び出して 1 加 算するというものです。 単語のパターンは java.util.regex.Pattern により指定します。 そして、この Pattern オブジェクトに対して、 matcher メソッドで Matcher オブジェクトを作成します。 この時、 matcher メソッドの引数は java.lang.CharSequence となっている ため、 java.io.InputStream や java.io.Reader ではなく java.lang.String オブジェクトで与えます。 得られた、 Matcher オブジェクトに関しては、 find メソッドで検索し、 group メソッドで文字列を取り出します。
import java.io.*;
import java.util.*;
import java.util.regex.*;
class Rei {
public static void main(String[] arg) throws IOException {
final BufferedReader br = new BufferedReader(
new InputStreamReader(System.in));
final TreeMap<String,Integer> hindo = new TreeMap<>();
final Pattern word = Pattern.compile("\\p{Alpha}\\p{Alnum}*");
String line;
while((line = br.readLine())!=null){
Matcher m = word.matcher(line);
while(m.find()){
if(hindo.containsKey(m.group())){
hindo.put(m.group(),hindo.get(m.group())+1);
}else{
hindo.put(m.group(),1);
}
}
}
for(Map.Entry<String,Integer> e : hindo.entrySet()){
System.out.println(e.getKey()+": "+e.getValue());
}
}
}
プログラム中に含まれる単語が出現する行番号を列挙するプログラムを作りな さい。
Java には複数の並列的なプログラムの実行を行う Thread という概念があり ます。
Thread を使用すると GUI などのようなイベント駆動型の環境で、様々なイベ ントごとにスレッドを割り当てることで自然なプログラミングを行うことがで きます。
また、インターネット関連のプログラミングにおいても効果を発揮します。 TCP を利用したサーバでは LISTEN するポート(サービスポート) と実際にサービスを行うポートが別です。 クライアントが接続してくると、別のポートでサービスを行います。 そこで、クライアントが接続してきたら、スレッドを起動して、別スレッドで サービスを行うようにすると、サービス中でも他のクライアントのサービスを 受け付けられるようになります。
また、 Java 7 ではマルチコアにそれぞれスレッドが配分され、高速な並列処 理計算が可能になることも予定されています。 今後、CPU のマルチコア、メニーコア化は進むと思われますので、 Thread の プログラミングは今後重要なテクニックになると思われます。
さて、Thread の基本的な作り方は次の通りです。
まず少々わざとらしい例を考えましょう。
StringBuffer に 1 から 100 までの数を表す文字列を 0.001 秒ごとに追加す る処理を 2 回やるプログラムを考えます。 さらに、この StringBuffer をメンバ変数として取り扱い、処理の指定の時は 引数を指定しません。
この処理を並列計算させるのが目標です。
class Rei {
final private static int max = 100;
private static void f(){
for(int i=1; i< max ; i++){
try{
Thread.sleep(1);
}catch(InterruptedException e){}
sb.append(i+" ");
}
}
private static StringBuilder sb;
public static void main(String[] arg){
sb = new StringBuilder();
f();
f();
System.out.println(sb);
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
次に、この処理部分を別クラスにすることを考えます。 StringBuffer はコンストラクタで与えます。
二回の処理に関して、同じオブジェクトのメソッドを二度呼ぶのではなく、二 つのオブジェクトを作って、一回ずつ呼び出します。 ただ、コンストラクタに同じオブジェクトを入れているので、別々のオブジェ クトで文字列を追加しても、上書きされずに連結されます。
class T {
final private static int max = 100;
final private StringBuilder sb;
public T(StringBuilder sb){
this.sb = sb;
}
public void f(){
for(int i=1; i<max ; i++){
try{
Thread.sleep(1);
}catch(InterruptedException e){}
sb.append(i+" ");
}
}
}
class Rei {
public static void main(String[] arg){
final StringBuilder sb = new StringBuilder();
final T t1 = new T(sb);
final T t2 = new T(sb);
t1.f();
t2.f();
System.out.println(sb);
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
作成した、一個の処理をするクラスをスレッド化します。
java.lang.Thread を継承し、処理の名前は public void run()
にします。
一方、処理の呼び出しには run を使用せず、start()
を使用します。
このようにすると、二つの処理が並列に行われます。
class T extends Thread {
final private static int max = 100;
final private StringBuilder sb;
public T(StringBuilder sb){
this.sb = sb;
}
@Override
public void run(){
for(int i=1; i< max ; i++){
try{
sleep(1);
}catch(InterruptedException e){}
sb.append(i+" ");
}
}
}
class Rei {
public static void main(String[] arg){
final StringBuilder sb = new StringBuilder();
final T t1 = new T(sb);
final T t2 = new T(sb);
t1.start();
t2.start();
try{
t1.join();
t2.join();
}catch(InterruptedException e){}
System.out.println(sb);
}
}
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 51 49 52 50 53 51 54 52 55 53 56 54 57 55 58 56 59 57 60 58 61 59 62 60 63 61 64 62 65 63 66 64 67 65 68 66 69 67 70 68 71 69 70 72 71 73 72 74 73 75 74 76 75 77 76 78 77 79 78 80 79 81 80 82 81 83 82 84 83 85 84 86 85 87 86 88 87 89 88 90 89 91 90 92 91 93 94 92 95 93 96 94 97 95 98 96 99 97 98 99
なお、静的関数 java.lang.Thread#sleep は指定されたミリ秒だけ休止します。 また、 join メソッドはそのスレッドが終了するまで待ちます。 いずれも java.lang.InterruptedException 例外が投げられる場合があります。 正常な処理では void interrupt() メソッドを実装して処理するなどの対処法 がありますが、上記のプログラムにおいては特になにもする必要がないので、 無反応になるようにしています。
なお、 Java は多重継承ができないため、この作り方では特定のサブクラスを スレッド化できません。 そのため、 Thread を継承する代わりに、 java.lang.Runnable インターフェ イスを実装する方法があります。
class A{
}
class B extends A implements Runnable {
public B(){
super();
}
@Override
public void run(){
System.out.println("This is B");
}
}
class C extends A implements Runnable {
public C(){
super();
}
@Override
public void run(){
System.out.println("This is C");
}
}
class Rei {
public static void main(String[] arg){
final Thread[] tarray = new Thread[2];
tarray[0] = new Thread(new B());
tarray[1] = new Thread(new C());
for(Thread t : tarray){
t.start();
}
}
}
なお、この方法では Thread のメンバ変数を実装時に使えません。 但し、 sleep などは、 Thread のスタティックな関数なので Thread.sleep() 使用できます。
次に、スレッドを途中で止めることを考えます。 java.lang.Thread クラスには stop メソッドがありますが、これはオブジェクトが壊れるなどの危険性があ るとされ、推奨されてません。 ここでは stop メソッドを使わないスレッドの止め方を考えます。
さて、このために考える例として、キーボードから文字列を入れると、その文 字列を 3 秒毎に 10 回表示するものを考えましょう。 これは、逐次入力を受け付け、入力が得られるごとに出力するスレッドを生成 します。 すると、スレッドは 30 秒間生きつづけます。
import java.io.*;
class Writer extends Thread {
final private String message;
public Writer(String message){
this.message=message;
}
@Override
public void run(){
for(int i=1;i<=10;i++){
System.out.println(i+": "+message);
try{
Thread.sleep(3000);
}catch(InterruptedException e){}
}
}
}
class Rei {
public static void main(String[] arg) throws IOException {
final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while((line=br.readLine())!=null){
Writer w = new Writer(line);
w.start();
}
}
}
Writer クラスのスレッドはコンストラクタで受けとったメッセージを単純に 10 回出力して停止します。 main 関数では BufferedReader を定義し、 標準入力から行を読み続けます。 読み込んだ行に対して Writer クラスのインスタンスを作り、 start メソッドを送るだけです。 そのため、実行中に標準入力から EOF が送られると main は終了しますが、スレッ ドはすべての出力を終えるまで停止しません。
次に、このプログラムの実行時に EOF を送ると、すべてのスレッドを止めるこ とを考えます。 このために interrupt を各スレッドで呼び出し、各スレッドで処理することを考えます。 このため、すべてのスレッドを管理し、動作しているスレッドのみに次々と interrupt を呼び出す方法も考えられます。 しかし、ここでは java.lang.ThreadGroup クラスを使うことを考えます。 Thread を作ると きに ThreadGroup オブジェクトをあらかじめ作っておき、 コンストラクタで ThreadGroup オブジェクトを指定することで、 ThreadGroup に関するコントロールを受け付けるようになります。 このようにしておき、 ThreadGroup オブジェクトにinterrupt メッセージを 送ると、関連付けたすべてのスレッドに interrput メッセージが届きます。
main 関数では EOF を受け取ったら処理を終え、 ThreadGroup tg に interrupt メッセージを送り、終了します。
Writer クラスでは、interrupt メソッドが実行されます。 ここでは、 interrupt メソッドとして、終了条件を表すフラグを設定した後、 super.interrupt() により Thread クラスに interrupt メッセージを送りま す。 これで、 InterruptedException が発生します。 すると、 sleep で待機していた run メソッドにおいて例外処理が行われ、メッ セージが出力されます。 そして、再度ループに入りますが、ループの終了条件で終了フラグの検査を行 い、終了します。
import java.io.*;
class Writer extends Thread {
final private String message;
private boolean active;
public Writer(ThreadGroup tg, String message){
super(tg,"");
active=true;
this.message=message;
}
@Override
public void interrupt(){
active=false;
super.interrupt();
}
@Override
public void run(){
for(int i=1; (i<=10)&&active ;i++){
System.out.println(i+": "+message);
try{
sleep(3000);
}catch(InterruptedException e){
System.out.println(message+" interrupted");
}
}
}
}
class Rei {
public static void main(String[] arg) throws IOException {
final BufferedReader br = new BufferedReader
(new InputStreamReader(System.in));
final ThreadGroup tg = new ThreadGroup("");
String line;
while((line=br.readLine())!=null){
Writer w = new Writer(tg,line);
w.start();
}
tg.interrupt();
}
}
文脈自由文法の素朴な文法解析において、可能な解釈を次々と試すために、 バックトラックという手法を使いました。 このバックトラックを用いる例を示します。
ここで、ゲーム木という概念を紹介します。 ここでとりあげるゲームとは、離散的な手を毎回選択するごとに 局面が変化して、最終的に勝ちと呼ばれる利得を得る 局面か、負けという損失を生じる局面のどちらかに到達するよう なものを言います。 手を選択するのをプレーヤと呼びます。 プレーヤが一人であるようなゲームを一人ゲーム と言い、プレーヤが二人で交互に手を選択するようなゲームを 二人ゲームと呼びます。
ゲームでは初期局面から始めて、次々に手を選ぶことで局面が変化します。 一般には、複数の手の組み合わせで同一の局面に合流することもあります。 しかし、ある局面から複数の次の局面に行くという対応関係の連続を、木構造 で表すことがあります。 この各頂点が局面で、手の選択で次の局面へ対応づいている根付き有向木 を ゲーム木 と呼びます。
通常、各局面で打てる手は 2 個以上あります。 すると、 N 手目までの局面の総数を考えると、ゲーム木のサイズは など、非常に大きなサイズになります。 したがって、ゲーム木の解析を行うのに、すべての局面を生成するわけには行 きません。 そこで、ゲーム木を深さ優先探索するのに、必要な局面として手の連続に対 応した局面のみを生成し、他の手の連続を解析する際は必要最低限度の局面を 捨てて途中まで戻り、そこから再度生成するようにします。
boolean 探索(局面){
if(局面が目的の形態) return true;
for(次の手){
次の局面を計算する
if(探索(次の局面)) return true;
}
return false;
}
一人ゲームの例として迷路探索を考えます。 迷路では分かれ道があるたび、あらゆる分岐を考え到達先を検索します。 そのため、迷路をゲームと考えると、最終的にゴールまでたどり着くための手 筋を一つ探すことが目標となります。
以下の迷路では座標 (1,1) の位置から文字 G が書かれたところまでの道を探 索します。 迷路は文字列の配列で表わし、壁は '+' 記号で、道は空白で表しています。
+++++++++++++++++++ + + + + + +++ + +++ +++++ + + + + + + + + + + + + + +++ + + + + + + + + + + + + +++++ + + +++ + + + + + + + + + + +++++++ + +++++ + + + G+ +++++++++++++++++++
実際には solve メソッドの呼び出しで迷路を探索します。 solve メソッドは実際は inspect(x,y) を呼び出すために下準備をし、呼び出 した後の結果を報告するだけのメソッドです。
inspect(x,y) は x,y の位置から探索を行うものです。 これは下記の処理を行います。
import java.util.*;
class Maze {
final private String[] maze;
public Maze(String[] maze){
this.maze = maze;
}
public String toString(){
final StringBuilder result= new StringBuilder();
for(String str : maze){
result.append(str+"\n");
}
return result.toString();
}
private StringBuilder[] work;
public Maze solve(){
work = new StringBuilder[maze.length];
for(int i=0; i<maze.length; i++){
work[i] = new StringBuilder(maze[i]);
}
inspect(1,1);
final String[] result = new String[work.length];
for(int i=0; i<work.length; i++){
result[i] = work[i].toString();
}
return new Maze(result);
}
private boolean inspect(int x, int y){
if(work[x].charAt(y)=='G'){
return true;
}
if(work[x].charAt(y)=='+'){
return false;
}
if(work[x].charAt(y)=='o'){
return false;
}
work[x].setCharAt(y,'o');
if(inspect(x-1,y) || inspect(x,y+1) || inspect(x+1,y) || inspect(x,y-1)){
return true;
}
work[x].setCharAt(y,' ');
return false;
}
}
class Main {
public static void main(String[] arg){
final Maze maze = new Maze(new String[]{
"+++++++++++++++++++",
"+ + + +",
"+ +++ + +++ +++++ +",
"+ + + + + + +",
"+ + + + + +++ + + +",
"+ + + + + + + +",
"+ +++++ + + +++ + +",
"+ + + + + +",
"+ + +++++++ + +++++",
"+ + + G+",
"+++++++++++++++++++"});
System.out.println(maze);
Maze result = maze.solve();
System.out.println(result);
}
}
チェスにおいて、クイーンとは縦と横と斜めにいくらでも移動で きる駒です。 チェスにおいて移動先にコマがあることを当たりといい、当たり になっている敵駒は取ることができます。
8 クイーン問題とは、 8個クイーンを用意して、それぞれが互いに当たりにな らないように配置する問題です。 これを一般化して n クイーン問題と言うのがあります。 これは、 n×n の盤面に n 個のクイーンを配置するものです。
なお、すでに述べたようにように、ゲーム木のサイズは巨大なので、この配置を解く 問題には膨大な計算時間がかかります。
二人ゲームではゲーム木をたどることにより、先手/後手必勝かどうかを確認 できる他、手の先読みにより、簡単なコンピュータプレイヤーを作ることがで きます。
まず、先手必勝かどうかの判定は次のような考え方でチェックします。
必勝手順とは、「先手がある手を選ぶと後手はどのような手を選んでも先手が 必勝手順を選べる」と帰納的に定義できます。 つまり、先手必勝という関数と、後手必敗という関数があったとき、 「先手が特定の手を選ぶとすべての後手の手で必敗」であれば先手必勝、 また、「後手のすべての手において、先手が先手必勝の手を選べる」時後手必 敗といえます。 これを関数にするとつぎのようになります。
boolean 先手必勝(局面){
先手が勝っている→ return true;
どの局面でも後手必敗→ return true;
そうでなければ return false;
}
boolean 後手必敗(局面){
後手が負けている→ return true;
少なくとも一つの局面で先手必勝→ return true;
そうでなければ return false;
}
なお、この「どの局面でも」は、一つでも「後手必敗」でないなら成立しませ んので、つぎのように書き換えられます。
boolean 先手必勝(局面){
先手が勝っている→ return true;
その局面において次に後手が可能な各局面において
{
if(!後手必敗(その局面)){
return false;
}
}
return true;
}
同様に「少なくとも一つ」はつぎのように書き換えられます。
boolean 後手必敗(局面){
後手が負けている→ return true;
その局面において次に先手が可能な各局面において
{
if(先手必勝(その局面)){
return true;
}
}
return false;
}
但し、通常は膨大な手数が必要なため、こんな単純な仕組みではメモリ効率や 時間効率の問題でうまく計算ができません。 例えば、オセロゲームでは最後に打った方が石の数が多くなるので後手が有利 であることが概念的に分かります。 そこで、 n × n マスのオセロゲームで後手必勝かどうかを考えます。 一つのマスで「石が無い」、「黒の石がある」、「白の石がある」の 3 通り がありますので、局面の数の最大値は高々 だけあります。 但し、石は必ず隣り合うように置かなければならないので、実際はもう少し少 なくなります。 また一つずつ盤面が埋まっていくので、ゲームが終了するまでの手数は 程度です。 しかし、一般のオセロは 8 × 8 ですが、これが後手必勝かどうかはまだ分かっ ていません。 但し、 6 × 6 のオセロについては後手必勝であることが示されています。
では、必勝手順が見つかっていないようなゲームにおいてコンピュータプレイ ヤーをどのように作るかを考えます。 これは非常に古い歴史がありますが、今回は単純に上記の必勝手順探索を利用 するものを考えます。 つまり、必勝手順が見つかればその手を打つ、一方、必勝手順が無ければ適当 に打つというようなプレイヤーを考えます。 但し、先手/後手必勝でないゲームは初期の段階などでは必ず必勝手の探索に 失敗します。 そのため、全局面の探索などをやっても無意味です。 そのため、通常は「何手先読みするか」を決めておきます。
private static int 先読み数 = 3;
手 コンピュータプレイヤー(局面){
for(次の手 : 可能な手){
次の手から次の局面を計算;
if(コンピュータが必勝(次の局面)){
return 次の手;
}
元の局面に戻す // バックトラック
}
return 適当に可能な手;
}
boolean コンピュータが必勝(局面, 先読み数){
if(先読み数 == 0){
return false;
}
if(その局面でコンピュータが勝っている){
return true;
}
その局面において次にプレーヤが可能な手において
{
手から次の局面を計算する
if(!プレーヤが必敗(次の局面, 先読み数-1)){
return false;
}
局面を戻す // バックトラック
}
return true;
}
boolean プレーヤが必敗(局面, 先読み数){
if(先読み数 == 0){
return false;
}
if(その局面でプレーヤが負けている){
return true;
}
その局面において次にコンピュータがが可能な各手において
{
手から次の局面を計算する
if(コンピュータが必勝(局面, 先読み数-1)){
return true;
}
局面を戻す // バックトラック
}
return false;
}
それでは、簡単な例として○×ゲームを対戦するコンピュータプレーヤを作っ てみましょう。
簡単のためにゲーム盤は単なる 9 文字の文字列とします。 書き換えを可能にするために java.lang.StringBuilder 型をコンポジション する型とします。 最初は空白 9 個で初期化します。 また、盤をコピーするため、コピーコンストラクタも用意します。 一方、手を置くために setCharAt メソッドを put メソッドとして、また探索 を行うため indexOf メソッドはそのまま実装します。 あと、 toString では盤の形で表示できるようにします。 最後に、 win メソッドで勝ちパターンかどうかを判定します。
import java.util.Iterator;
public class Ban implements Iterable<Integer>, Cloneable{
final private StringBuilder str;
public Ban(){
str = new StringBuilder(" ");
}
public Ban(Ban ban){ // コピーコンストラクタ
this.str = new StringBuilder(ban.str.toString());
}
public void put(char player, int te){
str.setCharAt(te,player);
}
public int indexOf(String str){
return str.indexOf(str);
}
@Override
public String toString(){
return "---\n"
+str.substring(0,3)+"\n"
+str.substring(3,6)+"\n"
+str.substring(6,9)+"\n"
+"---";
}
private static final int[][] winPattern =
{{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
public boolean win(char player){
for(int[] retsu : winPattern){
boolean result=true;
for(int i : retsu){
if(player != str.charAt(i)){
result = false;
break;
}
}
if(result){
return true;
}
}
return false;
}
@Override
public Iterator<Integer> iterator(){
return new Tsuginote(this.str.substring(0,9));
}
}
Ban 型で次に可能な手を容易にアクセスできるようにするため、 Ban 型を Iterable にし、イテレータを実装します。
import java.util.Iterator;
class Tsuginote implements Iterator<Integer>{
final private String ban;
private int index;
Tsuginote(String ban){
this.ban = ban;
index = ban.indexOf(" ");
}
@Override
public boolean hasNext(){
return index!=-1;
}
@Override
public Integer next(){
int result = index;
index = ban.indexOf(" ",index+1);
return result;
}
@Override
public void remove(){
}
}
コンピュータの思考ルーチンを作ります。 3 手先読みすることにします。 引き分けがありえます。 最終局面で相手側が引き分けに持ち込んだら true, こちらが引き分けにしか できなければ false を返すことにします。 あとのプログラムは上記と同様です。
public class Constant {
public static final int maxscore = 1;
public static char[] players = {'o','x'};
public static int depth = 3;
}
public interface Comp {
int te(Ban ban);
}
public class Comp1 implements Comp {
private final static int depth = 3;
public Comp1(){}
private boolean compHissho(Ban ban, int depth){
if(depth==0){
return false;
}
if(ban.win('x')){
return true;
}
if(ban.indexOf(" ")==-1){
return true; //Draw
}
final Ban tsugi = new Ban(ban);
for(int te: tsugi){
tsugi.put('o',te);
if(!playMake(tsugi,depth-1)){
return false;
}
tsugi.put(' ',te);
}
return true;
}
private boolean playMake(Ban ban, int depth){
if(depth==0){
return false;
}
if(ban.win('o')){
return false;
}
if(ban.indexOf(" ")==-1){
return false; //Draw
}
final Ban tsugi = new Ban(ban);
for(int te: tsugi){
tsugi.put('x',te);
if(compHissho(tsugi,depth-1)){
return true;
}
tsugi.put(' ',te);
}
return true;
}
public int te(Ban ban){
int value = -1;
final Ban tsugi = new Ban(ban);
for(int i : ban){
value = i;
tsugi.put('x',i);
if(compHissho(tsugi,depth)){
return i;
}
tsugi.put(' ',i);
}
return value;
}
}
主プログラムでは、盤を作り、 java.util.Scanner でプレーヤの手を読むよ うに準備します。 そして、プレーヤとコンピュータが交互に手を置くようにしています。 なお、エラーチェックなどを行っていませんので、このままでは×の上に○を 置けてしまいます。
import java.util.Scanner;
public class Rei {
public static void main(String[] arg){
Ban ban = new Ban();
boolean turn=false;
Comp comp = new Comp1();
Scanner sc = new Scanner(System.in);
try{
for(int i=0;i<9; i++){
if(turn){
ban.put('x',comp.te(ban));
}else{
ban.put('o',sc.nextInt());
}
System.out.println(ban);
if(ban.win('o')){
System.out.println("Player Wins.");
return;
}
if(ban.win('x')){
System.out.println("Computer Wins.");
return;
}
turn = ! turn;
}
System.out.println("Draw");
}finally{
sc.close();
}
}
○×ゲームには引き分けがあります。しかし、一方が勝てばもう一方は必ず 負けるため、勝ちの利得と負けの損失の大きさが同じで、引き分けの利得が ゼロなら、二人のプレイヤーの利得の和は常にゼロになります。 これをゼロ和ゲームと呼びます。 さらに、○×ゲームでは、盤の情報が常に全て両方のプレイヤーに見えるた め、完全情報ゲームと呼びます。 つまり、2つ合わせて、完全情報ゼロ和ゲームと呼びます。
前章のコンピュータプレイヤーの場合、引き分けを処理できず、勝ちと引き 分けが同価値に処理されてしまいます。 そのため、勝利できそうな場合でも確実に勝つ手を指しません。 例えば、0,(1),3,(6),2 とプレイヤーが悪手を指した場合（カッコ内は Comp1 の手）、(7)をコンピュータプレイヤーが差せば両あた りになるため勝利しますが、必ず勝てるのと引き分けが等価値になってしま うため、Comp1 では (4) を指してしまい、引き分けになってしまいます。
そこで、引き分けも取り扱えるよう、Ban に評価値 score を計算するよう にします。 まず、引き分けを 0, 勝ちの盤面の評価値を Constant.maxscore とします。 負けの盤面の評価値は -Constant.maxscore、勝敗不明は 0 となります。
次の手を決める条件として、全ての自分の手を試します。 そして、相手の立場でのscore が最小、つまり完全ゼロ和では自分の評価値を最大にする手を選びます。 なお、必勝手が複数ある場合、短い手順を優先します。
そこで、score の計算法として、手数が増えると目減り、つまり、正負の値 とも 0 に近づくような計算法を考えます。 そこで、既に示した自明な値以外は、相手の指す手の評価値の最大値を -2 で割ったものとします。 つまり、式で書くと次のようになります。
このようにして、評価値を計算するBanクラスを示します。
package marubatsu;
import java.util.Iterator;
public class Ban implements Iterable<Integer>, Cloneable{
final private StringBuilder str;
public Ban(){
str = new StringBuilder(" ");
}
public Ban(Ban ban){
this.str = new StringBuilder(ban.str.toString());
}
public Ban(int[] te) {
str = new StringBuilder(" ");
char p = Constant.players[0];
char e = Constant.players[1];
for(int t : te) {
str.setCharAt(t, p);
char temp=p;
p=e;
e=temp;
}
}
public void put(char player, int te){
str.setCharAt(te,player);
}
public int indexOf(String str){
return str.indexOf(str);
}
public double score(char player, char enemy, int k) {
if(win(player)) {
return 1;
}
if(win(enemy)) {
return -1;
}
if(indexOf(" ")==-1){
return 0; //Draw
}
if(k==0) return 0;
Ban tsugi = new Ban(this);
double s = Constant.maxscore;
for(int te: tsugi){
tsugi.put(enemy,te);
double s2 = -tsugi.score(enemy, player, k-1);
if(s2 < s) {
s = s2;
}
tsugi.put(' ',te);
}
return s/2;
}
@Override
public String toString(){
return "---\n"
+str.substring(0,3)+"\n"
+str.substring(3,6)+"\n"
+str.substring(6,9)+"\n"
+"---";
}
private static final int[][] winPattern =
{{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
public boolean win(char player){
for(int[] retsu : winPattern){
boolean result=true;
for(int i : retsu){
if(player != str.charAt(i)){
result = false;
break;
}
}
if(result){
return true;
}
}
return false;
}
@Override
public Iterator<Integer> iterator(){
return new Tsuginote(this.str.substring(0,9));
}
}
さらに、これに適応させたコンピュータプレイヤー Comp2 を示します。
package marubatsu;
public class Comp2 implements Comp {
@Override
public int te(Ban ban) {
int arg=-1;
int max=-2;
Ban tsugi = new Ban(ban);
for(int i : ban){
tsugi.put(Constant.players[1],i);
double value = tsugi.score(Constant.players[1],
Constant.players[0], Constant.depth);
if(value > max) {
arg = i;
max = value;
}
tsugi.put(' ',i);
}
return arg;
}
}