Lab 6: World Cup

この Lab では1~2人のクラスメートと協力することは問題ありませんが、そのグループのすべての受講生が等しく実習に貢献することが求められます。

FIFAワールドカップのシミュレーションプログラムを作成します。

$ python tournament.py 2018m.csv
Belgium: 20.9% chance of winning
Brazil: 20.3% chance of winning
Portugal: 14.5% chance of winning
Spain: 13.6% chance of winning
Switzerland: 10.5% chance of winning
Argentina: 6.5% chance of winning
England: 3.7% chance of winning
France: 3.3% chance of winning
Denmark: 2.2% chance of winning
Croatia: 2.0% chance of winning
Colombia: 1.8% chance of winning
Sweden: 0.5% chance of winning
Uruguay: 0.1% chance of winning
Mexico: 0.1% chance of winning

背景

サッカーのワールドカップ (W杯) の決勝トーナメントは16チームで行われます。各ラウンドでは、それぞれのチームが別のチームと対戦し、負けたチームは除外されます。2チームしか残っていない場合、決勝戦の勝者がチャンピオンとなります。

サッカーでは、各チームの相対的な技術レベルを表す数値であるFIFA レーティングが与えられます。FIFAの格付が高いほど、過去の試合の結果が良いことを示しており、2チームのFIFAの格付を考慮すると、どちらかのチームが現在の格付けに基づいて試合に勝つ確率を推定することが可能です。過去2回のワールドカップのFIFAレーティングは、2018年5月の男子FIFAランクと2019年3月の女子FIFAランクです。

この情報をもとに、1チームで終わるまでのラウンドシミュレーションを繰り返すことで、大会全体をシミュレーションすることができます。また、どのチームがトーナメントで優勝する可能性が高いかを推測するには、トーナメントを何度もシミュレートし (例:1000シミュレーション)、各チームがシミュレートしたトーナメントで何回優勝したかをカウントします。

1000回のシミュレーションは多いように見えるかもしれませんが、今日の計算能力をもってすれば、数ミリ秒のうちにこれらのシミュレーションを行うことができます。このラボの最後には、実行時間のトレードオフを考慮した上で、シミュレーションの回数を増やすことにどの程度の価値があるのかを実験してみます。

このLabの課題は、Pythonを使ってそれを実現することです。

始め方

VS Codeを開きます。

ターミナルウィンドウ内をクリックすることから始めて、それからcdを実行します。
その後プロンプトは次のようになっていることがわかります。

$

ターミナルウィンドウの内側をクリックし、次のように入力します。

wget https://cdn.cs50.net/2022/fall/labs/6/world-cup.zip

その後にEnterを押すと、world-cup.zipというZIPがあなたのCodespaceにダウンロードされます。wgetと次のURLの間にあるスペースや、その他の文字を見落とさないように注意してください。

次に

unzip world-cup.zip

を実行して、world-cupというフォルダを作成します。
ZIPファイルは不要になったため、

rm world-cup.zip

を実行し、プロンプトで “y “に続いてEnterで応答すると、ダウンロードしたZIPファイルが削除されます。

次に

cd world-cup

の後にEnterを押して、そのディレクトリに移動する（つまり、開く）。これでプロンプトは以下のようになります。

world-cup/ $

すべて成功した場合は、次のように実行します。

ls

次のファイルが表示されます。

answers.txt  2018m.csv  2019w.csv  tournament.py

もし問題が発生した場合は、もう一度同じ手順を踏んで、どこが間違っていたかを確認してください

理解を深める

まず、2018m.csvファイルを確認します。このファイルには、2018年男子ワールドカップのノックアウトラウンドの16チームと各チームの評価が含まれています。CSVファイルには2つの列があり、1つはチーム (チームの国名を表す) 、もう1つはレーティング (チームのレーティングを表す) です。

各ラウンドでどのチームが互いに対戦するかは、チームがリストされる順序によって決まります(例えば、第一ラウンドで、ウルグアイはポルトガルと対戦し、フランスはアルゼンチンと対戦します。次のラウンドで、ウルグアイ-ポルトガルの試合の勝者は、フランス-アルゼンチンの試合の勝者と対戦します)。したがって、このファイルに表示されるチームの順序は編集しないでください。

最終的にPythonでは、「チーム」と「格付」という2つの値を含む辞書として各チームを表すことができます。例えばウルグアイの場合、Pythonでは{"team": "Uruguay", "rating": 976}と表現したいでしょう。

次に、2019w.csvを見てみましょう。このファイルには、同じ形式で2019年女子ワールドカップのデータが含まれています。

tournament.pyを開いて、既にコードがいくらか書かれていることを確認してください。上にある変数Nは、実行するワールドカップシミュレーションの数を表します。この場合は1000です。

simulate_game関数は、2つのチームを入力として受け取り (各チームがチーム名とチームの格付を含む辞書であることを思い出してください) 、それらのチーム間のゲームをシミュレートします。最初のチームが勝つと、関数はTrueを返します。それ以外の場合はFalseを返します。

simulate_round関数は、チームのリスト (teamsという変数) を入力として受け取り、チームの各ペア間のゲームをシミュレートします。次に、この関数は、そのラウンドに勝ったすべてのチームのリストを返します。

main 関数では、まずlen(sys.argv) (コマンドライン引数の数) が2であることを確認します。コマンドライン引数を使用して、トーナメントシミュレーションの実行に使用するチームCSVファイルをPythonに指示します。次に、teams (最終的にはチームのリストとなります) と呼ばれるリストと、counts  (チーム名とそのチームがシミュレーションされたトーナメントで優勝した回数を関連付ける) と呼ばれる辞書を定義します。現時点ではどちらも空なので、どのように完成させるかはあなた次第です。

最後に、mainの最後に、シミュレーションで何回優勝したか (countsによって) の高い順にチームを並べ、それぞれのチームがワールドカップで優勝する確率をプリントします。

teamsとcountsを定義し、simulate_tournament関数を作成するのが今回の課題です。

実装の詳細

複数のトーナメントをシミュレートし、各チームの勝率を出力するように、tournament.pyの実装を完了します。

まずmainで、CSVファイルからプログラムのメモリにチームデータを読み込み、各チームをリストteamsに追加します。

  • 使用するファイルは、コマンドライン引数として指定されます。ファイルの名前にアクセスするには、sys.argv[1]を使用します。
  • open(filename)を使用してファイルを開くことができます。ここで、filenameはファイルの名前を格納する変数です。
  • ファイルfを取得したら、csv.DictReader(f) を使用して 「リーダー」 を作成できます。リーダーとは、Pythonでループしてファイルを1行ずつ読み取り、各行を辞書として扱うオブジェクトです。
  • デフォルトでは、ファイルから読み込まれるすべての値は文字列になります。そのため、まずチームのratingをintに変換してください (Pythonでint関数を使用してこれを行うことができます) 。
  • 最終的には、各チームの辞書をteamsに追加します。関数呼び出しteams.append(x)は、リストteamsにxを追加します。
  • 各チームは、チーム名teamと格付ratingを含む辞書でなければならないことを思い出してください。

次に、simulate_tournament関数を実装します。この関数は、チームのリストを入力として受け入れ、1つのチームが残るまでラウンドを繰り返しシミュレートします。この関数は、そのチームの名前を返します。

  • simulate_round関数を呼び出すことができます。simulate_round関数は、単一のラウンドをシミュレートし、チームのリストを入力として受け入れ、すべての勝者のリストを返します。
  • xがリストの場合、len(x) を使用してリストの長さを決定できます。
  • トーナメントのチーム数を想定するのではなく、2の累乗を想定してもいいでしょう。

最後にmain関数に戻り、N回トーナメントのシミュレーションを実行し、各チームが辞書countsで何回優勝したかを追跡します。

  • たとえば、ウルグアイが2トーナメントで優勝し、ポルトガルが3トーナメントで優勝したとすると、カウント辞書counts は{"Uruguay": 2, "Portugal": 3}になります。
  • simulate_tournamentを使用して各トーナメントをシミュレートし、勝者を決定します。
  • countsが辞書である場合、counts[team_name] = xのような構文は、team_nameに格納されたキーをxに格納された値に関連付けることを思い出してください。
  • Pythonでinキーワードを使用すると、その辞書にすでに特定のキーがあるかどうかをチェックできます。例えば、if "Portugal" in counts:は、「Portugal」が既に辞書countsに存在する値を持っているかどうかを調べます。

ウォークスルー

このビデオは、コースがまだコードを書くためにCS50 IDEを使用していたときに記録されたものです。インターフェイスはあなたのCodespaceと異なるように見えますが、2つの環境の動作はほぼ同じであるはずです

ヒント

  • ファイルを読み込むときは、filenameをファイル名、fileを変数として、この構文を使用すると便利です。
with open(filename) as file:
　　　　reader=csv.DictReader(file)
  • Pythonでリストの最後に追加するには、.append()関数を使用します。

解決方法がわかりませんか？

テスト

プログラムは、次の例に従って動作する必要があります。シミュレーションはそれぞれランダムであるため、出力は以下の例と完全には一致しません。

$ python tournament.py 2018m.csv
Belgium: 20.9% chance of winning
Brazil: 20.3% chance of winning
Portugal: 14.5% chance of winning
Spain: 13.6% chance of winning
Switzerland: 10.5% chance of winning
Argentina: 6.5% chance of winning
England: 3.7% chance of winning
France: 3.3% chance of winning
Denmark: 2.2% chance of winning
Croatia: 2.0% chance of winning
Colombia: 1.8% chance of winning
Sweden: 0.5% chance of winning
Uruguay: 0.1% chance of winning
Mexico: 0.1% chance of winning
$ python tournament.py 2019w.csv
Germany: 17.1% chance of winning
United States: 14.8% chance of winning
England: 14.0% chance of winning
France: 9.2% chance of winning
Canada: 8.5% chance of winning
Japan: 7.1% chance of winning
Australia: 6.8% chance of winning
Netherlands: 5.4% chance of winning
Sweden: 3.9% chance of winning
Italy: 3.0% chance of winning
Norway: 2.9% chance of winning
Brazil: 2.9% chance of winning
Spain: 2.2% chance of winning
China PR: 2.1% chance of winning
Nigeria: 0.1% chance of winning
  • 2018年と2019年のワールドカップで実際に何が起こったのか不思議に思うかもしれません。男子ではフランスが決勝でクロアチアに勝ちました。ベルギーはイギリスを破って3位になりました。女子ではアメリカが決勝でオランダに勝ちました。イングランドはスウェーデンが破って3位に入りました。

シミュレーション数

コードが正しいことを確認したら、ファイルの先頭にある定数Nの値をいじって、トーナメントのシミュレーションの回数を調整しましょう。トーナメントのシミュレーションの回数を増やせば、より正確な予測が可能になりますが、その分時間がかかります。

コマンドラインでの実行の前にtimeを付けることで、プログラムの時間を計ることができます。
例えば，N を 1000 (デフォルト) に設定した場合

time python tournament.py 2018m.csv

または

time python tournament.py 2019w.csv

とすれば次のように出力されるはずです。

real    0m0.037s
user    0m0.028s
sys     0m0.008s

ただし、時間は前後する可能性があります。

realという指標に注目してください。これは、tournament.pyの実行にかかった合計時間です。分と秒の単位で、1000分の1秒の精度で表示されることに注意してください。

answers.txtに、tournament.pyがシミュレーションに要した時間を記録してください

  • 10（十）トーナメント
  • 100（百）トーナメント
  • 1000（千）トーナメント
  • 10000（１万）トーナメント
  • 100000（１０万）トーナメント
  • 1000000（１００万）トーナメント

Nを調整するたびに、0m0.000sフォーマットで、answer.txtの適切なTODOに実時間を記録してください。各シナリオで時間を計った後、与えられたTODOを上書きして、2つのフォローアップの質問に答えてください。

  • シミュレーションの回数を増やすにつれて、どのような予測が誤っていることが判明しましたか
  • あなたのプログラムが使用する計算時間1秒ごとに料金を請求されるとします。何回シミュレーションをしたら、その予測は「十分」だと言えますか？

正しい書式のanswers.txt

Times:

10 simulations: 0m0.028s
100 simulations: 0m0.030s
1000 simulations: 0m0.041s
10000 simulations: 0m0.139s
100000 simulations: 0m1.031s
1000000 simulations: 0m11.961s

Questions:

Which predictions, if any, proved incorrect as you increased the number of simulations?:

シミュレーションの数が少ないと...

Suppose you’re charged a fee for each second of compute time your program uses.
After how many simulations would you call the predictions "good enough"?:

...くらいから予測が安定したような気がします。

コードのテスト方法

check50を使用して以下を実行し、コードの正確さを評価してください。ただし、コンパイルとテストは必ず自分で行ってください。

check50 cs50/labs/2023/x/worldcup

以下を実行し、style50を使用してコードのスタイルを評価します。

style50 tournament.py

提出方法

ターミナルで、以下のコマンドを実行して提出してください。

submit50 cs50/labs/2023/x/worldcup