飛び越しゲーム 計算数理２演習　課題１ ２０１１年度（阿原).

Presentation on theme: "飛び越しゲーム 計算数理２演習　課題１ ２０１１年度（阿原)."— Presentation transcript:

1 飛び越しゲーム 計算数理２演習　課題１ ２０１１年度（阿原)

2 ● ● ● ○ ○ ○ ● ● ● ○ ○ ○ 次のようなゲームを考えます
黒石を6つ、白石を6つ用意して、2×９の 升目の上に、下図のようにおきます。これ で準備完了です。 ● ● ● ○ ○ ○ ● ● ● ○ ○ ○

3 基本ルール 二人のプレーヤーがそれぞれ黒石・白石を動か します。黒石は左から右へ、白石は右から左へと 動かします。
黒石と白石は交互に動かします。動かせる状況 であるならばパスをすることは許されません。 つながった相手の石を飛び越すことが出来ま す。（自分の石は飛び越せません。）

4 飛び越し方 下の図のように、飛び越すことが出来ます。 ● ○ ● ○ ● ○

5 飛べない例 隙間があったり、自分の石があると飛び越 せません ● ○ ● ○

6 上がり 黒石は、全部右側に寄せれば上がり、白 石は全部左側に寄せれば上がりです。 黒勝ち ○ ○ ○ ● ● ● ○ ○ ○ ● ● ●

7 盤の名前の付け方 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 2*9 9 10 11 12 13 14 15 16 17 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 8 2*10 10 11 12 13 14 15 16 17 18 19

8 補助的なルール このゲームでは、動かせる場所がある場 合にはパスできません。 自分の石がないところを指定すると、即負 けになります。

9 このゲームの戦術を考えてください あなたは黒を持って、このゲームで出来る だけ勝つようなアルゴリズムを考案してくだ さい。
盤のサイズが２＊９，２＊１０の2つの場合 について戦術を考えてください。そして、そ れぞれの場合について、阿原が準備した３ 人のプレーヤーからできるだけ勝ちを上げ てください。

10 戦術のポイント 一般論としては，相手の石をたくさん飛び 越したほうが早くゴールに近づきます。
相手に自分の石を飛び越させないように することも大切です。 相手を手詰まりにもちこんで、こちらが手 を進めるという作戦もあり得ます。

11 戦術のポイント２ パスができないことを戦術に組み込むのも大切なことです。相手が動かしたくない石を、ほかの石を手詰まりにすることによって、無理やり動かさせるという戦術もあり得ます。 完全情報ゲームなので，必ず先手必勝か後手必勝があるはずですが，先手を持った場合，後手を持った場合，どちらも善戦できるプログラムを作ってください．（コンピュータ側は必勝手順で指すことはしません．）

12 ダウンロードファイル e/2011jump2008.zip e/2011jump2010.zip をダウンロードしてください。（表紙ページにもリンクが あります。）これを解凍すると、いくつかのファイル が現れますが、それらが同じフォルダにあるように してください。（普通に解凍すればそうなります。） jump.vcprojというファイルをダブルクリックすると， Visual C++が起動します． 皆さんが編集してよいのはjump.cppのみです。

13 コンパイルと実行 まずはプログラムを変更することなく，「デバッグ」メニューから「デバッグ開始」を選んでください．[F5]キーを押しても同じことです．以後，プログラムを動かすときにはいつもこの方法を用いてください． もし，「悪いことをした心当たりがない」のにコンパイルできなくなった場合には，「ビルド」メニューの「ソリューションのリビルド」を選択してください．それでも動かなかったら阿原を呼んでください．

14 プログラムの画面

15 動かし方 まずは自分の手入力とプログラムとで対戦し てみてください．「盤の大きさ｣「プレーヤー２選 択」をしてから，「1ゲーム（先手）」または「1ゲ ーム（後手）」をクリックしてください． プレーヤー１を手入力にしておけば，画面上 の青いコマをクリックすることによって，プレー ヤー２と対戦することができます．

16 プログラミング開始 あらかた遊んだら，今度はプログラミングをしてましょ う．一度ゲーム画面を閉じて，Visual C++の画面に 戻ります．
左側（時に右側）に「ソリューションエクスプローラー」 をかかれた部分があり，そこに「太字のjump」をダブ ルクリックします．そして「ソースファイル」をダブルク リックして「jump.cpp」をダブルクリックします．（この 作業は一度おこなえば，次からは自動的に開いてく れます．）

17 プログラム開始 Jump.cppというファイルを開くと，下のほうに Int Form1::myplay(void){ ・・・・・・ }
　} 　という部分があり，ここが「プログラム本体」で す．ここに飛び越しゲームをプレーする戦略プ ログラムを書いてもらいます．

18 プログラムの手引き 盤面を左から int board[];
という配列変数で表します。青石（あなた） は１、赤石（相手）は２、何もないところは０ であらわされます。2*9盤の最初の状態で は、 board[0]=board[1]=board[2]=1; board[9]=board[10]=board[11]=1; です。（２列目は9~17になります。）

19 盤の大きさを表す変数width widthという変数があり、これで盤の幅をあら わしています。つまり、widthの変数の値は 9,10のいずれかです。 このことから、左下の升目は board[width] とあらわされることが分かります。

20 jump.cppの中身 この中身を変更してください。 int Form1::myplay(void){ int i;
for(i=0;i<2*width;i++){ if(player1_movable(board,i)){ return i; } return -1; この中身を変更してください。

21 return iとは？ この関数では、「次に動かす石の位置」を指定し ます。上段一番左が０、一番右が８です。動かせ る黒石がそこにあれば、あとはプログラムが動か してくれます。もし、動かせる黒石でない場所を 指定した場合は負けです。初手で２の位置にあ る黒石を一つ右へ動かすためには、最初に 　　　　return 2; とすればよいことがわかります。

22 使ってよいデータは 配列変数board[]だけが参照できるデー タです。（これがゲームの情報の全てです。 完全情報ゲームといいます。）
２*９の時には配列変数の大きさは１８です が、２＊１０の時には２０となります。この配 列変数の値から、次に動かす石の場所を 返すような関数を作ってください。

23 使ってよい関数 bool player1_movable(int b[],int i); という関数を用意しました。これはi番の場所 を指定した場合、そこに黒石があって、そ の黒石が動かせる状況にあれば、trueが 返され、それ以外の場合にはfalseが返さ れる関数です。通常は if(player1_movable(board,2)){ 　　　return 2; } のように使ってください。

24 初級者のためのヒント（１） int i; for(i=0;i<2*width;i++){ if(player1_movable(board,i)){ return i; } こうすることによって、「盤面の0から順に2*width-1まで調べて、もし、動かせるコマがあればそのコマを動かす」という命令になります。

25 初級者のためのヒント（２） int i; for(i=2*width-1;i>=0;i--){ if(player1_movable(board,i)){ return i; } こうすることによって、「盤面の2*width-1から順に0まで（減らしながら）調べて、もし、動かせるコマがあればそのコマを動かす」という命令になります。

26 初級者のための練習問題 width=9だとして、盤面を、0,9,1,10,2,11,… の順番に調べたいときには、どのようにプログ ラムを組めばよいでしょうか？ width=9だとして、盤面を、 8,17,7,16,6,15,…の順番に調べたいときに は、どのようにプログラムを組めばよいでしょ うか？

27 初級者のためのヒント 盤面の　i　番を調べているときに、「一つ右隣 の盤面」を調べたいときには board[i+1] という変数を調べればよいことがわかります。 「一つ右隣に相手のコマがあれば」という条件 文は if(board[i+1]==2){ と書けばよいことがわかります。

28 レポートのポイント 勝つための戦略を明確にレポートしてください。「ひたすら進 める」などの漠然とした表現はだめです。
勝てなかったゲームについて、どの手がまずくて勝てなかっ たかをレポートしてください。つまり、ポイントとなる盤面を再 現し、そこであなたのプログラムは＊＊という手を指したが、 実際には＋＋のほうが良い手であった。という感じのレポート を作ってください。