jump

飛び越しゲーム
計算数理２演習課題１
２０１１年度（阿原)
次のようなゲームを考えます
• 黒石を6つ、白石を6つ用意して、2×９の
升目の上に、下図のようにおきます。これ
で準備完了です。
●●●
●●●
○○○
○○○
基本ルール
• 二人のプレーヤーがそれぞれ黒石・白石を動か
します。黒石は左から右へ、白石は右から左へと
動かします。
• 黒石と白石は交互に動かします。動かせる状況
であるならばパスをすることは許されません。
• つながった相手の石を飛び越すことが出来ます。
（自分の石は飛び越せません。）
飛び越し方
• 下の図のように、飛び越すことが出来ます。
●●
●○
● ● ○●
○○
○
○
飛べない例
• 隙間があったり、自分の石があると飛び越
せません
●
●●
●○●
●○
○○
○
○
上がり
• 黒石は、全部右側に寄せれば上がり、白
石は全部左側に寄せれば上がりです。
黒勝ち
○○ ○
●●●
○○○
●●●
盤の名前の付け方
0 1 2 3 4 5 6 7 8
9 1011121314151617
2*9
0 1 2 3 4 5 6 7 8 8
9 2*10
10111213141516171819
補助的なルール
• このゲームでは、動かせる場所がある場
合にはパスできません。
• 自分の石がないところを指定すると、即負
けになります。
このゲームの戦術を考えてください
• あなたは黒を持って、このゲームで出来る
だけ勝つようなアルゴリズムを考案してくだ
さい。
• 盤のサイズが２＊９，２＊１０の2つの場合
について戦術を考えてください。そして、そ
れぞれの場合について、阿原が準備した３
人のプレーヤーからできるだけ勝ちを上げ
てください。
戦術のポイント
•
•
•
一般論としては，相手の石をたくさん飛び
越したほうが早くゴールに近づきます。
相手に自分の石を飛び越させないように
することも大切です。
相手を手詰まりにもちこんで、こちらが手
を進めるという作戦もあり得ます。
戦術のポイント２
•
•
パスができないことを戦術に組み込むのも大切
なことです。相手が動かしたくない石を、ほかの
石を手詰まりにすることによって、無理やり動
かさせるという戦術もあり得ます。
完全情報ゲームなので，必ず先手必勝か後手
必勝があるはずですが，先手を持った場合，後
手を持った場合，どちらも善戦できるプログラ
ムを作ってください．（コンピュータ側は必勝手
順で指すことはしません．）
ダウンロードファイル
• http://www.math.meiji.ac.jp/~ahara/sk２
e/2011jump2008.zip
• http://www.math.meiji.ac.jp/~ahara/sk２
e/2011jump2010.zip
をダウンロードしてください。（表紙ページにもリンクが
あります。）これを解凍すると、いくつかのファイル
が現れますが、それらが同じフォルダにあるように
してください。（普通に解凍すればそうなります。）
• jump.vcprojというファイルをダブルクリックすると，
Visual C++が起動します．
• 皆さんが編集してよいのはjump.cppのみです。
コンパイルと実行
•
•
まずはプログラムを変更することなく，「デ
バッグ」メニューから「デバッグ開始」を選
んでください．[F5]キーを押しても同じこと
です．以後，プログラムを動かすときには
いつもこの方法を用いてください．
もし，「悪いことをした心当たりがない」の
にコンパイルできなくなった場合には，
「ビルド」メニューの「ソリューションのリビ
ルド」を選択してください．それでも動かな
かったら阿原を呼んでください．
プログラムの画面
動かし方
●
●
まずは自分の手入力とプログラムとで対戦し
てみてください．「盤の大きさ｣「プレーヤー２選
択」をしてから，「1ゲーム（先手）」または「1ゲ
ーム（後手）」をクリックしてください．
プレーヤー１を手入力にしておけば，画面上
の青いコマをクリックすることによって，プレー
ヤー２と対戦することができます．
プログラミング開始
●
●
あらかた遊んだら，今度はプログラミングをしてましょ
う．一度ゲーム画面を閉じて，Visual C++の画面に
戻ります．
左側（時に右側）に「ソリューションエクスプローラー」
をかかれた部分があり，そこに「太字のjump」をダブ
ルクリックします．そして「ソースファイル」をダブルク
リックして「jump.cpp」をダブルクリックします．（この
作業は一度おこなえば，次からは自動的に開いてく
れます．）
プログラム開始
●
Jump.cppというファイルを開くと，下のほうに
●
Int Form1::myplay(void){
・・・・・・
}
という部分があり，ここが「プログラム本体」で
す．ここに飛び越しゲームをプレーする戦略プ
ログラムを書いてもらいます．
プログラムの手引き
• 盤面を左から
• int board[];
• という配列変数で表します。青石（あなた）
は１、赤石（相手）は２、何もないところは０
であらわされます。2*9盤の最初の状態で
は、
board[0]=board[1]=board[2]=1;
board[9]=board[10]=board[11]=1;
です。（２列目は9~17になります。）
盤の大きさを表す変数width
●
●
widthという変数があり、これで盤の幅をあら
わしています。つまり、widthの変数の値は
9,10のいずれかです。
このことから、左下の升目は
board[width]
とあらわされることが分かります。
jump.cppの中身
int Form1::myplay(void){
int i;
for(i=0;i<2*width;i++){
if(player1_movable(board,i)){
return i;
}
}
return -1;
}
この中身を変更してください。
return iとは？
• この関数では、「次に動かす石の位置」を指定し
ます。上段一番左が０、一番右が８です。動かせ
る黒石がそこにあれば、あとはプログラムが動か
してくれます。もし、動かせる黒石でない場所を
指定した場合は負けです。初手で２の位置にあ
る黒石を一つ右へ動かすためには、最初に
return 2;
とすればよいことがわかります。
使ってよいデータは
• 配列変数board[]だけが参照できるデー
タです。（これがゲームの情報の全てです。
完全情報ゲームといいます。）
• ２*９の時には配列変数の大きさは１８です
が、２＊１０の時には２０となります。この配
列変数の値から、次に動かす石の場所を
返すような関数を作ってください。
使ってよい関数
• bool player1_movable(int b[],int i);
という関数を用意しました。これはi番の場所
を指定した場合、そこに黒石があって、そ
の黒石が動かせる状況にあれば、trueが
返され、それ以外の場合にはfalseが返さ
れる関数です。通常は
if(player1_movable(board,2)){
return 2;
}
のように使ってください。
初級者のためのヒント（１）
int i;
for(i=0;i<2*width;i++){
if(player1_movable(board,i)){
return i;
}
}
こうすることによって、「盤面の0から順に2*width-1まで
調べて、もし、動かせるコマがあればそのコマを動かす」と
いう命令になります。
初級者のためのヒント（２）
int i;
for(i=2*width-1;i>=0;i--){
if(player1_movable(board,i)){
return i;
}
}
こうすることによって、「盤面の2*width-1から順に0まで
（減らしながら）調べて、もし、動かせるコマがあればそのコ
マを動かす」という命令になります。
初級者のための練習問題
●
●
width=9だとして、盤面を、0,9,1,10,2,11,…
の順番に調べたいときには、どのようにプログ
ラムを組めばよいでしょうか？
width=9だとして、盤面を、
8,17,7,16,6,15,…の順番に調べたいときに
は、どのようにプログラムを組めばよいでしょ
うか？
初級者のためのヒント
●
●
盤面の i 番を調べているときに、「一つ右隣
の盤面」を調べたいときには
board[i+1]
という変数を調べればよいことがわかります。
「一つ右隣に相手のコマがあれば」という条件
文は
if(board[i+1]==2){
と書けばよいことがわかります。
レポートのポイント
●
●
勝つための戦略を明確にレポートしてください。「ひたすら進
める」などの漠然とした表現はだめです。
勝てなかったゲームについて、どの手がまずくて勝てなかっ
たかをレポートしてください。つまり、ポイントとなる盤面を再
現し、そこであなたのプログラムは＊＊という手を指したが、
実際には＋＋のほうが良い手であった。という感じのレポート
を作ってください。

Download Report