AI Driven Snake Game using Deep Q Learning
Published: 2023-04-07 18:09:49

Ref: https://www.geeksforgeeks.org/ai-driven-snake-game-using-deep-q-learning/
**Introduction:**  project นี้เกี่ยวกับ Reinforcement Learning ที่จะให้ฝึกงู(เกมงู)ให้กินอาหารที่มีอยู่ใน the environment

gif ตัวอย่างแสดงเพื่อให้เข้าใจว่าเรากำลังจะสร้างอะไร
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gcftk320j7by9yudgk23.gif)


## ข้อกำหนดเบื้องต้นสำหรับ project นี้คือ:
- Reinforcement Learning
- Deep Learning (Dense Neural Network)
- Pygame

**วิธีสร้างเกมงู 2 มิติโดยใช้ pygame**
link : https://www.geeksforgeeks.org/snake-game-in-python-using-pygame-module/
หลังจากสร้างเกมงูได้แล้ว ตอนนี้จะมุ่งเน้นไปที่วิธีการประยุกต์ Reinforcement Learning กับเกมงู

## 3 Modules ที่เราต้องสร้างใน project นี้
**1. The Environment** (ตัวเกม)
**2. The Model** (Reinforcement model สำหรับการทำนายการเคลื่อนที่)
**3. The Agent** (ตัวกลางระหว่าง The Environment กับ The Model )


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8l3ic6cqdrjbbdkqkfd3.jpg)


## Algorithm:
เรามีงูและอาหารที่เกิดแบบสุ่ม

- คำนวณสถานะของงูโดยใช้ค่า 11 ค่า และหากเงื่อนไขใดเป็นจริงให้ ค่านั้นเป็น 1 ถ้าไม่ใช่ให้เป็น 0

     1. ตรงไปอันตราย
     2. เลี้ยวขวาอันตราย
     3. เลี้ยวซ้ายอันตราย
     4. ทิศซ้าย
     5. ทิศขวา
     6. ทิศบน
     7. ทิศล่าง
     8. อาหารอยู่ทางซ้าย
     9. อาหารอยู่ทางขวา
     10. อาหารอยู่บน
     11. อาหารอยู่ล่าง




![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a4pwxy72jybulids7y4t.png)ตัวอย่างการคำนวณสถานะ โดยค่าทั้งหมดจะคำนวณจากส่วนหัวของงู

- หลังจากได้ค่าของแต่ละสถานะแล้ว agent จะส่งค่าเหล่านี้ไปยัง model เพื่อดำเนินการขั้นต่อไป
- ลำดับถัดมาคือการคำนวณ Reward
 
 - **กินอาหาร : +10**
 - **Game Over : -10**
 - **อื่นๆ : 0**
- อัปเดตค่า Q (ซึ่งจะกล่าวถึงในภายหลัง) และฝึก model
- หลังจากวิเคราะห์ Algorithm แล้ว ตอนนี้เราต้องสร้างไอเดียเพื่อดำเนินการ Algorithm นี้ด้วยการ coding

## **The Model:**
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/524nffhfwyj6cagdm88a.png)

## Models ทำงานอย่างไร?
- เมื่อเกมเริ่ม ค่า Q จะถูกสุ่ม
- ระบบได้รับสถานะเป็น s
- ระบบจะดำเนินการแบบสุ่มหรือใช้ neural network นั้นขึ้นอยู่กับ s ซึ่งในช่วงแรกของการฝึก ระบบมักจะเลือกการกระทำแบบสุ่มเพื่อเพิ่มการสำรวจให้ได้มากที่สุด และภายหลังระบบจะอาศัย neural network มากขึ้นเรื่อยๆ
- เมื่อ AI เลือกและดำเนินการการกระทำ, the environment จะให้รางวัล จากนั้น agent จะเข้าสู่สถานะใหม่และอัพเดตค่า Q ตามสมการของ Bellman 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h1jzx5mnff413h9tifar.png)

- นอกจากนี้ สำหรับแต่ละการเคลื่อนไหวมันจะเก็บสถานะแรกเริ่ม การกระทำ, สถานะที่ได้รับหลังจากดำเนินการนั้น, รางวัลที่ได้รับ, และไม่ว่าเกมจะจบลงหรือไม่ ข้อมูลนี้จะถูกสุ่มตัวอย่างในภายหลังเพื่อฝึก neural network การดำเนินการนี้เรียกว่า Replay Memory
- การดำเนินการสองครั้งสุดท้ายนี้จะเกิดขึ้นซ้ำจนกว่าจะตรงตามเงื่อนไขที่กำหนด (ตัวอย่างเงื่อนไข: เกมจบลง)

หัวใจของ project นี้คือ model ที่กำลังจะฝึก เพราะความถูกต้องของการเดินของงูนั้นจะขึ้นอยู่กับคุณภาพของ model ที่สร้างขึ้น 

## Part-I

1. สร้าง class ชื่อ Linear_Qnet สำหรับการเริ่มต้น the linear neural network
2. ฟังก์ชัน forward ใช้เพื่อรับ input (เวกเตอร์สถานะ 11 ตัว) และส่งผ่านไปยัง Neural network และใช้ฟังก์ชันการเปิดใช้งาน relu และให้ out put กลับมา เช่น การขยับของเวกเตอร์ขนาด 1 x 3 (นี่คือฟังก์ชันการคาดคะเนที่ agent จะเรียกใช้)
3. ฟังก์ชัน save ใช้เพื่อบันทึก model ที่ผ่านการฝึกอบรมเพื่อใช้ในอนาคต

```
class Linear_QNet(nn.Module):
	def __init__(self, input_size, hidden_size, output_size):
		super().__init__()
		self.linear1 = nn.Linear(input_size, hidden_size)
		self.linear2 = nn.Linear(hidden_size, output_size)

	def forward(self, x):
		x = F.relu(self.linear1(x))
		x = self.linear2(x)
		return x

	def save(self, file_name='model_name.pth'):
		model_folder_path = 'Path'
		file_name = os.path.join(model_folder_path, file_name)
		torch.save(self.state_dict(), file_name)

```

## Part-II

1. สร้างคลาส QTrainer
   * การตั้งค่า learning rate สำหรับ optimizer
   * ค่า Gamma เป็น discount rate ที่ใช้ในสมการ Bellman
   * สร้าง Adam optimizer เพื่ออัปเดต weight และอคติ
   * criterion คือ the Mean squared loss ฟังก์ชัน

2. ฟังก์ชัน Train_step
   * PyTorch ใช้งานได้กับ tensors เท่านั้น ดังนั้นจึงต้องแปลงอินพุตทั้งหมดเป็น tensors
   * เรามี Training short memory ดังนั้นเราจะผ่านเพียงค่าเดียว สถานะ การกระทำ รางวัล การเคลื่อนไหว ดังนั้นเราต้องแปลงให้เป็นเวกเตอร์ เราจึงใช้ unsqueezed function
   * รับสถานะจาก model และคำนวณค่า Q ใหม่โดยใช้สูตรด้านล่าง:
     Q_new = รางวัล + แกมมา * สูงสุด (ค่า Q ถัดไปที่คาดการณ์ไว้)
  * คำนวณ mean squared error ระหว่างค่า Q ใหม่และค่า Q ก่อนหน้า และแพร่ error ย้อนกลับค่าที่มีส่วนเกี่ยวข้อง สำหรับการอัปเดต weight

```
class QTrainer:
	def __init__(self,model,lr,gamma):
		#Learning Rate for Optimizer
		self.lr = lr
		#Discount Rate
		self.gamma = gamma
		#Linear NN defined above.
		self.model = model
		#optimizer for weight and biases updation
		self.optimer = optim.Adam(model.parameters(),lr = self.lr)
		#Mean Squared error loss function
		self.criterion = nn.MSELoss()

	
	def train_step(self,state,action,reward,next_state,done):
		state = torch.tensor(state,dtype=torch.float)
		next_state = torch.tensor(next_state,dtype=torch.float)
		action = torch.tensor(action,dtype=torch.long)
		reward = torch.tensor(reward,dtype=torch.float)

		# if only one parameter to train , then convert to tuple of shape (1, x)
		if(len(state.shape) == 1):
			#(1, x)
			state = torch.unsqueeze(state,0)
			next_state = torch.unsqueeze(next_state,0)
			action = torch.unsqueeze(action,0)
			reward = torch.unsqueeze(reward,0)
			done = (done, )

		# 1. Predicted Q value with current state
		pred = self.model(state)
		target = pred.clone()
		for idx in range(len(done)):
			Q_new = reward[idx]
			if not done[idx]:
				Q_new = reward[idx] +
				self.gamma * torch.max(self.model(next_state[idx]))
			target[idx][torch.argmax(action).item()] = Q_new
		# 2. Q_new = reward + gamma * max(next_predicted Qvalue)
		#pred.clone()
		#preds[argmax(action)] = Q_new
		self.optimer.zero_grad()
		loss = self.criterion(target,pred)
		loss.backward() # backward propagation of loss

		self.optimer.step()

```


## The Agent
- รับสถานะปัจจุบันของงูจาก the Environment

```
def get_state(self, game):
	head = game.snake[0]
	point_l = Point(head.x - BLOCK_SIZE, head.y)
	point_r = Point(head.x + BLOCK_SIZE, head.y)
	point_u = Point(head.x, head.y - BLOCK_SIZE)
	point_d = Point(head.x, head.y + BLOCK_SIZE)

	dir_l = game.direction == Direction.LEFT
	dir_r = game.direction == Direction.RIGHT
	dir_u = game.direction == Direction.UP
	dir_d = game.direction == Direction.DOWN

	state = [
		# Danger Straight
		(dir_u and game.is_collision(point_u))or
		(dir_d and game.is_collision(point_d))or
		(dir_l and game.is_collision(point_l))or
		(dir_r and game.is_collision(point_r)),

		# Danger right
		(dir_u and game.is_collision(point_r))or
		(dir_d and game.is_collision(point_l))or
		(dir_u and game.is_collision(point_u))or
		(dir_d and game.is_collision(point_d)),

		# Danger Left
		(dir_u and game.is_collision(point_r))or
		(dir_d and game.is_collision(point_l))or
		(dir_r and game.is_collision(point_u))or
		(dir_l and game.is_collision(point_d)),

		# Move Direction
		dir_l,
		dir_r,
		dir_u,
		dir_d,

		# Food Location
		game.food.x < game.head.x, # food is in left
		game.food.x > game.head.x, # food is in right
		game.food.y < game.head.y, # food is up
		game.food.y > game.head.y # food is down
	]
	return np.array(state, dtype=int)

```
- Call model เพื่อรับสถานะต่อไปของงู

```
def get_action(self, state):
	# random moves: tradeoff explotation / exploitation
	self.epsilon = 80 - self.n_game
	final_move = [0, 0, 0]
	if(random.randint(0, 200) < self.epsilon):
		move = random.randint(0, 2)
		final_move[move] = 1
	else:
		state0 = torch.tensor(state, dtype=torch.float).cuda()
		prediction = self.model(state0).cuda() # prediction by model
		move = torch.argmax(prediction).item()
		final_move[move] = 1
	return final_move

```

- เล่นขั้นตอนที่คาดการณ์โดย model ใน the environment
- บันทึกสถานะปัจจุบัน การกระทำที่ทำ และ reward
- Train model จากการกระทำที่ทำ และ reward ที่ได้มาจาก the Environment (Training short memory)

```
def train_short_memory(self, state, action, reward, next_state, done):
	self.trainer.train_step(state, action, reward, next_state, done)

```
- หากเกมจบลงเนื่องจากการชนกำแพงหรือร่างกาย ให้ฝึก model ตามการเคลื่อนไหวทั้งหมดที่ทำจนถึงตอนนี้และรีเซ็ต the environment(Training Long memory)  Training in a batch size of 1000.

```
def train_long_memory(self):
	if (len(self.memory) > BATCH_SIZE):
		mini_sample = random.sample(self.memory, BATCH_SIZE)
	else:
		mini_sample = self.memory
	states, actions, rewards, next_states, dones = zip(*mini_sample)
	self.trainer.train_step(states, actions, rewards, next_states, dones)

```

**Output:**
- ใน Run เกมนี้ก่อนอื่นให้สร้าง environment ใน anaconda prompt หรือ (แพลตฟอร์มใดก็ได้) จากนั้นติดตั้งโมดูลที่จำเป็น เช่น Pytorch (สำหรับ DQ Learning Model), Pygame (สำหรับภาพของเกม) และโมดูลพื้นฐานอื่น ๆ
- จากนั้นเรียกใช้ไฟล์ agent.py ใน environment ที่เพิ่งสร้างขึ้น จากนั้นการฝึกจะเริ่มต้นขึ้น และคุณจะเห็น GUI สองอันต่อไปนี้ อันหนึ่งสำหรับความคืบหน้าของการฝึก และอีกอันสำหรับเกมงูที่เล่นโดย AI

- หลังจากได้คะแนนที่กำหนดแล้ว คุณสามารถออกจากเกมได้ และ model ที่คุณเพิ่งฝึกจะถูกเก็บไว้ใน path ที่คุณกำหนดไว้ในฟังก์ชันบันทึกของ models.py


หลังจากนี้ คุณสามารถใช้ model ที่ผ่านการฝึกอบรมนี้โดยเพียงแค่เปลี่ยนโค้ดในไฟล์ agent.py ดังที่แสดงด้านล่าง:

```
self.model.load_state_dict(torch.load('PATH'))

```

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/myizcgbl5pcts0j10r81.png)

**Initial Epochs  VS   After 100th Epochs**
Initial Epochs![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y7d0dcr02s5sk34s3er0.gif)After 100th Epochs
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wxcz3qhqc2cbasab221r.gif)

**สรุปผล**
เราสามารถนำ Deep Q Learning มาสร้าง AI ที่เล่นเกมงูได้เองโดยผ่านการฝึกใน environment ของตัวเกม ซึ่งในการฝึกก็มีทั้งการสุ่มและการใช้ Deep Q Learning เนื่องจากการสุ่มจะมีโอกาสที่เจอรูปแบบต่างๆได้มากกว่า ส่วน Deep Q Learning จะเลือกอันที่ optimal ที่สุดจากข้อมูลที่ถูก train มา

เย้!! 🎉
63120501033 พุฒิพงศ์ ป่าไม้ทอง
Source Code: https://github.com/vedantgoswami/SnakeGameAI