プログラミング(112) 階乗

n の階乗を n! と書きます。!（エクスクラメーションマーク）を使うのは、階乗がビックリするほど大きな数になるからだとか。

囲碁の9路盤を黒白交互に埋めていくと、どの位のパターンができるのか。ざっくり計算すると、最初に黒が選べる交点が81個、次に白が選べる交点が80個、というように組み合せの数は、81×80×...×1 = 81! になります。Small Basic で普通に計算しようとすると桁あふれを起こしてしまいます。そこで桁あふれが起きないようなプログラムを作ってみました。プログラムID HHW468-2 で発行しました。

このプログラムで81の階乗を計算してみました。

81! =
5,797,126,020,747,367,985,879,734,231,578,109,105,412,357,
244,731,625,958,745,865,049,716,390,179,693,892,056,256,
184,534,249,745,940,480,000,000,000,000,000,000

です。囲碁の場合は、これだけの組み合せがあるから三目並べのようにゲーム木の検索という手法がうまくいきません。それで統計的な手法が研究されているわけです。ちなみに19路盤のゲーム木の枝は、

361! =
1,437,923,258,884,890,654,832,362,511,499,863,354,754,907,
538,644,755,876,127,282,765,299,227,795,534,389,618,856,
841,908,003,141,196,071,413,794,434,890,585,968,383,968,
233,304,321,607,713,808,837,056,557,879,669,192,486,182,
709,780,035,899,021,100,579,450,107,333,050,792,627,771,
722,750,412,268,086,775,281,368,850,575,265,418,120,435,
021,506,234,663,026,434,426,736,326,270,927,646,433,025,
577,722,695,595,343,233,942,204,301,825,548,143,785,112,
222,186,834,487,969,871,267,194,205,609,533,306,413,935,
710,635,197,200,721,473,378,733,826,980,308,535,104,317,
420,365,367,377,988,721,756,551,345,004,129,106,165,050,
615,449,626,558,110,282,424,142,840,662,705,458,556,231,
015,637,528,928,999,248,573,883,166,476,871,652,120,015,
362,189,137,337,137,682,618,614,562,954,409,007,743,375,
894,907,714,439,917,299,937,133,680,728,459,000,034,496,
420,337,066,440,853,337,001,284,286,412,654,394,495,050,
773,954,560,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000

という数になります。ほんとうにビックリです。

統計ではたくさんの事例（母集団といいます）をすべて調べるのではなく、サンプル（標本）となる事例を調べて全体像を把握します。囲碁のプログラムで行われるモンテカルロ法はこの考え方をベースにして次の一手を決めるものです。