Search on the blog

2013年7月28日日曜日

Curly Bracket Initialization in C++

curly bracketをつかった配列の初期化をいまいち把握していなかったので、調べてみた。

int xs[10] = {0};
これはxsの要素がすべて0に初期化される。

int xs[10] = {};
これでもxsの要素がすべて0に初期化されるらしい。最近までこの書き方は知らなかった。。

int xs[10] = {123};
これはxsの要素がすべて123になると見せかけて、
  • xs[0] = 123
  • xs[i] = 0,  i = 1, 2, ..., 9.
となる。ということは{}の中で指定されなかった要素は0になるということかと予想してみる。

調べてみる
  • curly bracketの要素数を配列のサイズより大きくすることはできない。 
  • curly bracketの要素数を配列のサイズより小さくすることはできる。その場合、値が指定されなかった残りの要素はデフォルト値で初期化される。
ということらしい。[1]

参考URL
[1] Curly Bracket Initialization in C++ and Java

2013年7月27日土曜日

Swingで繰り返しRepaintするときはTimerを使う

Swingで定期的に画面を再描画するような処理を書いていてはまったので、メモを残しておきます。
結論から言うと、javax.swing.Timerを使うとやりたいことができました。


ソースコード

ダメな例
最初処理を書いたときは、
  1. Thread.sleep()でスレッドを一時停止する
  2. repaintを呼んで再描画する
をSTOPボタンが押されるまで繰り返すという書き方(参考URL[2]にあるような書き方)をしていたのですが、これだと思った動作ができませんでした。

調べてみると、

Thread.sleep()は、実行中のスレッドをスリープさせる。このときスリープするスレッドは保持しているロックを開放しない[1]。

ということでした。

その結果、
  1. repaintリクエストは実行されることなくキューに溜まっていく。
  2. STOPボタン押下時にはじめてキューにたまったrepaintが実行可能となる。
  3. 実行されてないrepaintリクエストが複数個ある場合は、一つにまとめられて最後のrepaintメソッドだけが実行される。(もしくは設定によってはキューに溜まったrepaintがすべて間隔をあけることなく一瞬で実行される。)
  4. 思った動作にはならない。
ということが起きていました。

参考URL
[1] Difference between wait() and sleep()
[2] Java - repaint component every second?
[3] Combining repaint() with Thread.Sleep()

最近の出来事

最近仕事が忙しい。だいたい毎日終電帰り。
そして楽しみと言ったら、帰りにコンビニによってビールとつまみを買って家で一人晩酌するくらい。やばいわー。やばい。やばい。

でもwebシステムのことだったり、フレームワークについてだったり、大規模システムの開発だったり、一人だとなかなか学べないことを学べているので、いい経験かもしれない。
アルゴリズムとか数学とか一人で出来ることは趣味でやって、一人だとできないことを仕事でやるといいのかもしれない。

あと最近スターウォーズをレンタルして見ている。まずprequel trilogyを見て、original trilogyを見てるけど、多分prequelの方がおもしろい。そして、ナタリーポートマンがかわいい。レオンのときの幼女ナタリーもかわいかったけど、大人の女性に成長したナタリーはとびっきりの上玉だ。

あと家に帰ってから、頭を使うことをする気力がないので、バスケットボールを指の上で回す練習をしている。50秒くらいは回せるようになった。多分の何の役にも立たないスキル。

2013年7月23日火曜日

what doesn't kill you makes you stronger

Kelly Clarksonの2012年のヒット曲の一節。

What doesn't kill you makes you stronger.

最初聞いたとき、え、どういうこと?

What kills you makes you stronger.

の間違いじゃないの?と思った。

死ぬほど辛い経験は人を強くするってことでしょ?

What could kill you makes you stronger.

じゃないの?

なぜdoesn'tがつくのか。
doesn'tがつくとそんなに辛くないことみたいに聞こえる。

辛いけど、死ぬほどの辛さじゃなければ、それは人を強くする。

いや、まあそうだけど。この辺は英語と日本語の感覚のずれなのだろうか。


2013年7月21日日曜日

Connect Fourソルバーを作る(6)

前回までで簡単なAIが出来たので、GUIで遊べるゲームを作り始めました。

が、なんとなくクラス設計をミスった感じがしています。
とりあえず今まで作っていたものを
  • Connect4_Core
  • Connect4_Batch
  • Connect4_CUI
  • Connect4_GUI
のように分けて、Connect4_Coreにゲームの状態を判定したり、プレイヤーの戦略ロジックとかを寄せてみました。で、Coreの機能を利用して各UIを実装しました。Batch/CUIはうまく書けましたが、GUIがうまく書けない(うまくCoreと連携できない)。

前回JUnitでテストをしたときに、リフレクションを使ってprivateのメソッドをpublicのメソッドに変更してテストを行ったのですが、
「何でテストフレームワークにアクセス権限を変えるような機能がないんだろう。よく使いそうなのに。」
と不思議に思っていろいろと調べていたら、
「privateなメソッドをpublicにしないと単体テストができないっていうのは、クラス設計がいけていない証拠だ。クラス設計やりなおせ。」
みたいなことを書いているサイトを見つけて今思い返すとまさにそのとおりだなーという感じです。

半日くらいでさくっと書けると期待してましたが、道のりは思っていたより長そうです。とりあえずマウスクリックしたら石が下から埋まっていくとこまでは出来たので、画面イメージをはっておきます。


TCPとは何か?

分かってるようで分かっていなかったので、概要レベルでまとめてみた。

wikipediaより
  • Internet protocol suiteの中核をなすプロトコル(決まりごと)の一つ。
  • TCPはとても重要なので、Internet protocol suite全体を指してTCP/IPと呼ぶことがある。
Internet protocol suiteっていうのは、HTTPとかFTPとかSSHとかTCPとかUDPとか・・・インターネットのために使われるコミュニケーションプロトコルの集まりのこと。


searchnetworkingより
  • インターネット上のコンピュータ間のデータ転送を行うための決まりごと。
  • TCPは効率的なネットワーク上のルーティングのために分割された個々のデータ(パケット)の管理を行う。
  • 例えばWEBサーバーのTCPレイヤーは、HTMLファイルを複数のパケットに分割し、パケットの数を数え、個々のパケットをIPレイヤーに渡す。それぞれのパケットの行き先は同じIPアドレスだったとしても、それぞれのパケットは異なるルーティングをされるかもしれない。
  • クライアントサイドでは、TCPはパケットが送られてくるのを待って、パケットを一つの元のファイルに組み立て直す。
要するに、TCPの役割はデータをパケットに分割すること + 受け取り側で分割されたパケットを組み立てること
なぜそんなことが必要かというと、効率的にデータを転送するため。(パケットを使わずに一気に送ろうとすると、何らかの理由で相手に届かなかったとき最初からすべて送り直さないといけないので非効率。パケットを使うと、届かなかったパケットがあった場合そのパケットだけを再送すればいい。)


Reference
[1] https://en.wikipedia.org/wiki/Transmission_Control_Protocol
[2] http://searchnetworking.techtarget.com/definition/TCP

2013年7月16日火曜日

Connect Fourソルバーを作る(5)

 Connect FourのAIの進捗を書きます。
 えーと、まずα-β pruningを実装してみました。pruningなしのものと比較して予想通りの動きをしてくれたので、正しく実装できていると思います。
どの辺が追加されたか分かり辛いので、pruning入れる前のものとのdiff。
--- SmartMinMaxPlayer.java  2013-07-15 22:52:02.976994462 +0900
+++ AlphaBetaPlayer.java  2013-07-16 01:10:53.800748315 +0900
@@ -2,16 +2,16 @@
 
 import java.util.Random;
 
-public class SmartMinMaxPlayer extends Player {
+public class AlphaBetaPlayer extends Player {
   
-  private final int DEPTH = 8;
+  private final int DEPTH = 10;
   
   private char[][] board;
     
   @Override
   public int getNextHand(char[][] board) {
     this.board = board;
-    int[] res = dfs(0);
+    int[] res = dfs(0, -Integer.MAX_VALUE, Integer.MAX_VALUE);
     System.out.println("評価値: " + res[0]);
     return res[1];
   }
@@ -20,7 +20,7 @@
     return (c == FIRST_STONE) ? SECOND_STONE : FIRST_STONE;
   }
   
-  private int[] dfs(int turn) {
+  private int[] dfs(int turn, int alpha, int beta) {
     char cur = (turn % 2 == 0) ? getStone() : opponent(getStone());
         
     // 相手の前の手で自分の負けが確定
@@ -56,8 +56,9 @@
       if (i == -1)
         continue;
       
+      alpha = Math.max(alpha, res);
       board[i][j] = cur;
-      int[] tmp = dfs(turn+1);
+      int[] tmp = dfs(turn+1, -beta, -alpha);
       if (-tmp[0] > res || move == -1) {
         res = -tmp[0];
         move = j;
@@ -66,6 +67,9 @@
       board[i][j] = EMPTY;
       if (res == Integer.MAX_VALUE)
         break;
+      if (res >= beta) {
+        return new int[] {beta, -1};
+      }
     }
 
     return new int[] {res, move};
@@ -196,7 +200,7 @@
   
   @Override
   public String getName() {
-    return "Smart Min Max Player";
+    return "Alpha Beta Player";
   }
 
 }

α-βとは関係ないですが、前回まで作ったプログラムにバグがあったので直しました。

Analysis
 まず考慮時間について。枝刈りを入れることで体感だと10倍以上考慮時間が短くなった。深さ20くらいいけるかなと予想していたけど、深さ12の時点で10秒以上かかってしまった。(※このプロジェクトでは10秒以内に指し手を決定するAIを目指している。)
 AlphaBetaPlayer(探索深さ10)を前回まで最強キャラだったSmartMinMaxPlayer(探索深さ8)と戦わせてみた。10戦1勝9分。
ゲームの流れを見ていると、お互いが負けないような手を指しあって引き分けパターンに毎回落ち着いている感じだった。あまり見ていて面白いゲームではなかった。
 これだけだと強くなったかどうか分からないので、MinMaxPlayerと戦わせてみた。100戦91勝7敗。こちらも大きな進歩は見られなかった。うーん、今回の改良はスピードアップができたというだけか。読みの深さが2増える程度だとそんなに結果に影響しないということか。というより評価関数が正確なものじゃないことが問題なのか。

Tasks Ahead
  • 評価関数をもう少し練る
  • 終盤に近づくに連れて探索の深さを深くしてみる
  • GUIのVisualizerを作って人間様と戦わせてみる

Maison Ikkoku(English dub) Completed!

 英語吹替版「めぞん一刻」全エピソード見終わりました。今年の目標の一つだったので達成感に満ち溢れています。

話を既に知っている&英語版コミックを読んだことがあるので、話の内容はほぼ完璧に理解できました。一言一句完全に聞き取れるかというレベルだと、キャラクターによるという状態です。

  • 五代、響子さん、三鷹、九条、こずえ → ほぼ100%聞き取れる
  • 五代のおばあちゃん、一ノ瀬さん → 7, 80%くらい聞き取れる
  • 朱美、坂本 → 5,60%くらい聞き取れる
  • 四谷 → 30%くらいしか分からない
分析してみると、きちんとしたキャラクターはきちんとした言葉使いをするのでほぼ完全に聞き取れる。多少ラフな言葉使いやスラング程度なら理解できる。速く喋る人、ぼそぼそっと喋る人の英語はまだ完全には聞き取れない。前後の会話と脈絡のないことを言われるとほぼ分からない。シェークスピアの引用とかされても分からない。

と言ったところでしょうか。

次はアメリカのsitcomに挑戦してみようかな。

2013年7月11日木曜日

最近覚えた英語の表現(1)

See you later, alligator.
これは昔聞いたことがある。実はこれに対する正しい(?)受け答えがある。
In a while, crocodile.

相手の英語力を図るために使ってみるといいかも。

blah-blah-blah
これはフィリピン人と英会話をしていたときに、よく聞いた表現。
英語とは思っていなかったが、英語だったらしい。
意味は、うんぬんかんぬん。かくかくしかじか。みたいな感じ。
長くなりそうな重要でない話を省略するときに使う。

go ga-ga
え、Lady Gaga?
Oh, my Lady Gaga.みたいに何かにかけた表現かなと思ったら、
go ga-ga over~で~に夢中になる。という意味らしい。

shm-
誰かが何かを言ったときに、「いやいやそんなことないやろー」と応じるときに使う言葉。
-の部分で誰が言った言葉を繰り返す。

She' so cute! (彼女、まじかわいいんすけど。)
Cute, shmute.(どこがやねん。)

2013年7月5日金曜日

Connect Fourソルバーを作る(4)

簡単に書けそうだったので、評価関数を真面目に考えたバージョンをさくっと作ってみました。
評価関数は以下のようにしました。
  • 自分の勝ち  +oo
  • 相手の勝ち  -oo
  • その他の場合は、f(自分) - f(相手)
fはすべての4つの隣接するセルについてループを回し
  • 自分が4つ埋める可能性がない場合(少なくとも1つのセルが相手にとられている場合)は +0点。
  • 自分が4つ埋める可能性があり、すでに2つ埋めている場合 +4点。
  • 自分が4つ埋める可能性があり、すでに3つ埋めている場合 +9点。
のように計算。

ソースコード
SmartMinMaxPlayer.java

実験
今まで作ったプレイヤーの中で最強だった、MinMaxPlayerと対戦させました。
結果は、96勝4敗。これほど強くなるとは思いませんでした。

MinMaxPlayerは探索を打ちきるときの局面で勝敗がついてない場合は「勝敗がつかない」という情報を与えるだけなのに対して、SmartMinMaxPlayerはどれだけ有利な局面なのかまで情報を渡してくれるので情報量がまったく違います。そう考えるとこのくらい強くなるのは妥当なのかもしれません。

今後の目標
遅い部分の処理を高速化する。
α-β探索を取り入れる。

そこまで出来たら、GUIを作ってJava Web Startで公開。
その後はモンテカルロ木を実装してみる。

Connect Fourソルバーを作る(3)

単純なMinMax戦法をとるプレイヤーを作りました。

評価関数は、
  • 自分の勝ちなら +1
  • 引き分けなら 0
  • 自分の負けなら -1
です。枝刈りは自分の勝ちが確定した時点で探索を止めるという単純なものを採用しました。8手先まで読むことができます。

8手読んでどう頑張っても負けると分かったら、潔く「負けました」と言ってくれます。



プログラムソース
ちゃんと最適化とかしてませんが、上の要件は満たしているはずです。(追記: バグあるかも。)

ver 0.1.0 added MinMax Player


どれくらい強いか?
[対AI]
今まで作ったAIと対戦させました。
GreadyPlayerと戦わせた結果は、92勝8負。前回までの最強プレイヤーを軽くねじ伏せました。

[対人間]
対人間と言っても僕がプレーしてみただけです。
ミスしたら確実についてくるのと、終盤の読みがするどいです。なかなか強いです。3回やって1回勝てるくらいです。

次の目標
評価関数を真面目に考える。

Connect Fourソルバーを作る(2)

Connect Four既に解かれてる(お互いが最善手を指した場合の結果が分かっている)らしいです。
  • 先手の第一手が真ん中なら、先手必勝
  • 先手の第一手が真ん中の隣なら、引き分け
  • 先手の第一手が上記以外なら、後手必勝
なんと。

でも、数学的にもプログラミング的にも面白いテーマなのでもうちょっと続けようと思います。

今日はテストコードを追加しました。

GameクラスのwinOfというメソッドをテストしようとしましたが、winOfはprivateなメソッド。
privateなメソッドをテストしたいとき、どうするか?
JUnitかdjUnitに便利な機能があるかなと思いましたが見つけられなかったので、自前でリフレクションを使ってテストすることにしました。

こんな感じです。

package com.kenjih.connectfour.test.games;

import static org.junit.Assert.*;

import java.lang.reflect.Field;
import java.lang.reflect.Method;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import com.kenjih.connectfour.main.games.Game;
import com.kenjih.connectfour.main.players.RandomPlayer;

public class TestGame {

 Game game;

 @Before
 public void setUp() throws Exception {
  game = new Game(new RandomPlayer(), new RandomPlayer());
 }

 @After
 public void tearDown() throws Exception {
 }
 
 private void setBoard(char[][] board) throws Exception {
  Field field = game.getClass().getDeclaredField("board");
  field.setAccessible(true);
  field.set(game, board);  
 }
 
 private boolean winOf(char stone) throws Exception {
  Method method = game.getClass().getDeclaredMethod("winOf", char.class);
  method.setAccessible(true);
  return (Boolean) method.invoke(game, stone);
 }

 @Test
 public void testWinOf_1() throws Exception {
  
  char[][] board = { 
   ".......".toCharArray(),
   ".......".toCharArray(),
   "..XOOO.".toCharArray(),
   "..XXOO.".toCharArray(),
   "..X.X..".toCharArray(), 
   ".......".toCharArray()
  };
  
  setBoard(board);
  assertEquals(false, winOf('O'));
  assertEquals(false, winOf('X'));
 }

 @Test
 public void testWinOf_2() throws Exception {
  
  char[][] board = { 
   ".......".toCharArray(),
   ".......".toCharArray(),
   "..O....".toCharArray(),
   "..O....".toCharArray(),
   "..O....".toCharArray(), 
   "..O....".toCharArray()
  };
  
  setBoard(board);
  assertEquals(true, winOf('O'));
  assertEquals(false, winOf('X'));
 }
        
        // other test cases follow.
}

2013年7月3日水曜日

Connect Fourソルバーを作る(1)



Connect Fourをプレーするプログラムを書いてみました。
暇な時更新していきたいと思います。


次は、DFSとかα-β探索とかを書く予定。

あとちゃんと読んでないけど、このサイトが面白そう。

その場かぎりのGready戦略を取るプレイヤーを対戦相手に学習(どの手を打つと勝てるか、どの手を打つと負けるか記憶させる)させて、minimax戦略を取るプレイヤーと戦わせたら98%勝利することが出来たらしい。

深さがどの程度のminimaxか書いてないのですごいのかどうかはぱっと見では分からないけど、ソースがあるので今度読んで見ようと思う。