トップ 最新 追記

U-memo

2006|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|08|
2009|08|10|
2010|02|03|
2011|11|12|
2012|04|
2016|02|
All= / Today= / Yesterday=

2007-11-01 [長年日記]

_ [雑記] 継投完全試合日本一!

うひょー!

頭でわかっていても8回完全試合中の山井をスイッチする落合監督すげぇ。 岩瀬もよくやった。

良かった生きているうちにドラゴンズの日本一を見られただよ。

本日のツッコミ(全2件) [ツッコミを入れる]

_ うんの [あー、おめでとうございます! サンデーで連載中の Major を彷彿しました。(漫画かよ!)]

_  [関係ないコメントです。 有名な鵜飼さんは滋賀県の方なんですね!さすが滋賀県です!]


2007-11-04 [長年日記]

_ [雑記] ブロックスデュオ プログラムメモ

いきなり当たって負かされた1位のhmmm(iroriの日記)

評価関数アルゴリズムのうち、勢力範囲のほうは骨子は同じような。 私のは使用ピースについてはこれから打つものに関しての大きさ以外の考慮なし。

使用ピースは変に考えても、境界の争いで 1,2-オミノ を打てなくなる弊害が大きすぎたので早々に捨てた。ただ、以下のとおり、確定自陣の評価にまだ打っていないピースが効いてくるけど。

私は勢力範囲無限大で傾斜配点をつけた(遠いほど点が減る)んですが、 距離きめ打ちのほうが速いかも。

   1 2 3 4 5 6 7 8 9 A B C D E
 ┏━━━━━━━━━━━━━━┓
1┃      □    ■              ┃
2┃      □  ■■■            ┃
3┃      □・  ■□■■        ┃
4┃    □□・・  □□■■      ┃
5┃      ◎□  □□    ■      ┃
6┃      □□□      ■        ┃
7┃        □  □□■■■      ┃
8┃          □  □□□■      ┃
9┃          □■  ■■        ┃
A┃          □■  ■■        ┃
B┃          □■  ■          ┃
C┃      □  □■■            ┃
D┃      □□                  ┃
E┃        □□                ┃
 ┻━━━━━━━━━━━━━━┛
  • 黒から見て◎のようにすり抜けられる場所は(低めながら)点数をつけた
  • ただし、手持ちのピースからはどうやっても侵入されないエリアが作れたら高い点数をつける (厳密にやると重すぎるのでやや大雑把に判断)

こんなことしてるから評価関数が重くなるんだな。 10/9に公開したヤツ ではその半分くらいインプリされた状態。

最終的には先手が強くなったけど、当初は後手のほうが強かった。 先手が打った直後は先手がリードしている局面であり、 後手が打った直後は互角の局面になっている、 と言う差がうまくバランスさせられなかったわけだが。 先手がやけに守りに入りすぎて後手に逆転されるとかいう感じ。

プログラムがヘボかったのと含めて 評価に時間がかかってしまっていたので、 候補を相当絞った上で(将棋の数え方で)3手先読みが限界でした。 hmmm は序盤から4〜6手読むそうだから勝てるわけがない。

α-βとかまじめにインプリする根性もなかったからいいけど。

あと、定石はなし(先手の初手だけ決めうち)。 最初の数手の手の広がり方が大きすぎるので定石を確立 する時間なんぞあるわけもなく。

大会の様子(おびなたのはてな日記)

モンテカルロがそこそこ強かったと? たまにツボに入って強いケースはあったけど、 自分のインプリのは(時間がかかる割りに)別に強くなかった気がする。

自分のプログラムのレベル5 (評価関数一手読み、思考時間数秒以下) に勝てないけどモンテカルロもどきには勝てるから。

_ [雑記] プログラム対戦反省

そもそもプログラムが汚い(まず関数型言語には見えない)のはさておいて

  • ヘボかった点: matrix_array を使ってしまったところ

局面の生成消失が派手に起こるので、高速化するつもりがあるなら 一次元配列で持っておくべきだった。 matrix_array は簡単に盤面のコピーができないのだ。 このせいでかなり時間は損したはず。 もっとも最初から一次元でやったとしてバグ取れたかどうかは疑問。

  • ヘボかった点2: 自分が弱い

評価関数1手読みで勝てなくなってから、プログラムを強くする手段を 判別するのが相当困難になってしまったとか言う。 イロイロ思いついたのを試してみても弱くなったりする始末。

  • ヘボかった点3: 完全読みがバグってるとか

そもそもαβとか諸々を実装してないとか他イロイロあるけど、 終盤の完全読みも殺してある。 まぁ、1ピース差とかの僅差の勝負にはならなかっただろうから たぶん問題ないと思うけど。

  • ヘボかった点4: 思考時間可変じゃない

消費時間を一切見てない。そこまで考えるのは嫌だったから、 3通りくらいの深さバリエーションを作っておいたけど、 どう実行されたのだろう?

  • 番外

12日の締め切り後に改善する気すらなかったし、 差し替えはしていません。


2007-11-05 [長年日記]

_ [雑記] プログラム対戦ソースとか

置いた。応募したものそのものです。 もとが GNU/Linux 上で開発したので Win 版はあまりみてない。

非商用かつ次回があったときにそのまま使わないくらいの条件でどうぞ。


2007-11-10 [長年日記]

_ [雑記] gcc で絶対値

cygwin + gcc 3.4.4 環境(Athlon XP)で試しましたが、 やはり -O0 は abs2 のほうがはやいですー。

それよりも -O0 なのに abs3 (三項演算子使用)を最適化する gcc は いかがなものか。

  • abs1
real	0m3.359s
user	0m3.359s
sys	0m0.015s
  • abs2
real	0m2.875s
user	0m2.858s
sys	0m0.015s
  • abs3
real	0m2.765s
user	0m2.765s
sys	0m0.015s

試したコードは以下のとおりでつ。

#include<stdio.h>
#include<stdlib.h>

int abs1(int x)
{
  if(0<x)return x;
  else return -x;
}

int abs2(int x)
{
  int y = x>>31;
  return (x^y)-y;
}

int abs3(int x)
{
  return 0<x ? x : -x;
}

main(int ac, char**av )
{
  volatile int c=1;
  int i;
  int s=atoi(av[1])-1;
  int m=RAND_MAX/2;
  int (*fun[3])(int) = {abs1,abs2,abs3};

  for(i=99999999;i>0;i--){
    c=rand()-m;
    c=fun[s](c);
  }
  printf("%d,%d\n",c,s);
}
  • abs1
pushl	%ebp
movl	%esp, %ebp
subl	$4, %esp
cmpl	$0, 8(%ebp)
jle	L2
movl	8(%ebp), %eax
movl	%eax, -4(%ebp)
jmp	L1
L2:
movl	8(%ebp), %eax
negl	%eax
movl	%eax, -4(%ebp)
L1:
movl	-4(%ebp), %eax
leave
ret
  • abs2
pushl	%ebp
movl	%esp, %ebp
subl	$4, %esp
movl	8(%ebp), %eax
sarl	$31, %eax
movl	%eax, -4(%ebp)
movl	-4(%ebp), %eax
xorl	8(%ebp), %eax
subl	-4(%ebp), %eax
leave
ret
  • abs3
pushl	%ebp
movl	%esp, %ebp
movl	8(%ebp), %eax
cltd
movl	%edx, %eax
xorl	8(%ebp), %eax
subl	%edx, %eax
popl	%ebp
ret
本日のツッコミ(全1件) [ツッコミを入れる]

_ Ozy [VCで問題なかったコードがGCCで問題があって,GCCで問題があったコードがVCで問題があって,というようなことが入..]


2007-11-16 [長年日記]

_ [雑記] hmmm と対戦させてみた。

duocaml は level5 (先読みしない)、 hmmm は思考時間5秒で、ほぼ同等の思考時間。

  • duocaml 先手 (L5) / hmmm 後手 (5sec) 67-68
+--------------+
|ooo    xx xx x|
|  oxxxx x  x x|
|oo   x xx x  x|
|ooxxxooooox x |
|o  xo  xx x x |
| o xooox xx x |
|oo  xoxx   ox |
| o xxxo xooox |
| oxox oxxoxxoo|
|oxo   ooxxoxxo|
|oxoooo o oo x |
| oxxx o ooxx x|
|oo oxoooxxx xx|
|o ooo o ooooxx|
+--------------+
P1:   c    h     n pq
P2:     e ghi       q
Turn-P2 / P1:67 P2:68 (99)
Player1:67  v.s. Player2:68  Finished.
Player 1 plays [66t0]
Player 2 plays [99t7]
Player 1 plays [7Al1]
Player 2 plays [86s2]
Player 1 plays [84j2]
Player 2 plays [B5k0]
Player 1 plays [ABr2]
Player 2 plays [58u0]
Player 1 plays [4Bk2]
Player 2 plays [CAr0]
Player 1 plays [27o1]
Player 2 plays [BDl3]
Player 1 plays [7Du0]
Player 2 plays [45p4]
Player 1 plays [14m4]
Player 2 plays [62o2]
Player 1 plays [21f6]
Player 2 plays [D6j0]
Player 1 plays [BEe2]
Player 2 plays [EDm0]
Player 1 plays [1Ab0]
Player 2 plays [39a0]
Player 1 plays [2Di2]
Player 2 plays [2Ab0]
Player 1 plays [4Eg6]
Player 2 plays [92n0]
Player 1 plays [B8s1]
Player 2 plays [4Cf6]
Player 1 plays [E9d3]
Player 2 plays [C1d3]
Player 1 plays [49a0]
Player 2 plays [E2c0]
Player 1 passes [----]
Player 2 passes [----]
  • hmmm 先手 (5sec) / duocaml 後手 (L5) / 82-54

これはひどい。完封負け

+--------------+
|ooxxxooooo    |
|oxooo x    oo |
|ooxxoox ooo oo|
|xxooxxx oo o  |
|x o oooo  ooo |
|x oxxxo oo o  |
|x o  xx  o  oo|
|oxxxx  x oo oo|
|oox oooxxx o  |
|oxoxxox  xoo  |
|xxoxxoxx oo   |
| xoxoxoxx  o o|
|x xoxxo  ooo o|
|xxxox ooo o oo|
+--------------+
P1:    de
P2:    def h j     p   tu
Turn-P2 / P1:82 P2:54 (99)
Player1:82  v.s. Player2:54  Finished.
Player 1 plays [75o2]
Player 2 plays [99s0]
Player 1 plays [A7s3]
Player 2 plays [66l6]
Player 1 plays [35k4]
Player 2 plays [38o3]
Player 1 plays [BAr2]
Player 2 plays [8Br3]
Player 1 plays [BDt1]
Player 2 plays [15k4]
Player 1 plays [52l6]
Player 2 plays [43b2]
Player 1 plays [7Eq0]
Player 2 plays [4Bm4]
Player 1 plays [A3m7]
Player 2 plays [2En2]
Player 1 plays [12n1]
Player 2 plays [74q1]
Player 1 plays [81j2]
Player 2 plays [2Bg1]
Player 1 plays [C5u0]
Player 2 plays [6Di2]
Player 1 plays [6Ap4]
Player 2 plays [22a0]
Player 1 plays [5Ca0]
Player 2 plays [41c2]
Player 1 plays [D2i0]
Player 2 passes [----]
Player 1 plays [D7h0]
Player 2 passes [----]
Player 1 plays [EDf0]
Player 2 passes [----]
Player 1 plays [4Db0]
Player 2 passes [----]
Player 1 plays [3Bc0]
Player 2 passes [----]
Player 1 plays [19g0]
Player 2 passes [----]
Player 1 passes [----]

実力差がかなりあることを認識。はう。