<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Artificial Intelligence & Machine Learning
Tugas 3
Step1:  1. Dynamic Programming (5 poin)
Seorang pria di Australia pada tahun 2017 memesan 200 McNuggets melalui drive-through hingga diliput oleh media setempat. Asumsikan bahwa McDonald's bersedia memenuhi permintaan tersebut dan dalam menu terdapat kombinasi paket McNuggets berisi 3, 6, 10, dan 24. Buatlah program dinamis untuk menghitung berapa jumlah paket McNuggets minimum yang dapat diberikan kepada pria tersebut!
Step2:  2. Search (10 poin)
Diberikan peta UK sebagai berikut.
Step3:  Soal 2.1 (2 poin)
Gunakan algoritma UCS dari networkx untuk mencari jalan dari London ke Edinburgh.
Step4:  Soal 2.2 (4 poin)
Gunakan algoritma A* dari networkx untuk mencari jalan dari London ke Edinburgh. Implementasikan fungsi heuristik berdasarkan variabel heuristics yang diberikan.
Step5:  Soal 2.3 (2 poin)
Berapa jarak tempuh dari jalur terpendek London ke Edinburgh dari soal 2.2?
Step6:  Soal 2.4 (2 poin)
Apakah hasil pada soal 2.1 dan 2.2 sama? Mengapa?
Jawaban Anda di sini
3. Reinforcement Learning (10 poin)
Game yang akan dimainkan kali ini adalah Frozen Lake. Terjemahan bebas dari dokumentasi
Step7:  Soal 3.2.1 (2 poin)
Simulasikan permainan ini dengan algoritma random dan SARSA. Bandingkan rata-rata utilities yang didapatkan.
Step8:  Soal 3.2.2 (2 poin)
Gambarkan perubahan nilai utilities dari algoritma random dan SARSA dengan rolling mean 100 episodes. Apa yang dapat Anda amati?
Petunjuk
Step9:  Soal 3.3 (2 poin)
Tampilkan optimal policy untuk setiap state dari algoritma SARSA.
<ASSISTANT_TASK:>
Python Code:
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
plt.rcParams = plt.rcParamsOrig
Explanation: Artificial Intelligence & Machine Learning
Tugas 3: Search & Reinforcement Learning
Mekanisme
Anda hanya diwajibkan untuk mengumpulkan file ini saja ke uploader yang disediakan di https://elearning.uai.ac.id/. Ganti nama file ini saat pengumpulan menjadi tugas3_NIM.ipynb.
Keterlambatan: Pengumpulan tugas yang melebihi tenggat yang telah ditentukan tidak akan diterima. Keterlambatan akan berakibat pada nilai nol untuk tugas ini.
Kolaborasi: Anda diperbolehkan untuk berdiskusi dengan teman Anda, tetapi dilarang keras menyalin kode maupun tulisan dari teman Anda. Kecurangan akan berakibat pada nilai nol untuk tugas ini.
Petunjuk
Anda diperbolehkan (jika dirasa perlu) untuk mengimpor modul tambahan untuk tugas ini. Namun, seharusnya modul yang tersedia sudah cukup untuk memenuhi kebutuhan Anda. Untuk kode yang Anda ambil dari sumber lain, cantumkan URL menuju referensi tersebut jika diambil dari internet!
Perhatikan poin untuk tiap soal! Semakin kecil poinnya, berarti kode yang diperlukan untuk menjawab soal tersebut seharusnya semakin sedikit!
End of explanation
def dynamic_prog_mcnuggets(total_mcnuggets: int, packs: list):
    pass # Kode Anda di sini
dynamic_prog_mcnuggets(200, [3, 6, 10, 24])
Explanation: 1. Dynamic Programming (5 poin)
Seorang pria di Australia pada tahun 2017 memesan 200 McNuggets melalui drive-through hingga diliput oleh media setempat. Asumsikan bahwa McDonald's bersedia memenuhi permintaan tersebut dan dalam menu terdapat kombinasi paket McNuggets berisi 3, 6, 10, dan 24. Buatlah program dinamis untuk menghitung berapa jumlah paket McNuggets minimum yang dapat diberikan kepada pria tersebut!
End of explanation
import networkx as nx
import urllib
locs = pd.read_csv('https://raw.githubusercontent.com/aliakbars/uai-ai/master/datasets/uk-coordinates.csv')
heuristics = pd.read_csv('https://raw.githubusercontent.com/aliakbars/uai-ai/master/datasets/uk-heuristics.csv')
G = nx.read_gpickle(urllib.request.urlopen("https://raw.githubusercontent.com/aliakbars/uai-ai/master/datasets/uk.pickle"))
def draw_map(G, locs):
    pos = locs.set_index('city_name').apply(
        lambda x: (x['longitude'], x['latitude']),
        axis=1
    ).to_dict()
    
    fig, ax = plt.subplots(figsize=(7, 7))
    nx.draw(
        G, pos,
        with_labels=True,
        edge_color='#DDDDDD',
        node_color='#A0CBE2',
        node_size=300,
        font_size=10,
        ax=ax
    )
    labels = nx.get_edge_attributes(G, 'weight')
    labels = {k: np.round(v).astype(int) for k, v in labels.items()}
    nx.draw_networkx_edge_labels(
        G, pos,
        edge_labels=labels,
        ax=ax
    )
draw_map(G, locs)
Explanation: 2. Search (10 poin)
Diberikan peta UK sebagai berikut.
End of explanation
# Kode Anda di sini
Explanation: Soal 2.1 (2 poin)
Gunakan algoritma UCS dari networkx untuk mencari jalan dari London ke Edinburgh.
End of explanation
def heuristic(source, target):
    pass # Kode Anda di sini
# Kode Anda di sini
Explanation: Soal 2.2 (4 poin)
Gunakan algoritma A* dari networkx untuk mencari jalan dari London ke Edinburgh. Implementasikan fungsi heuristik berdasarkan variabel heuristics yang diberikan.
End of explanation
# Kode Anda di sini
Explanation: Soal 2.3 (2 poin)
Berapa jarak tempuh dari jalur terpendek London ke Edinburgh dari soal 2.2?
End of explanation
from tqdm.notebook import trange
import gym
class Agent:
    def __init__(self, env, algo="random", eps=0.2, eta=0.1, gamma=1):
        self.env = env
        self.s = env.reset() # inisialisasi state
        self.q = np.zeros((env.observation_space.n, env.action_space.n)) # inisialisasi semua nilai pada matriks Q = 0
        self.eps = eps # probabilitas eksplorasi
        self.eta = eta # learning rate
        self.gamma = gamma # discount factor
        self.algo = algo
    
    def update_q(self, s, a, r, s_, a_):
        # Implementasikan SARSA pada bagian ini
        self.q[s, a] = ... # Kode Anda di sini
    
    def choose_action(self, s):
        if self.algo == "random":
            return self.env.action_space.sample()
        elif self.algo == "sarsa":
            ... # Kode Anda di sini
        else:
            raise NotImplementedError()
    
    def play(self):
        a = self.choose_action(self.s)
        state, reward, done, _ = self.env.step(a)
        action = self.choose_action(state) # melihat aksi selanjutnya
        self.update_q(self.s, a, reward, state, action)
        self.s = state # state saat ini diperbarui
        return done, reward
    
    def reset(self):
        self.s = self.env.reset()
Explanation: Soal 2.4 (2 poin)
Apakah hasil pada soal 2.1 dan 2.2 sama? Mengapa?
Jawaban Anda di sini
3. Reinforcement Learning (10 poin)
Game yang akan dimainkan kali ini adalah Frozen Lake. Terjemahan bebas dari dokumentasi:
Musim dingin telah tiba. Anda dan teman Anda sedang bermain frisbee dan tanpa sengaja Anda melempar cakram frisbee ke tengah danau. Sebagian besar danau sudah beku, tetapi ada beebrapa lubang karena esnya telah mencair. Jika Anda terjatuh ke lubang, maka Anda akan tercebur ke air yang sangat dingin. Anda harus mengambil cakram tersebut dengan menyeberangi danau. Namun, es yang Anda pijak licin, sehingga Anda tidak selalu bisa berjalan ke arah yang Anda tuju. Anda diminta mencari strategi (policy) berupa jalan yang aman menuju ke ubin tujuan.
Peta danau:
SFFF
FHFH
FFFH
HFFG
Soal 3.1 (4 poin)
Di dalam kelas yang sudah didefinisikan di bawah ini:
1. Implementasikan SARSA untuk memperbarui nilai Q. (2 poin)
2. Implementasikan algoritma $\epsilon$-greedy untuk memilih aksi. Petunjuk: Manfaatkan np.random.random(). (2 poin)
End of explanation
def simulate(algo, num_episodes=10000):
    np.random.seed(101)
    env = gym.make("FrozenLake-v0")
    agent = Agent(env, algo)
    utilities = []
    for i in trange(num_episodes):
        while True:
            done, reward = agent.play()
            if done:
                utilities.append(reward)
                agent.reset()
                break
    env.close()
    
    return agent, utilities
# Kode Anda di sini
Explanation: Soal 3.2.1 (2 poin)
Simulasikan permainan ini dengan algoritma random dan SARSA. Bandingkan rata-rata utilities yang didapatkan.
End of explanation
# Kode Anda di sini
Explanation: Soal 3.2.2 (2 poin)
Gambarkan perubahan nilai utilities dari algoritma random dan SARSA dengan rolling mean 100 episodes. Apa yang dapat Anda amati?
Petunjuk: Cari tentang "pandas rolling mean".
End of explanation
# Kode Anda di sini
Explanation: Soal 3.3 (2 poin)
Tampilkan optimal policy untuk setiap state dari algoritma SARSA.
End of explanation
<END_TASK>