Anaconda 3というPython開発環境はシステム実習2だけに用意されている。個人のパソコンにインストールしたい場合はanacondaのホームページ (https://www.python.jp/install/anaconda/windows/install.html)に参照しましょう。 注意：古いパソコンにはインストールしない方が安心です。
- Python入門編https://www.python.ambitious-engineer.com/introduction-index
- Anaconda Prompt, Pythonを実行してから、インタープリター上でプログラムを入力する。授業中のログ（20191002.log）
- Jupyter Notebookを使ってみよ https://pythondatascience.plavox.info/python/Jupyter Notebook を使ってみよう
- Google Colabについて：https://www.python.jp/train/experience/index.html
ハノイの塔を状態空間法で解決する
Pythonプログラムソース
Rubik Cube 2x2 3D(https://www.grubiks.com/puzzles/rubiks-mini-cube-2x2x2/)
グラフのサンプル：graphs_notebook.pdf
幅優先探索アルゴリズムの実装プログラム(2.7), 幅優先探索アルゴリズムの実装プログラム(3.*)
縦優先探索アルゴリズムの実装プログラム
グラフ１：均一コスト探索の例
Wikipediaのダイクストラ法は均一コスト探索と同じことを行っている。
課題4: 必修：1),2), 選択:3)
1)迷路の問題を解けるとき、sからtまでの経路を求める。幅優先探索による解と深さ優先探索の解を求めよ。
その時の探索木、OpenList,ClosedListのステップごとに示す。
2)グラフ１について、A(スタート)、L(ゴール)の時、均一コスト探索の解を求めよ(networkxライブラリを用いて計算を行う)
3)双方向探索の幅優先探索による、グラフ探索プログラムを作成する。グラフ１について、A(スタート)、L(ゴール)の時、実行結果を示す。
双方向探索は初期状態から前向きに、そしてゴールから後ろ向きにと同時に探索して、中央で二つの探索が出会うときに止まるというものである。このアルゴリズムの終了条件は
Aノードが両方の探索の訪問されたリストにある。
Graph Heuristic Search (graph1), Sのヒューリスティック値は10とGのヒューリスティック値は0をする.
山登り法の別名は勾配降下法(Gradient Descent)がある。ヒューリスティック関数の値を比較する時、最小値が優先すれば、勾配降下法を行う。
山登り法コード, 第10回のグラフgraph1とgraph1_hヒューリスティックを使用する。
課題5:(a),(c):必修, (b),(d):選択
(a) グラフの図(A:スタート, h(A)=4,G:ゴール, h(G)=0),迷路の図(h(S)=9,h(G)=0)
1. 最良優先探索を用いて、解を求めよ。
2. A*探索を用いて、解を求めよ。g(n)=Sからノードnまでの枝の数をコストする（探索木のノードnの深さと同じである）。迷路の場合はg(n)=Sからノードnまでのマスの数をコストする
探索木、OpenList, ClosedListなどを示す。
(b) 迷路の図,
1. h*(n)は効用的ヒューリスティックですか
2. 直線距離のヒューリスティックに比較すれば、優位ヒューリスティックはどれでしょうか。
(c) グラフ(A:スタート,G:ゴール)(課題5.(a))の最良優先探索プログラムをコメントし、アルゴリズムステップごとの部分をプログラムに明確する。
(d): スライドにあるグラフ例題2のデータを入力し、GraphRomania.pyを修正し、例題2のソースコードと実行出力結果を提出する。グラフに載ってないノードコストはh(S)=10,h(G)=0にする。
testGraph()には、枝を追加する時、g.addEdge(WeightedEdge(隣接するノードと重み))という命令を行う。
WeightedEdge変わりにEdgeクラスを使用する。その時、枝の重みはありません。例えば、Sのノード
はnodes[0]、Gのノードはnodes[7]となっている。
reversi-test.ipynb オセロプログラム（python 3.4バージョン）
game_print.pdf 三目並べプログラムのクラス図
tictactoe_ai2-1.py 三目並べプログラム（python 3.4以上バージョン）
tictactoe_ai2-minimax.py 三目並べプログラム（python 3.4以上バージョン）とミニマックス法
課題6:
ミニマックス法とアルファーベータ法でMAXの最善手とMINの最善手を求めなさい。アルファーベータ法でカットできるノード（探索されないノード）を示しなさい。
