この記事はあくあたん工房Advent Callenderの12日目の記事です．
###はじめに
torisiura9です．あくあたんに洗脳されそふらぼことソフトウェア工学研究室でドクターをしています．
D進から逃げるな．
あくあたん工房は有能星人だけが入れるエリート集団なので残念ながら僕は会員ではないのですが，部室を持たないあくあたん工房がそふらぼの学生部屋を不当に占拠していることに対して罪の意識に耐えかねた首魁の二人がそふらぼの軍門に下ったことで優秀な手駒を手に入れた，という立ち位置の人です．常々ラボサーバの管理をしてもらったり珈琲を淹れてもらっているお返しに一記事だけ寄稿したいと思います．
###一乗寺って？
ここからは書きやすさ優先で常体で書く．
我らが京都工芸繊維大学松ヶ崎キャンパスのある松ヶ崎から川を一本隔ててわずか数百メートルのところに一乗寺という地区がある．そこでは十数軒ものラーメン屋が腕を競い合うように軒を連ね，最近ではちょっとした観光地のようにもなっている．
不健康の権化である大学生の主食は麺と塩と脂であるので，京都工芸繊維大学の学生は部活帰りに，試験終わりのご褒美に，課題前の気合入れにと，多かれ少なかれ一乗寺のお世話になっている．外食にしてはリーズナブルだし，友達や先輩後輩を誘っておしゃべりするのも悪くない．
特にその恩恵を受けているのは近隣に住まう下宿生で，生活スキルの無さから自炊を諦め，またご飯を作りに来てくれる可愛い彼女や後輩を持たない彼らを一乗寺は暖かく迎え入れてくれている．
ちょっとだけ紹介
押しも押されぬ名店と化した極鶏
天天有の優しいスープが体に染み込む
高安は唐揚げが主役という声もある
お世話になっております．
ところで，一乗寺に入り浸りラーメンばかり食べていると頭がバグってくる．次のような経験は無いだろうか？
- 食べ終わった後で「よく考えると今日はこの店の気分じゃなかったな……」とぼんやり後悔する．
- 微妙だったはずの店に「今日は大丈夫やろ」とまた入ってしまう．（多くの場合大丈夫ではない）
- 前を通ろうとしただけなのに気づくと店内にいる．
このように，確信を持てずに食べてしまったラーメンは深い満足に繋がらない．これら「空振り」をしてしまう原因はすべて我々の計画不足に他ならない．我々が卒業までに食べられるラーメンには限りがあるのだ．一食一食により重きを置き，生活を研ぎ澄まさなければならない．漫然と呆けていてはならない．
##最適化する
というわけで、一乗寺から得られる最高経験を最適化してみる。最高の2019年1月の一乗寺計画を立てるぞ。
###満足度の総和を最大化する
とりあえず一乗寺のラーメン屋を書き出してみる．全部はさすがにあれなので，代表的な店を15軒挙げる．あといつも頼むメニューも挙げておく．多分年始は営業日が変則的になると思うがここでは無視する。
| 店名 | メニュー | 定休日 | 昼営業 |
|---|---|---|---|
| 天天有 | 中華そば煮卵入り | 水曜 | 無 |
| 極鶏 | 黒だく | 月曜 | |
| 豚人 | とこ塩とんこつ | ||
| 高安 | からあげ定食 | ||
| びし屋 | 和え麺 | ||
| 夕日のキラメキ | 直太朗（大） | ||
| 重厚軍団 | Jまぜそば(にんにく) | 金のみ無 | |
| 夢を語れ | 汁なし | 月曜 | |
| 池田屋 | ラーメン（プチ） | ||
| 珍遊 | 中華そば（大） | ||
| 恵那く | 得製つけ麺 | 火曜 | |
| あらじん | 豚骨味噌ラーメン | 火曜 | |
| 一乗寺ブギー | つけそば | ||
| つるかめ | 魚介醤油ラーメン | ||
| 天下一品総本店 | こってり | 木曜 |
京都二郎が無い？ 京都ではよそから来て五年も経ってない店はまだまだ「お客様」やさかい……
次に満足度を10点満点でふってみる．万が一にもこれを見た店主達から特定されて出禁を食らいたくないのでここでは乱数を使う．次のようになった．
| 店名 | メニュー |
|---|---|
| 天天有 | 6 |
| 極鶏 | 4 |
| 豚人 | 4 |
| 高安 | 5 |
| びし屋 | 2 |
| 夕日のキラメキ | 3 |
| 重厚軍団 | 10 |
| 夢を語れ | 5 |
| 池田屋 | 2 |
| 珍遊 | 2 |
| 恵那く | 2 |
| あらじん | 4 |
| 一乗寺ブギー | 1 |
| つるかめ | 3 |
| 天下一品総本店 | 3 |
だいぶ下に偏ってしまったが，これはこれで使いやすそうなのでこのままいく．じっさい軍団のまぜそばはめちゃくちゃうまい．
かてへん
さて，満足度が判明したので，営業日の制約を満たしながら得られる満足度の総和を最大化するように来月の計画を立ててみよう．31日間の昼食と夕食で合計62回という食事回数が制約として与えられ，組み合わせ最適問題として解くことができる．
結果は次のようになった．
Date Goto Reward Sum_Rewards
0 1/1 gundan +10.0 10.0
1 1/1 gundan +10.0 20.0
2 1/2 gundan +10.0 30.0
3 1/2 gundan +10.0 40.0
4 1/3 gundan +10.0 50.0
5 1/3 gundan +10.0 60.0
6 1/4 gokkei +5.0 65.0
7 1/4 gundan +10.0 75.0
8 1/5 gundan +10.0 85.0
9 1/5 gundan +10.0 95.0
10 1/6 gundan +10.0 105.0
11 1/6 gundan +10.0 115.0
12 1/7 gundan +10.0 125.0
13 1/7 gundan +10.0 135.0
14 1/8 gundan +10.0 145.0
15 1/8 gundan +10.0 155.0
16 1/9 gundan +10.0 165.0
17 1/9 gundan +10.0 175.0
18 1/10 gundan +10.0 185.0
19 1/10 gundan +10.0 195.0
20 1/11 gokkei +5.0 200.0
21 1/11 gundan +10.0 210.0
22 1/12 gundan +10.0 220.0
23 1/12 gundan +10.0 230.0
24 1/13 gundan +10.0 240.0
25 1/13 gundan +10.0 250.0
26 1/14 gundan +10.0 260.0
27 1/14 gundan +10.0 270.0
28 1/15 gundan +10.0 280.0
29 1/15 gundan +10.0 290.0
30 1/16 gundan +10.0 300.0
31 1/16 gundan +10.0 310.0
32 1/17 gundan +10.0 320.0
33 1/17 gundan +10.0 330.0
34 1/18 gokkei +5.0 335.0
35 1/18 gundan +10.0 345.0
36 1/19 gundan +10.0 355.0
37 1/19 gundan +10.0 365.0
38 1/20 gundan +10.0 375.0
39 1/20 gundan +10.0 385.0
40 1/21 gundan +10.0 395.0
41 1/21 gundan +10.0 405.0
42 1/22 gundan +10.0 415.0
43 1/22 gundan +10.0 425.0
44 1/23 gundan +10.0 435.0
45 1/23 gundan +10.0 445.0
46 1/24 gundan +10.0 455.0
47 1/24 gundan +10.0 465.0
48 1/25 gokkei +5.0 470.0
49 1/25 gundan +10.0 480.0
50 1/26 gundan +10.0 490.0
51 1/26 gundan +10.0 500.0
52 1/27 gundan +10.0 510.0
53 1/27 gundan +10.0 520.0
54 1/28 gundan +10.0 530.0
55 1/28 gundan +10.0 540.0
56 1/29 gundan +10.0 550.0
57 1/29 gundan +10.0 560.0
58 1/30 gundan +10.0 570.0
59 1/30 gundan +10.0 580.0
60 1/31 gundan +10.0 590.0
61 1/31 gundan +10.0 600.0
Sum_Rewards = 600.0
定休日である金曜の昼以外は全て軍団に通うことになってしまった．言われてみればそういうのもありかもしれない．
###ライフ制を導入する
とはいえ流石に毎食ラーメンはしんどい．栄養も偏るし，高血圧高血糖で卒業前に死にたくはない．
そこでライフ制を導入する．初期ライフは9あるとする．これは上限でもある．ラーメンを1回食べるごとにライフが1減少し，0になると死ぬ．死んでしまうと累計満足度は0になってしまうため，死ぬのは避けたい．
食事の際にラーメンを休憩し，代わりに生野菜を食べることでライフが3回復することにする．生野菜の満足度は0だが，ライフが回復しただけ将来的に多くのラーメンを食べられるので行動としての価値は高い．
これで少しは戦略的な要素が出てきたと思う．休憩を挟むことによって寿命を延ばし，最大の満足度を得るようにふるまうことが期待される．これを最適化すると次のようになる．
Date Goto life Reward Sum_Rewards
0 1/1 gundan 8 +10.0 10.0
1 1/1 gundan 7 +10.0 20.0
2 1/2 gundan 6 +10.0 30.0
3 1/2 gundan 5 +10.0 40.0
4 1/3 gundan 4 +10.0 50.0
5 1/3 gundan 3 +10.0 60.0
6 1/4 REST 6 +0.0 60.0
7 1/4 gundan 5 +10.0 70.0
8 1/5 gundan 4 +10.0 80.0
9 1/5 gundan 3 +10.0 90.0
10 1/6 gundan 2 +10.0 100.0
11 1/6 gundan 1 +10.0 110.0
12 1/7 REST 4 +0.0 110.0
13 1/7 gundan 3 +10.0 120.0
14 1/8 gundan 2 +10.0 130.0
15 1/8 gundan 1 +10.0 140.0
16 1/9 REST 4 +0.0 140.0
17 1/9 gundan 3 +10.0 150.0
18 1/10 gundan 2 +10.0 160.0
19 1/10 gundan 1 +10.0 170.0
20 1/11 REST 4 +0.0 170.0
21 1/11 gundan 3 +10.0 180.0
22 1/12 gundan 2 +10.0 190.0
23 1/12 gundan 1 +10.0 200.0
24 1/13 REST 4 +0.0 200.0
25 1/13 gundan 3 +10.0 210.0
26 1/14 gundan 2 +10.0 220.0
27 1/14 gundan 1 +10.0 230.0
28 1/15 REST 4 +0.0 230.0
29 1/15 gundan 3 +10.0 240.0
30 1/16 gundan 2 +10.0 250.0
31 1/16 gundan 1 +10.0 260.0
32 1/17 REST 4 +0.0 260.0
33 1/17 gundan 3 +10.0 270.0
34 1/18 REST 6 +0.0 270.0
35 1/18 gundan 5 +10.0 280.0
36 1/19 gundan 4 +10.0 290.0
37 1/19 gundan 3 +10.0 300.0
38 1/20 gundan 2 +10.0 310.0
39 1/20 gundan 1 +10.0 320.0
40 1/21 REST 4 +0.0 320.0
41 1/21 gundan 3 +10.0 330.0
42 1/22 gundan 2 +10.0 340.0
43 1/22 gundan 1 +10.0 350.0
44 1/23 REST 4 +0.0 350.0
45 1/23 gundan 3 +10.0 360.0
46 1/24 gundan 2 +10.0 370.0
47 1/24 gundan 1 +10.0 380.0
48 1/25 REST 4 +0.0 380.0
49 1/25 gundan 3 +10.0 390.0
50 1/26 gundan 2 +10.0 400.0
51 1/26 gundan 1 +10.0 410.0
52 1/27 REST 4 +0.0 410.0
53 1/27 gundan 3 +10.0 420.0
54 1/28 gundan 2 +10.0 430.0
55 1/28 gundan 1 +10.0 440.0
56 1/29 REST 4 +0.0 440.0
57 1/29 gundan 3 +10.0 450.0
58 1/30 gundan 2 +10.0 460.0
59 1/30 gundan 1 +10.0 470.0
60 1/31 REST 4 +0.0 470.0
61 1/31 gundan 3 +10.0 480.0
Sum_Rewards = 480.0
金曜昼またはライフが1になった時だけ休憩し，他は全て軍団に行く計画ができた．間違ってはいないが……
###飽きシステムを導入する
軍団の満足度が圧倒的すぎることで否が応でも軍団に行かされることになるが，これが最適解かと問われると現実的な感覚からは疑問の余地がある．ではなぜ毎日軍団に行かないかと言えば，単純に飽きるからだろう．なのでこの「飽き」を設定に組み込んでみる．
どこかの店でラーメンを食べると，次の食事ではその店の満足度が現在の満足度の半分になる．また行かなかった他のラーメン屋の満足度は1回復する．休憩して生野菜を食べるともちろん全ての店の満足度が1回復する．ただし満足度の初期値を超えることはない．
また生野菜は飽きないとしておく．まあ実際は飽きてるのかもしれないが元々が満足度0なので変動しようがない．
例えば，初日の昼に軍団に行くと軍団の満足度が10から5に下がる．次の夕食では満足度6の天天有が軍団の満足度5にまさっているため天天有を選ぶことにする．すると天天有の満足度は3に下がり，いっぽうで軍団の満足度は1回復して6になる……とこういう感じだ．なんとなくeligibility traceっぽい．（ほんまか？）
飽きシステムが加わったことで戦略性がさらに増し，より実感に即した結果が得られるようになったと思う．ただし最適化するにあたっては，継時的な要素が加わったため単純な組み合わせ最適問題として扱えなくなった．そこで探索的に解いてみることにする．
とはいえ全探索しようとすると16の62乗通りとかいうドヤバい数になってしまうので，n手先だけを見て，その中で最大の満足度が得られる選択肢を選んでいく方法をとってみる．
- n=1
$ python Search1JoG.py -n 1
Date Goto Life Reward Sum_Rewards
0 1/1 gundan 8 +10.0 10.000000
1 1/1 takayasu 7 +5.0 15.000000
2 1/2 gundan 6 +6.0 21.000000
3 1/2 yume-kata 5 +5.0 26.000000
4 1/3 tentenyu 4 +6.0 32.000000
5 1/3 takayasu 3 +5.0 37.000000
6 1/4 gundan 2 +6.0 43.000000
7 1/4 yume-kata 1 +5.0 48.000000
8 1/5 REST 4 +0.0 48.000000
9 1/5 takayasu 3 +5.0 53.000000
10 1/6 tentenyu 2 +6.0 59.000000
11 1/6 gundan 1 +7.0 66.000000
12 1/7 REST 4 +0.0 66.000000
13 1/7 takayasu 3 +5.0 71.000000
14 1/8 tentenyu 2 +6.0 77.000000
15 1/8 gundan 1 +6.5 83.500000
16 1/9 REST 4 +0.0 83.500000
17 1/9 takayasu 3 +5.0 88.500000
18 1/10 tentenyu 2 +6.0 94.500000
19 1/10 gundan 1 +6.25 100.750000
20 1/11 REST 4 +0.0 100.750000
21 1/11 takayasu 3 +5.0 105.750000
22 1/12 tentenyu 2 +6.0 111.750000
23 1/12 gundan 1 +6.125 117.875000
24 1/13 REST 4 +0.0 117.875000
25 1/13 takayasu 3 +5.0 122.875000
26 1/14 tentenyu 2 +6.0 128.875000
27 1/14 gundan 1 +6.0625 134.937500
28 1/15 REST 4 +0.0 134.937500
29 1/15 takayasu 3 +5.0 139.937500
30 1/16 gundan 2 +5.03125 144.968750
31 1/16 yume-kata 1 +5.0 149.968750
32 1/17 REST 4 +0.0 149.968750
33 1/17 takayasu 3 +5.0 154.968750
34 1/18 tentenyu 2 +6.0 160.968750
35 1/18 yume-kata 1 +5.0 165.968750
36 1/19 REST 4 +0.0 165.968750
37 1/19 gundan 3 +8.515625 174.484375
38 1/20 tentenyu 2 +6.0 180.484375
39 1/20 gundan 1 +5.2578125 185.742188
40 1/21 REST 4 +0.0 185.742188
41 1/21 takayasu 3 +5.0 190.742188
42 1/22 tentenyu 2 +6.0 196.742188
43 1/22 gundan 1 +5.62890625 202.371094
44 1/23 REST 4 +0.0 202.371094
45 1/23 takayasu 3 +5.0 207.371094
46 1/24 tentenyu 2 +6.0 213.371094
47 1/24 gundan 1 +5.814453125 219.185547
48 1/25 REST 4 +0.0 219.185547
49 1/25 takayasu 3 +5.0 224.185547
50 1/26 tentenyu 2 +6.0 230.185547
51 1/26 gundan 1 +5.9072265625 236.092773
52 1/27 REST 4 +0.0 236.092773
53 1/27 takayasu 3 +5.0 241.092773
54 1/28 tentenyu 2 +6.0 247.092773
55 1/28 gundan 1 +5.95361328125 253.046387
56 1/29 REST 4 +0.0 253.046387
57 1/29 takayasu 3 +5.0 258.046387
58 1/30 yume-kata 2 +5.0 263.046387
59 1/30 gundan 1 +5.976806640625 269.023193
60 1/31 REST 4 +0.0 269.023193
61 1/31 takayasu 3 +5.0 274.023193
Sum_Rewards = 274.023193359375
- n=2
$ python Search1JoG.py -n 2
Date Goto Life Reward Sum_Rewards
0 1/1 tentenyu 8 +6.0 6.0
1 1/1 takayasu 7 +5.0 11.0
2 1/2 gundan 6 +10.0 21.0
3 1/2 yume-kata 5 +5.0 26.0
4 1/3 tentenyu 4 +6.0 32.0
5 1/3 takayasu 3 +5.0 37.0
6 1/4 gundan 2 +8.0 45.0
7 1/4 REST 5 +0.0 45.0
8 1/5 tentenyu 4 +6.0 51.0
9 1/5 takayasu 3 +5.0 56.0
10 1/6 yume-kata 2 +5.0 61.0
11 1/6 REST 5 +0.0 61.0
12 1/7 tentenyu 4 +6.0 67.0
13 1/7 takayasu 3 +5.0 72.0
14 1/8 gundan 2 +10.0 82.0
15 1/8 REST 5 +0.0 82.0
16 1/9 yume-kata 4 +5.0 87.0
17 1/9 takayasu 3 +5.0 92.0
18 1/10 tentenyu 2 +6.0 98.0
19 1/10 REST 5 +0.0 98.0
20 1/11 gundan 4 +10.0 108.0
21 1/11 takayasu 3 +5.0 113.0
22 1/12 tentenyu 2 +6.0 119.0
23 1/12 REST 5 +0.0 119.0
24 1/13 yume-kata 4 +5.0 124.0
25 1/13 takayasu 3 +5.0 129.0
26 1/14 tentenyu 2 +6.0 135.0
27 1/14 REST 5 +0.0 135.0
28 1/15 gundan 4 +10.0 145.0
29 1/15 takayasu 3 +5.0 150.0
30 1/16 yume-kata 2 +5.0 155.0
31 1/16 REST 5 +0.0 155.0
32 1/17 tentenyu 4 +6.0 161.0
33 1/17 takayasu 3 +5.0 166.0
34 1/18 gundan 2 +10.0 176.0
35 1/18 REST 5 +0.0 176.0
36 1/19 tentenyu 4 +6.0 182.0
37 1/19 takayasu 3 +5.0 187.0
38 1/20 yume-kata 2 +5.0 192.0
39 1/20 REST 5 +0.0 192.0
40 1/21 tentenyu 4 +6.0 198.0
41 1/21 takayasu 3 +5.0 203.0
42 1/22 gundan 2 +10.0 213.0
43 1/22 REST 5 +0.0 213.0
44 1/23 yume-kata 4 +5.0 218.0
45 1/23 takayasu 3 +5.0 223.0
46 1/24 tentenyu 2 +6.0 229.0
47 1/24 REST 5 +0.0 229.0
48 1/25 gundan 4 +10.0 239.0
49 1/25 takayasu 3 +5.0 244.0
50 1/26 tentenyu 2 +6.0 250.0
51 1/26 REST 5 +0.0 250.0
52 1/27 yume-kata 4 +5.0 255.0
53 1/27 takayasu 3 +5.0 260.0
54 1/28 tentenyu 2 +6.0 266.0
55 1/28 REST 5 +0.0 266.0
56 1/29 gundan 4 +10.0 276.0
57 1/29 takayasu 3 +5.0 281.0
58 1/30 yume-kata 2 +5.0 286.0
59 1/30 REST 5 +0.0 286.0
60 1/31 tentenyu 4 +6.0 292.0
61 1/31 gundan 3 +9.0 301.0
Sum_Rewards = 301.0
- n=3
$ python Search1JoG.py -n 3
Date Goto Life Reward Sum_Rewards
0 1/1 tentenyu 8 +6.0 6.0
1 1/1 gundan 7 +10.0 16.0
2 1/2 takayasu 6 +5.0 21.0
3 1/2 gokkei 5 +4.0 25.0
4 1/3 tentenyu 4 +6.0 31.0
5 1/3 yume-kata 3 +5.0 36.0
6 1/4 gundan 2 +9.0 45.0
7 1/4 REST 5 +0.0 45.0
8 1/5 tentenyu 4 +6.0 51.0
9 1/5 takayasu 3 +5.0 56.0
10 1/6 REST 6 +0.0 56.0
11 1/6 yume-kata 5 +5.0 61.0
12 1/7 tentenyu 4 +6.0 67.0
13 1/7 gundan 3 +10.0 77.0
14 1/8 REST 6 +0.0 77.0
15 1/8 takayasu 5 +5.0 82.0
16 1/9 gokkei 4 +4.0 86.0
17 1/9 yume-kata 3 +5.0 91.0
18 1/10 tentenyu 2 +6.0 97.0
19 1/10 REST 5 +0.0 97.0
20 1/11 gundan 4 +10.0 107.0
21 1/11 gokkei 3 +4.0 111.0
22 1/12 tentenyu 2 +6.0 117.0
23 1/12 REST 5 +0.0 117.0
24 1/13 takayasu 4 +5.0 122.0
25 1/13 yume-kata 3 +5.0 127.0
26 1/14 tentenyu 2 +6.0 133.0
27 1/14 REST 5 +0.0 133.0
28 1/15 gundan 4 +10.0 143.0
29 1/15 takayasu 3 +5.0 148.0
30 1/16 REST 6 +0.0 148.0
31 1/16 yume-kata 5 +5.0 153.0
32 1/17 tentenyu 4 +6.0 159.0
33 1/17 takayasu 3 +5.0 164.0
34 1/18 gundan 2 +10.0 174.0
35 1/18 REST 5 +0.0 174.0
36 1/19 tentenyu 4 +6.0 180.0
37 1/19 takayasu 3 +5.0 185.0
38 1/20 REST 6 +0.0 185.0
39 1/20 yume-kata 5 +5.0 190.0
40 1/21 tentenyu 4 +6.0 196.0
41 1/21 gundan 3 +10.0 206.0
42 1/22 REST 6 +0.0 206.0
43 1/22 takayasu 5 +5.0 211.0
44 1/23 gokkei 4 +4.0 215.0
45 1/23 yume-kata 3 +5.0 220.0
46 1/24 tentenyu 2 +6.0 226.0
47 1/24 REST 5 +0.0 226.0
48 1/25 gundan 4 +10.0 236.0
49 1/25 gokkei 3 +4.0 240.0
50 1/26 tentenyu 2 +6.0 246.0
51 1/26 REST 5 +0.0 246.0
52 1/27 takayasu 4 +5.0 251.0
53 1/27 yume-kata 3 +5.0 256.0
54 1/28 tentenyu 2 +6.0 262.0
55 1/28 REST 5 +0.0 262.0
56 1/29 gundan 4 +10.0 272.0
57 1/29 takayasu 3 +5.0 277.0
58 1/30 REST 6 +0.0 277.0
59 1/30 yume-kata 5 +5.0 282.0
60 1/31 tentenyu 4 +6.0 288.0
61 1/31 gundan 3 +9.0 297.0
Sum_Rewards = 297.0
- n=4
$ python Search1JoG.py -n 4
Date Goto Life Reward Sum_Rewards
0 1/1 tentenyu 8 +6.0 6.00
1 1/1 gundan 7 +10.0 16.00
2 1/2 gokkei 6 +4.0 20.00
3 1/2 butanchu 5 +4.0 24.00
4 1/3 tentenyu 4 +6.0 30.00
5 1/3 REST 7 +0.0 30.00
6 1/4 gundan 6 +9.0 39.00
7 1/4 takayasu 5 +5.0 44.00
8 1/5 tentenyu 4 +6.0 50.00
9 1/5 REST 7 +0.0 50.00
10 1/6 yume-kata 6 +5.0 55.00
11 1/6 gokkei 5 +4.0 59.00
12 1/7 tentenyu 4 +6.0 65.00
13 1/7 gundan 3 +10.0 75.00
14 1/8 REST 6 +0.0 75.00
15 1/8 gokkei 5 +4.0 79.00
16 1/9 butanchu 4 +4.0 83.00
17 1/9 REST 7 +0.0 83.00
18 1/10 tentenyu 6 +6.0 89.00
19 1/10 gundan 5 +10.0 99.00
20 1/11 gundan 4 +5.0 104.00
21 1/11 takayasu 3 +5.0 109.00
22 1/12 tentenyu 2 +6.0 115.00
23 1/12 REST 5 +0.0 115.00
24 1/13 tentenyu 4 +4.0 119.00
25 1/13 yume-kata 3 +5.0 124.00
26 1/14 REST 6 +0.0 124.00
27 1/14 butanchu 5 +4.0 128.00
28 1/15 gundan 4 +9.5 137.50
29 1/15 REST 7 +0.0 137.50
30 1/16 gokkei 6 +4.0 141.50
31 1/16 butanchu 5 +4.0 145.50
32 1/17 tentenyu 4 +6.0 151.50
33 1/17 REST 7 +0.0 151.50
34 1/18 gundan 6 +9.75 161.25
35 1/18 takayasu 5 +5.0 166.25
36 1/19 tentenyu 4 +6.0 172.25
37 1/19 REST 7 +0.0 172.25
38 1/20 yume-kata 6 +5.0 177.25
39 1/20 gokkei 5 +4.0 181.25
40 1/21 tentenyu 4 +6.0 187.25
41 1/21 gundan 3 +10.0 197.25
42 1/22 REST 6 +0.0 197.25
43 1/22 gokkei 5 +4.0 201.25
44 1/23 butanchu 4 +4.0 205.25
45 1/23 REST 7 +0.0 205.25
46 1/24 tentenyu 6 +6.0 211.25
47 1/24 gundan 5 +10.0 221.25
48 1/25 gundan 4 +5.0 226.25
49 1/25 takayasu 3 +5.0 231.25
50 1/26 tentenyu 2 +6.0 237.25
51 1/26 REST 5 +0.0 237.25
52 1/27 tentenyu 4 +4.0 241.25
53 1/27 yume-kata 3 +5.0 246.25
54 1/28 REST 6 +0.0 246.25
55 1/28 butanchu 5 +4.0 250.25
56 1/29 gundan 4 +9.5 259.75
57 1/29 REST 7 +0.0 259.75
58 1/30 gokkei 6 +4.0 263.75
59 1/30 takayasu 5 +5.0 268.75
60 1/31 tentenyu 4 +6.0 274.75
61 1/31 gundan 3 +8.75 283.50
Sum_Rewards = 283.5
3手読み，4手読みだと2手読みに比べて満足度の総和が下がってしまうのが不思議だ．死が視界に入ると臆病になってしまうのだろうか．それか単に実装が間違ってるかもしれない．公開前日にわちゃわちゃやってるので……
まあ2手読みで最適化された動きを見ても特段変なことをしているようには見えないので，暫定的にこれを「最適な一乗寺の通い方」として決定したいと思う．この計画表通りにラーメン屋に通うことで最大の満足度を得られることが保証されるというわけだ．
###経験による最適化を目指す
待て待て，確かに最適化はされたが，ルールを全部知っている上で最適化するのはマッチポンプな気がしないでもない．一乗寺の全ての店の満足度が正確に分かっている学生がどれだけいるだろう？ 自分が何回連続でラーメンを食べると死ぬか知っているだろうか？ 一乗寺初心者であるKIT一回生でもちゃんと最適化できるすべを知っておきたい．
強化学習を使えば経験的にルールを学習し，行動を最適化することができる．
強化学習とは機械学習の一種だ．機械学習には大雑把に分けて次の種類がある．
- 教師あり学習 (Supervised Learning)
- 教師なし学習 (Unsupervised Learning)
- 強化学習 (Reinforcement Learning)
教師あり学習は与えられたラベル付きの入力データと出力データの組から学習を行う．教師なし学習はラベルのない入力データに構造を見出してラベルをつけるなどする．
強化学習の仕組みは少し独特で，エージェントがある状態で何らかの行動を起こすと環境から報酬が与えられ，次の状態に移る．エージェントは与えられた報酬によって，行動選択基準を更新していく．強化学習の目的は，経験を繰り返すことによって累計報酬を最大化させるような行動選択基準を獲得することだ．
今回の一乗寺最適化問題に翻訳すると，エージェント(agent)が学生，環境(environment)が一乗寺，行動(action)はどのラーメン屋に行くかor休憩するかを決めること，報酬(reward)はラーメンの満足度となる．状態(state)についてはおいおい考えていく．
モデルが分かっていないという前提なので，Model-Free型の学習法を選ぶ．とりあえず有名どころのQ学習にしておく．Q学習は，各状態において各行動を取った場合の累計報酬の期待値と対応したQ値というものをそれぞれ持ち，エピソード毎に得られた報酬によってQ値を更新していく．エージェントは基本的にはQ値の一番高い行動を選択する．
これはQ学習に限らない話だが，その時点でベストな行動ばかりをエージェントが取っていると他にもっといい行動があっても見逃してしまう．たまには今のところ良くなさそうな選択肢も試してみたい．そこで使われるのがε-greedyという戦法で，確率εを定めておき，確率εで最善でない行動を選択するというものだ．例えばQ学習でε=0.1と設定すると，ターン毎に，90%の確率でQ値に従って最善の行動を選び，10%の確率で最善でない行動をランダムに選ぶことになる．これによって多様性を獲得し，局所解に陥ることを回避する．
####実装
さっそく実装していく．
状態については，ライフのみの10状態と日程のみの62状態をそれぞれ試したみたが上手くいかなかったので，両方合わせて<日程，ライフ>を表す合計620状態を使用することにした．
つまり，例えば<1月10日，ライフ4>という状態に対してそれぞれの行動の優先度(Q値)を考えていくことになる．
実装は結局次のようになった．
import numpy as np
max_number_step = 62
num_episodes = 100000
initial_life = 9
actions = ["REST", "tentenyu", "gokkei", "butanchu", "takayasu", "bisiya", "kirameki", "gundan", "yume-kata", "ikedaya", "chin-yu", "enaku", "arajin", "boogie", "tsurukame", "ten-ichi"]
q_table = np.random.uniform(0,1,(630,16)) #Q値の初期値 乱数で埋めておく
initial_point = [0,6,4,4,5,2,3,10,5,2,2,2,4,1,3,3] #満足度の初期値
#営業日の判定に使うフィルター
week_filter = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1],
[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
#functions =======================================
#次の行動を決定する
def get_action(next_state, q_table):
#ε-greedyの部分
epsilon=0.01
if epsilon<np.random.uniform(0,1):
next_action=np.argmax(q_table[next_state])
else:
next_action=np.random.randint(n_ramen)
return next_action
#Q値を更新する
def update_Qtable(q_table,state,action,reward,next_state):
gamma=0.99 #将来価値のパラメータ
alpha=0.5 #学習率
q_table[state,action]=(1-alpha)*q_table[state,action]+\
alpha*(reward+gamma*max(q_table[next_state]))
return q_table
#飽きによる満足度の更新
def update_Ptable(point_table, action, Winitial_point):
next_point_table = [min(p+1,i) for p,i in zip(point_table, Winitial_point)]
next_point_table[action] = point_table[action]/2
return next_point_table
#次状態でのライフを求める
def get_life(life, action):
if action == 0:
next_life = min(initial_life, life+3)
else:
next_life = life - 1
return next_life
#行動に応じて営業日を考慮した満足度を返す
def get_reward(action, point_table,t):
day = int(t/2)
weekday = (day+2)%7
filtered_point_table = np.array(point_table) * np.array(week_filter[weekday])
if t%2: filtered_point_table[1]=0
if t%2 and weekday == 5: filtered_point_table[7]=0
return filtered_point_table[action]
#main routine ========================================
for episode in range(num_episodes): #エピソード毎
#初期パラメータ
life = initial_life
action = np.argmax(q_table[life])
point_table = initial_point
reward = 0
for t in range(max_number_step): #食事毎
next_life = get_life(life, action)
reward = reward + get_reward(action, point_table, t)
state = t*10 + life
next_state = (t+1)*10 + next_life
if next_life == 0:
reward = 0
q_table = update_Qtable(q_table,state,action,reward,next_state)
point_table = update_Ptable(point_table, action, weighted_initial_point)
action=get_action(next_state, q_table)
state = next_state
life = next_life
if life == 0:
break
テスト出力の類は省略している．
状態(state)の表現が雑なので全くアクセスしないQ値テーブルが発生してしまったが動作に影響はないはず．
学習用エピソードは10万回とした．
####結果
Q学習が導き出した一乗寺計画を見る前に，まず学習の様子を見てみよう．
まず上のグラフはエージェントがいつ死んだかをエピソード毎に表している．序盤のうちは連続でラーメンを食べ過ぎてすぐ死んでいるが，だんだんと寿命が延びていき，一万回試行したあたりで生きて2月を迎えられるようになっている．ただその後もε-greedyのせいでライフが1なのに我慢できずにラーメンを食べてしまい，よく死んでしまっている．結局，10万回のうち18556回は死んでしまった．
次に，上のグラフは得られた累計満足度をエピソード毎に表したものである．序盤は死んでしまうので累計満足度は0だが，生き残る方法を見つけてからは満足度がどんどん上がっていっているのが分かる．ただ250程度で頭打ちになり，たまに大きく沈みながら200〜250あたりの満足度で収束しているように見える．エピソード数を増やしてもあまり意味はないっぽい．学習中のハイスコアは258.125だった．
結局，10万回死に覚えして学習したQ値の最大値に従うと，次のような計画になるらしい．
$ python RL1JoG.py
Date Goto Life Reward Sum_Rewards
0 1/1 boogie 8 +1.0 1.00000
1 1/1 gundan 7 +10.0 11.00000
2 1/2 butanchu 6 +4.0 15.00000
3 1/2 butanchu 5 +2.0 17.00000
4 1/3 chin-yu 4 +2.0 19.00000
5 1/3 takayasu 3 +5.0 24.00000
6 1/4 gundan 2 +9.0 33.00000
7 1/4 kirameki 1 +3.0 36.00000
8 1/5 REST 4 +0.0 36.00000
9 1/5 ten-ichi 3 +3.0 39.00000
10 1/6 tentenyu 2 +6.0 45.00000
11 1/6 boogie 1 +1.0 46.00000
12 1/7 REST 4 +0.0 46.00000
13 1/7 gundan 3 +10.0 56.00000
14 1/8 yume-kata 2 +5.0 61.00000
15 1/8 gundan 1 +6.0 67.00000
16 1/9 REST 4 +0.0 67.00000
17 1/9 takayasu 3 +5.0 72.00000
18 1/10 gundan 2 +5.0 77.00000
19 1/10 yume-kata 1 +5.0 82.00000
20 1/11 REST 4 +0.0 82.00000
21 1/11 takayasu 3 +5.0 87.00000
22 1/12 arajin 2 +4.0 91.00000
23 1/12 REST 5 +0.0 91.00000
24 1/13 gundan 4 +7.5 98.50000
25 1/13 tsurukame 3 +3.0 101.50000
26 1/14 tentenyu 2 +6.0 107.50000
27 1/14 REST 5 +0.0 107.50000
28 1/15 tentenyu 4 +4.0 111.50000
29 1/15 tsurukame 3 +3.0 114.50000
30 1/16 gundan 2 +8.75 123.25000
31 1/16 REST 5 +0.0 123.25000
32 1/17 yume-kata 4 +5.0 128.25000
33 1/17 tsurukame 3 +3.0 131.25000
34 1/18 gundan 2 +7.375 138.62500
35 1/18 ten-ichi 1 +3.0 141.62500
36 1/19 REST 4 +0.0 141.62500
37 1/19 gundan 3 +5.6875 147.31250
38 1/20 kirameki 2 +3.0 150.31250
39 1/20 boogie 1 +1.0 151.31250
40 1/21 REST 4 +0.0 151.31250
41 1/21 ten-ichi 3 +3.0 154.31250
42 1/22 tentenyu 2 +6.0 160.31250
43 1/22 gokkei 1 +4.0 164.31250
44 1/23 REST 4 +0.0 164.31250
45 1/23 gundan 3 +9.84375 174.15625
46 1/24 kirameki 2 +3.0 177.15625
47 1/24 REST 5 +0.0 177.15625
48 1/25 takayasu 4 +5.0 182.15625
49 1/25 tsurukame 3 +3.0 185.15625
50 1/26 tentenyu 2 +6.0 191.15625
51 1/26 ikedaya 1 +2.0 193.15625
52 1/27 REST 4 +0.0 193.15625
53 1/27 yume-kata 3 +5.0 198.15625
54 1/28 tsurukame 2 +3.0 201.15625
55 1/28 REST 5 +0.0 201.15625
56 1/29 gundan 4 +10.0 211.15625
57 1/29 takayasu 3 +5.0 216.15625
58 1/30 REST 6 +0.0 216.15625
59 1/30 tentenyu 5 +6.0 222.15625
60 1/31 ikedaya 4 +2.0 224.15625
61 1/31 yume-kata 3 +5.0 229.15625
Sum_Rewards = 229.15625
ショボ……
同じルールで最適化した2手先読み探索の結果（Sum_Rewards=301.0）と比べると，正直微妙だと言わざるをえない．なんで満足度が1しかない一乗寺ブギーに何回も行ってんねんという気持ちになる．（ブギーさんごめんなさい！）
まあしかし，知識ゼロの地点からここまで成長できたかと思うと感慨深い．一乗寺でも死に覚えは有効なようである．高級食材でありながら致死性の高い毒を持つふぐ料理は何人もの料理人の犠牲の上に成り立っていると言うし，同じようなものなのかもしれない．皆さんは死なないでください．
最適な一乗寺ライフを！
###おわりに
前学期に強化学習理論の講義を受けたのでせっかくなら実際に動かしてみたいと思って題材にしたのですが，よく考えると設定した問題は報酬が過去の行動の影響を受けるからマルコフ性満たしてないじゃん．でもまあまあちゃんと学習できてたので逆にビビりました．
余裕があったらactor-critic法とかDQNも試そうと思ってたけど余裕が有馬温泉
それでは〜
###参考