このドキュメントは 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<String,Integer>();
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 の基本的な作り方は次の通りです。
class T extends Thread {
final private static int max = 100;
final private StringBuilder sb;
public T(StringBuilder sb){
this.sb = sb;
}
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);
}
}
なお、静的関数 sleep は指定されたミリ秒だけ休止します。 また、 join メソッドはそのスレッドが終了するまで待ちます。 いずれも java.lang.InterruptedException 例外が投げられる場合があります。 正常な処理では void interrupt() メソッドを実装して処理するなどの対処法 がありますが、上記のプログラムにおいては特になにもする必要がないので、 無反応になるようにしています。
なお、 Java は多重継承ができないため、この作り方では特定のサブクラスを スレッド化できません。 そのため、 Thread を継承する代わりに、 java.lang.Runnable インターフェ イスを実装する方法があります。
class A{
}
class B extends A implements Runnable {
public B(){
super();
}
public void run(){
System.out.println("This is B");
}
}
class C extends A implements Runnable {
public C(){
super();
}
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 のスタティックな関数なので使用できます。
次に、スレッドを途中で止めることを考えます。 java.lang.Thread クラスには stop メソッドがありますが、これはオブジェクトが壊れるなどの危険性があ るとされ、推奨されてません。 ここでは stop メソッドを使わないスレッドの止め方を考えます。
さて、このために考える例として、キーボードから文字列を入れると、その文 字列を 3 秒毎に 10 回表示するものを考えましょう。 これは、逐次入力を受け付け、入力が得られるごとに出力するスレッドを生成 します。 すると、最初のメッセージの後、 9 回表示することになるので、スレッドは 27 秒間生きつづけます。
import java.io.*;
class Writer extends Thread {
final private String message;
public Writer(String message){
this.message=message;
}
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;
}
public void interrupt(){
active=false;
super.interrupt();
}
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 個以上あり、手は局面を表現するビット数と関連するので、ゲー ム木のサイズは など、非常に大きなサイズになります。 ゲーム木の解析を行うのに、すべての局面を生成するわけには行きません。 そこで、ゲーム木を深さ優先探索するのに、必要な局面として手の連続に対 応した局面のみを生成し、他の手の連続を解析する際は必要最低限度の局面を 捨てて途中まで戻り、そこから再度生成するようにします。
一人ゲームの例として迷路探索を考えます。 迷路では分かれ道があるたび、あらゆる分岐を考え到達先を検索します。 そのため、迷路を
以下の迷路では座標 (1,1) の位置から文字 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.*;
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;
}
public Iterator<Integer> iterator(){
return new Tsuginote(this.str.substring(0,9));
}
}
Ban 型で次に可能な手を容易にアクセスできるようにするため、 Ban 型を Iterable にし、イテレータを実装します。
import java.util.*;
class Tsuginote implements Iterator<Integer>{
final private String ban;
private int index;
Tsuginote(String ban){
this.ban = ban;
index = ban.indexOf(" ");
}
public boolean hasNext(){
return index!=-1;
}
public Integer next(){
int result = index;
index = ban.indexOf(" ",index+1);
return result;
}
public void remove(){
}
}
コンピュータの思考ルーチンを作ります。 3 手先読みすることにします。 引き分けがありうるので、それは必勝でも必敗でもないということで双方 false を返すことにします。 あとのプログラムは上記と同様です。
class Comp {
private final static int depth = 3;
public Comp(){}
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 でプレーヤの手を読むよ うに準備します。 そして、プレーヤとコンピュータが交互に手を置くようにしています。 なお、エラーチェックなどを行っていませんので、このままでは×の上に○を 置けてしまいます。
class Rei {
public static void main(String[] arg){
final Ban ban = new Ban();
boolean turn=false;
final Comp comp = new Comp();
final Scanner sc = new Scanner(System.in);
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 Win.");
return;
}
if(ban.win('x')){
System.out.println("Computer Win.");
return;
}
turn = ! turn;
}
System.out.println("Draw");
}
}