2015年10月25日日曜日

ウラムの螺旋を描く[Processing]

 素数っていいですよね。孤高な感じがして。でもなんか覚えにくいイメージがありますね。私の場合は,数字を覚えるときに,数字が小さいとその数字を因数分解して覚えます。そうすると「ああ,2^2+3^3=108なのか。2,2,3,3で覚えやすいな」みたいなことがあるのですが,素数はそういった覚え方ができないのがまた逆に良いですね。

1.ウラムの螺旋とは


 ウラムの螺旋はウラムさんが見つけたものです。とりあえずこんな感じの図形のこと。なんとなくn斜めに線が浮かび上がっているのがわかるでしょうか。
 この図形は素数に当たる数字の場所を緑色に塗ったものです。素数というと,なんだか法則性があるようでないような感じがしますが,このように図にしてみると法則性がありそうだということがわかります。
 この図形の書き方は,数字をある規則によって並べていき,素数を塗ると幾つかの線が現れるというものです。以下にその数字の並べ方を書いておきます。自分の手で一回書いてみると面白いですよ。
素数を青色に塗ってみました。なんとなく線が浮かび上がってくるのがわかるでしょうか。なぜこのような性質があるのかに対して,証明は確かされていなかったはず。しかしこのウラムの螺旋から,素数を多く生産する数式がたくさん発見された。

 ちなみに二次式で素数を大量生産できる式といえばこんな式がある。
n=0なら41(素数),n=1なら43(素数),n=2なら47(素数),n=3なら53(素数)……と,n=39までは全部素数になる。この数式であらわされる素数をオイラー素数と言ったりする。昔この式であらわされる自然数は全部素数になるよ,というデマに騙されたことがある。n=41を入れれば合成数になることは明らかなのにね。

2.ソースコード


 余談はさておき,プログラムはこんな感じ。素数はエラトステネスの篩で計算した。色を塗る場所の計算がちょっと雑で,上の表とは違っているかもしれない。まぁでも見るだけなら問題ない。
 ホントよくこんなこと考えたよね。まず数字を並べたりしないし,素数を縫ったりもしないからなぁ……。

boolean[] Board;

void setup() {
  /* 適当な大きさでウィンドウを開く */
  size(512, 512);

  /* indexが素数ならfalseの配列を作る */
  Board = new boolean[width*height+1];
  Board[0] = Board[1] = true;

  /* 素数かどうかをあらかじめエラトステネスの篩で計算 */
  for (int i = 2; i < sqrt(Board.length) ; i++ ) {
    /* iが素数ならば */
    if ( Board[i] == false ) {
      /* その倍数は合成数 */
      for (int j = 2 * i; j < Board.length; j += i ) {
        Board[j] = true;
      }
    }
  }
}

void draw() {
  /* 背景を黒にする */
  background(0);

  /* 描画する色を緑にする */
  stroke(0, 255, 0);
  fill(0, 255, 0);
  
  /* 原点を中心に持ってくる */
  translate(width/2, height/2);

  /* 描画する座標 */
  int x = 0;
  int y = 0;
  /* 座標をどう動かすかを計算するための変数 */
  int dx = 1;
  int dy = 0;
  int n = 1;
  
  for (int i = 1; i < width * height + 1; i++ ) {
    /* 素数ならば描く */
    if ( Board[i] == false )
      rect(x, y, 1, 1);  

    /* iに応じて次の描画場所を決める */
    if ( n * n + 1 == i ) {
      dy = (n % 2)*2-1;
      dx = 0;
      n++;
    } else if ( n * n - n + 1 == i) {
      dx = (n % 2)*2-1;
      dy = 0;
    }
    x += dx;
    y += dy;
  }
}

遺伝的アルゴリズムでオセロのAIを学習させてみた[C#]

 最近何かとネットに上がっている遺伝的アルゴリズムを自分でも実装してみた。

 本当は先々週ぐらいにもう完成してたけれどネットが繋がらなくなったりパソコンが起動しなくなったりと,結構面倒なことが起きたので遅れてしまった。まるで何か大きな力が私を止めようとしていたのか……?何事もなければいいのだが。

1.動画

 自分が人工知能や人工生命みたいなワードに興味を持ったきっかけの一つが,むにむに教授さんがやってた遺伝的アルゴリズムシリーズ。今回はそれに便乗してオセロのAIを作ってみて,その評価関数を最適化するのに遺伝的アルゴリズムを使ってみた。そんでもって,せっかくなので動画にしてみた。この動画に刺激されてこういう分野に興味を持ってくれる人が出てくると嬉しい。

 動画編集は初めてで苦戦したし自分でもうまくできていないのはわかっているが,まぁ一度やってみたかったからいいんだ。楽しかったし。

2.解説

 まぁ詳しい内容は割りと動画内でしたつもりだが,もう少しプログラムの詳細をここでは書く。あ,一応述べておくけれど動画内では学習とかなんとか言ってたけどただの最適化だからね。学習って聞くと誤解する人がいそうだから本当は避けるべきだったのかもしれない。

 評価に際して対戦させたわけだが,実際はバックグラウンドで行った。あとAIはすべて1手先しか読んでいない。ミニマックス法で実装したら割りと学習には時間がかかりそうだったしめんどくさいし……。

 交配は64の個体のうち,勝った回数が最も多かった上位10個体から行った。その上位10個体の遺伝子はそのまま引き継ぐ。

 今回は150世代までやったわけだけれども,実際には条件をちょっと変えて行ってみたのだが,大体同じ感じになった。だが対戦相手が変わるため,遺伝子が収束しないというのがちょっと問題かな。あれ?なんか問題多いな。まぁいいか。

3.学習結果

 一応どうなるのかを予想してみた。イメージではこんな感じになると思っていた。

 カドの点数は絶対高いだろうというのは間違いないだろうと思っていた。カドの周りの点数が下がり,自分がそこに置かないようにするというのもまぁ想定の範囲内だった。だが端(一番外側)の部分は,ほとんど高くなると思っていたが実際は違った。

 端(一番外側)の部分でも,中央寄りの部分は点数が下がっている。また中央の部分が下がっている。その辺が驚きだった。いやだって取れるもんはとったほうがいいじゃん?と思っていましたので。

 これについてちょっと考えていたのだが,おそらく「すぐひっくり返されるところ」の点数が下がっていき,「ひっくり返されにくいところ」の得点が高くなっているのだろうと思う。彼らの対戦をすべて保存して状態を解析してみないとわからないのだが,間違いなく相関関係はあるだろうね。

 まぁ実を言うとオセロのAIを作るのは人生で2回目。1回目のプログラムはちゃんとミニマックス法を実装してた。その時の経験から言わせてもらうと,終盤は正直カドを取るということよりも量を取る方に評価関数を変えたほうが強くなった。確か40手ぐらい打ったらもうカドよりも量を取る方に評価関数を変えて,深読みさせたほうが強かった。終盤だとカドを取るべきと取らざるべきがあるからね。そう考えるとこの学習もミニマックス法を実装したほうが良かったかもしれない。

 ソースコードは公開しようと思ったけれど,いじっている間にスパゲティになったので公開はしないつもり。でもオセロはここで書いたやつを使いまわしてる。