JIPDEC AITEC NEWS
News on FGCS Technology and related activities by
Research Institute for Advanced Information Technology(AITEC),
the successor of ICOT |
July 31, 1997 |
| Issue #12 |
【平成 9 年度「KLIC プログラミング・コンテスト」特集号 # 2】
コンテストに関する詳細は こちらのページ をご覧下さい。
目次
- はじめに
- 逐次環境部門課題：「一人遊びポーカー」
- 並列環境部門課題：「ライフゲーム」
- 編集後記
皆さん！
「ＫＬＩＣプログラミング・コンテスト」の課題が決まりました。
コンテストの応募要項は、７月２日に発行したＡＩＴＥＣ ＮＥＷＳ ＃１０で、
既にお知らせした通りです。この号では、その課題を発表します。なお、応募
要項は、ＡＩＴＥＣのホーム・ページ (http://www.icot.or.jp)でも見ること
が出来ます。あるいは、klic-contest@icot.or.jp までお気軽にお問合せ下さ
い。
今年度の課題は、逐次環境部門と並列環境部門とで異なったものを用意しまし
た。両課題とも、題材はゲームからとりましたので、コンテスト参加者の方々
には、きっと楽しんでプログラミングして頂けると考えています。
本コンテストは、ＫＬＩＣを知らない方も大歓迎です。そのような方々のため
に、テキストの配布や初心者向けの講習会(無料)も行ないます。詳しいことは
応募要項をご覧下さい。
さぁ、「ＫＬＩＣプログラミング・コンテスト」に参加して、貴方のプログラ
ム作成の腕前を競ってみませんか？
==========================================
【逐次環境部門課題】：「一人遊びポーカー」
==========================================
まず、一組のトランプ52枚（ジョーカーは含まないものとする）から、
25枚のカードが配られる。 この25枚のカードを5×5の桝目に並べるとする。
並べた桝目の各列それぞれをポーカーの手札として評価したとき、
より高い総合点となる並び方を、できるだけ早く求めよ。
なお、これら縦5列、横5列、対角線2列の合計12列によって構成される各手札は、
次の手役とその評価値によって総合点を計算すること。
--------------------
１. 総合点の計算方法
--------------------
総合点 ＝ 縦5列、横5列、対角線2列を手役としたときの評価値の合計
評価値 ＝ 役の基準点 ＋ 加点
【役の基準点】
ストレートフラッシュ （同一組の札の5枚続きの手）
Straight Flush 2745600 点
フォーカード （同じ数の札の 4 枚ぞろい）
Four of a Kind 176000 点
フルハウス（3枚の同位札と2枚の同位札からなる手）
Full House 29333 点
フラッシュ（同一組の札の5枚ぞろいの手）
Flush 21500 点
ストレート（異なる組の5枚続きの手）
Straight 10767 点
スリーカード（同じ数の札の 3 枚そろい）
Three of a Kind 2000 点
ツーペア（2枚の同位札2組からなる手）
Two Pairs 888 点
ワンペア（同じ数の札の2枚そろい）
One Pair 100 点
注）ストレートおよびストレートフラッシュでは、A（エース）は
最高ランクとしても最低ランク(1)としても使える。
従って、10,J,Q,K,A あるいは A,2,3,4,5 の組合せで使うことができる。
【加点】
手札のうち、役を構成するのに用いられた札についてのみ、次の点を加える。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
なおこの加点は、各手役ごとに独立して計算されるため、同じ札が別の（縦、横、
対角線）の役に用いられた場合にも計算対象となる。
A エース 14 点 （エースとして用いたとき）
K キング 13 点
Q クイーン 12 点
J ジャック 11 点
10〜2は、その位の札の数 をそのまま加点とする
A 1 点 （ストレートで1として用いたとき）
計算例： ツーペア K,K,8,8,A は、基準点 888点、
加点はKの2枚と8の2枚について 13×2+8×2 = 42 点 となる。
よって、888+42 = 930 点 となる。
ストレート 10,J,Q,K,A は、基準点 10767 点に
加点は 10+11+12+13+14 = 60 点 より、10767+60 = 10827点 となる。
ストレートフラッシュ A,2,3,4,5 は、基準点 2745600 点に
加点が 1+2+3+4+5 = 15点 より、2745600 + 15 = 2745615点となる。
----------------------
２. プログラムについて
----------------------
--------------------
２.１ インタフェース
--------------------
モジュール名をsolitaire、述語名をpoker とする2引数の述語を用意せよ。
第1引数を入力として25枚のカードを渡し、第2引数を出力として解のリスト
となるカード並びを返すものとする。
もちろんこれ以外のモジュールを補助的に用いてもかまわないが、
その場合には solitaire_xxxx （xxxxは任意）の形式とすること。
例）?- solitaire:poker([card(8,spades),card(2,diamonds),...],Result)
に対して、次のように解がストリームResultに流れる。
Result = [X1,X2,....],
X1 = [card(2,diamonds),....,card(8,spades),...],
X2 = [card(8,spades),...,card(2,diamonds),....],
(1) 入力：要素数25のリストを入力とする。リスト要素が1枚のカードを表す。
各カードはcard(Rank,Suit) の形のファンクタとする。
Rankはカードの位、2,3,4,5,6,7,8,9,10,jack,queen,king,ace を
Suitはカードの組、spades, hearts, diamonds, clubs をそれぞれ表す。
なお、同じカードは重複して現れないものとする。
例）card(10,spades), card(jack,clubs), card(ace,hearts)
(2) 出力：解を出力するストリームとする。
ストリームに流される解は、入力と同形式のリストである。
解は、先頭からの要素を以下1〜25の順に5×5に並べたものとみなす。
1, 2, 3, 4, 5,
6, 7, 8, 9,10,
11,12,13,14,15,
16,17,18,19,20,
21,22,23,24,25
上の並びにおいて、横 (1,2,3,4,5),...,(21,22,23,24,25),
縦 (1,6,11,16,21),...,,(5,10,15,20,25) および 対角線
(1,7,13,19,25),(5,9,13,17,21)を手役として評価する。
従って、回転や線対称になる並びでは総合点は同じとなる。
例）解 [card(10,spades), card(ace,clubs), card(queen,diamonds),
card(9,hearts), card(ace,hearts), card(6,diamonds),
card(jack,spades), card(7,hearts), card(ace,diamonds),
card(5,diamonds), card(4,hearts), card(10,clubs),
card(queen,spades), card(9,spades), card(9,diamonds),
card(2,spades), card(8,spades), card(8,hearts),
card(7,spades), card(king,diamonds), card(8,clubs),
card(queen,clubs), card(jack,diamonds), card(3,clubs),
card(6,spades)] は、
手札の組 spades,hearts,diamonds,clubsをそれぞれS,H,D,Cで、
位 10,jack,queen,king,aceをそれぞれ T,J,Q,K,A で表すと、
次のような並びと点に相当する。
縦
0 | 0 | 124 | 118 | 0 | 932 対角線
------+------+------+------+------+--
ST | CA | DQ | H9 | HA | 128
D6 | SJ | H7 | DA | D5 | 0
H4 | CT | SQ | S9 | D9 | 118 横
S2 | S8 | H8 | S7 | DK | 116
C8 | CQ | DJ | C3 | S6 | 0
------+------+------+------+------+--
| 21546 対角線
TOTAL=23082
注意）出力はストリームであり、複数解を出力してもかまわないが、
それぞれの解は、ストリームに流す際に完全に具体化しなければ
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ならない。 すなわち、未完成で未束縛変数を含む項を解として
~~~~~~~~~
出力してはならない。 また、複数解を出力した場合には、
~~~~~~~~~~~~~~~~~~~~~~~~~
審査時間内に出力された解のうち、最後のものを審査の際の
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
評価対象とする。
~~~~~~~~~~~~~~
（完全に具体化した解のみを出力するためには、解が全部具体化
していることを wait ガード述語などを用いて確かめた後に、
ストリームに出力するようにすれば良い。）
----------------------------
２.２ プログラミング上の制限
----------------------------
・C言語のインライン挿入を使ってはならない。
・ボディ・ゴールの優先順位指定のために、
`GOAL@priority(ABSPRIO)'
の形式は使ってはならない。
優先順位指定では、
`GOAL@lower_priority'
`GOAL@lower_priority(RELPRIO)'
の形式のみ使用して良い。
--------------------------------
３. 応募作品に対する判定について
--------------------------------
入賞は審査委員会の定める制限時間以内に得た最後の完全な解について、
その総合点の高さを主たる基準に、プログラムの構成、添付文書のわかりやすさ
などを考慮に入れて審査の上、決定する。
--------
４. 参考
--------
参考として手札の評価実験プログラム(以下、「添付プログラム」と呼ぶ)を
用意しています。
http://www.icot.or.jp/AITEC/FGCS/KLICON/97/kadai97-J.html
にアクセスして頂くか、
klic-contest@icot.or.jp
に、「逐次環境部門、添付プログラム希望」とメールして下さい。
======================================
【並列環境部門課題】：「ライフゲーム」
======================================
コンウェイ(John Horton Conway)のライフゲームを作りましょう。入力で初
期状態と世代数が指定されるものとし, 最終状態を出力するものとします。
負荷分散をするのにどういうようにプログラムを書いたらいいでしょうか。ど
れくらい高速に計算できるでしょうか。
------------------------
１. ライフゲームについて
------------------------
ライフゲームは, (理想的には無限の) 2 次元の格子状に並んだセルの状態
が規則によって自動的に変化していくゲームです。すべてのセルはオンとオフ
との 2 種類の状態のいずれかを取ります(以下ではオンのセルを ■ で, オフ
のセルを □ で表します)。そして, 時間の流れは離散的で, 世代から世代に
進みます。ある世代の状態によって次の世代の状態が決り, 続けて, 次の世代
の状態からその次の世代の状態が決り... というように進みます。
規則は以下の通りです。一つのセルに注目すると, 隣り合うセルに縦横斜め
あわせて 8 つのセルがあります(図 1. 参照)。★ を注目するセルとすると
☆ が隣り合うセルです。
☆☆☆
☆★☆
☆☆☆
図 1. 隣り合うセル
【規則 その 1】
注目するセルがオンの場合, 隣り合うセルでオンのものが 2 つ,
あるいは 3 つの場合, 次の世代でもオンとなります。隣り合う
セルでオンのものが 0, 1, 4, 5, 6, 7, 8 の場合, 次の世代で
はオフになります。
【規則 その 2】
注目するセルがオフの場合, 隣り合うセルでオンのものが 3 つ
の場合, 次の世代でオンとなります。隣り合うセルでオンのもの
が 0, 1, 2, 4, 5, 6, 7, 8 の場合, 次の世代でもオフのままで
す。
具体例をあげてみます。
【例 その 1 (ブリンカー)】
ブリンカーと呼ばれる周期 2 のパターンです。
□□□□□ □□□□□ □□□□□
□□□□□ □□■□□ □□□□□
□■■■□ □□■□□ □■■■□
□□□□□ □□■□□ □□□□□
□□□□□ □□□□□ □□□□□
世代 N 世代 N+1 世代 N+2
図 2. ブリンカー
【例 その 2 (安定なパターン)】
世代によって変化しない安定なパターンです。
□□□□□□ □□□□
□□■■□□ □■■□
□■□□■□ □■■□
□□■■□□ □□□□
□□□□□□
図 3. 安定なパターン
【例 その 3 (グライダー)】
移動していくパターンです。
□□□□□□ □□□□□□ □□□□□□ □□□□□□ □□□□□□
□□■□□□ □□□□□□ □□□□□□ □□□□□□ □□□□□□
□□□■□□ □■□■□□ □□□■□□ □□■□□□ □□□■□□
□■■■□□ □□■■□□ □■□■□□ □□□■■□ □□□□■□
□□□□□□ □□■□□□ □□■■□□ □□■■□□ □□■■■□
□□□□□□ □□□□□□ □□□□□□ □□□□□□ □□□□□□
世代 N 世代 N+1 世代 N+2 世代 N+3 世代 N+4
図 4. グライダー
----------------------
２. プログラムについて
----------------------
---------------------------------
２．１ プログラムのインタフェース
---------------------------------
応募作品では, モジュール名を life, 述語名を compute とする 3 引数の
述語を用意して下さい。
life:compute(世代数, 初期状態, 最終状態)
第 1 引数, 第 2 引数が入力で, 第 3 引数が出力となります。
第 1 引数は, 世代数として, 何世代後まで計算するかの整数が渡ります。
第 2 引数は, 初期状態としてオンのセルのリストが渡ります。
第 3 引数は, 最終状態としてオンのセルのリストが返るとします。
ここで, オンのセルは, X, Y を座標を示す整数とした時, p(X,Y) というファ
ンクタ p/2 のデータ構造とします。
また, オンのセルのリストは, それらの座標にしたがって昇順にソートされて
いるとします。ここで, 二つの座標 p(X0,Y0), p(X1,Y1) は, Y0 < Y1 あるいは
Y0 = Y1 で X0 < X1 のとき, そしてそのときのみ, p(X0,Y0) < p(X1,Y1) である
とします。
例(グライダー):
?- life:compute(4,[ p(2,1),
p(3,2),
p(1,3), p(2,3), p(3,3)],Result).
に対して,
Result = [ p(3,2),
p(4,3),
p(2,4), p(3,4), p(4,4)].
が求まります。
-------------------------------
２．２ 入力データの範囲について
-------------------------------
入力データ中, および指定した最終世代までの間の各世代におけるオンのセル
座標は -2^20 から 2^20 の範囲にあるものとします。
-----------------------------------------
２．３ プログラミング上の制限および注意点
-----------------------------------------
・C 言語のインライン挿入を使わないで下さい。
・並列なので, @node 使わないと意味がないことに留意して下さい。
--------------------------------
３. 応募作品に対する判定について
--------------------------------
入賞は審査委員会の定めるいくつかの初期状態パターンに対して要した計算
時間を主たる基準に, プログラムの構成と美しさ, 利用している手法の面白さ,
添付文書のわかりやすさなどを考慮に入れて審査の上, 決定します。
--------
４. 参考
--------
参考としてメインルーチンとグラフィカルユーザインターフェースのプログ
ラム, およびサンプル入力とその出力(これらを以下、「添付プログラム」と
呼ぶ)を用意しています。
http://www.icot.or.jp/AITEC/FGCS/KLICON/97/kadai97-J.html
にアクセスして頂くか、
klic-contest@icot.or.jp
に、「並列環境部門、添付プログラム希望」とメールして下さい。
以上、今年度の「ＫＬＩＣ プログラミング・コンテスト」の課題についてお知らせ
しました。
本コンテストに関する最新情報は、
http://www.icot.or.jp/AITEC/FGCS/KLICON/97/KLIC97-J.html
で、お知らせしています。今後の情報にご注意下さい。
また、参加申込をなさった方々には、課題に関連した添付プログラム（「４. 参考」
参照）の更新などの最新情報や、ＫＬＩＣ講習会(無料)案内をメールでお知らせ
します。本コンテストに興味を持った方は、是非参加申込をして下さい。
参加申込に関する詳しいことは、
http://www.icot.or.jp/AITEC/FGCS/KLICON/97/submit97-J.html
をご覧下さい。
では、今年も皆さんの積極的参加をお待ちしています！
☆＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊☆
ＡＩＴＥＣ ＮＥＷＳ Ｉｓｓｕｅ ＃１２
編集・配布 ＡＩＴＥＣ ＮＥＷＳ編集グループ
佐藤真紀子 高橋千恵 相場 亮 河西和美
武田 浩一 鳥居良春 佐藤 博 内田俊一
発行 1997年7月31日
財団法人 日本情報処理開発協会 先端情報技術研究所
東京都港区芝2丁目3番3号 芝東京海上ビル2F
TEL :03-3456-3191 FAX :03-3455-4877
e-mail: aitec-news@icot.or.jp
URL : http://www.icot.or.jp
☆＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊☆
www-admin@icot.or.jp