Tài liệu Bài tập lớn ứng dụng mạng nơ ron vào thiết kế trí tuệ nhân tạo học chơi flappy bird

lOMoARcPSD|16991370 TRƯỜNG ĐẠI HỌC KINH TẾ QUỐC DÂN -------***------- BÀI TẬP LỚN HỌC PHẦN TRÍ TUỆ NHÂN TẠO ĐỀ TÀI: Ứng dụng mạng nơ ron vào thiết kế Trí Tuệ Nhân Tạo học chơi Flappy Bird Họ và tên sinh viên: Mai Vĩnh Minh Lớp tín chỉ: Kinh tế chính trị Mác - Lênin(220)__07 Mã SV: 11206102 Hà Nội, 17 tháng 4 năm 2022 0 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 MỤC LỤC TỔNG QUAN ĐỀ TÀI Giới thiệu đề tài Công cụ xây dựng Mục tiêu Phân tích NỘI DUNG TÌM HIỂU Trí tuệ nhân tạo AI Machine learning Reinforcement learning Mạng nơ ron Giải thuật NEAT Ứng dụng NEAT vào Flappy Bird LẬP TRÌNH Lập trình trò chơi Flappy bird Cài đặt và ứng dụng giải thuật NEAT Kết quả 1 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 I. TỔNG QUAN VỀ ĐỀ TÀI 1. Giới thiệu đề tài Khi xã hội ngày càng phát triển, những công nghệ, máy móc đã thể hiện được sự đột phá về tính ứng dụng trong các vấn đề hàng ngày. Trí tuệ nhân tạo (còn được gọi là Artificial Intelligence - AI) cũng trên đà đó mà phát triển ngày càng mạnh mẽ trong nhiều lĩnh vực khác nhau trong khoa học và đời sống của con người, Để kiểm nghiệm mức độ thông minh của Trí tuệ nhân tạo, các nhà khoa học thường thử kiểm nghiệm thông qua các trò chơi, từ đó họ có thể đo lường và so sánh các sản phẩm AI để tìm ra sản phẩm nào tốt hơn. Trong nhiều thập kỷ qua, con người ngày càng phát triển ra nhiều thuật toán trong Trí tuệ nhân tạo đối đầu với con người trong nhiều trò chơi khác biệt nhau về quy tắc và thử thách như là cờ vua, cờ vây, poker, … Qua những hoạt động thử nghiệm trên, các nhà khoa học sẽ thu được dữ liệu và sử dụng để phát triển các ứng dụng sau này. Chính vì vậy,, em đã chọn đề tài huẩn luyện Trí tuệ nhân tạo chơi game Flappy Bird làm đề tài Bài tập lớn của mình. 2. Công cụ xây dựng Em sử dụng Integrated Development Environment là Pycharm và lập trình chủ yếu bằng ngôn ngữ lập trình python. Ngoài ra, em sử dụng thư viện pygame để lập trình giao diện trò chơi và thư viện neat-python để áp dụng thuật toán NEAT huẩn luyện cho Trí tuệ nhân tạo của mình. 3. Mục tiêu Tạo ra một Trí tuệ nhân tạo có khả năng tự học hỏi sau mỗi lần thua và ngày càng trở nên giỏi hơn cho tới mức không thể thua nữa. 4. Phân tích 2 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 Về trò chơi Flappy bird: Flappy Bird (tạm dịch là Chú chim vỗ cánh) là một trò chơi điện tử trên điện thoại do anh Nguyễn Hà Đông phát triển, và do dotGEARS, một studio phát triển game quy mô nhỏ, hoạt động độc lập có trụ sở tại Việt Nam phát hành vào năm 2013. Trò chơi được trình bày theo phong cách sidescroller (phong cách game với các đối tượng được nhìn thấy ở mặt bên (side-view) và di chuyển từ cạnh trái sang cạnh phải của màn hình), trong đó người chơi điều khiển một chú chim, cố gắng vượt qua các hàng ống màu xanh lá cây mà không chạm vào chúng. Mục tiêu của trò chơi là điều khiển một chú chim bay qua những cái ống. Nếu chú chim chạm vào chướng ngại vật thì trò chơi sẽ kết thúc. Mỗi khi chú chim vượt qua một cặp ống thì người chơi nhận được một điểm. Về thuật toán AI phù hợp: Thuật toán NEAT là viết tắt của NeuroEvolution of Augmented Topologies. Nó là một phương pháp để phát triển mạng nơ-ron nhân tạo bằng một thuật toán di truyền. NEAT thực hiện ý tưởng hiệu quả nhất bằng cách bắt đầu quá trình phát triển với các mạng nhỏ, đơn giản và cho phép chúng ngày càng trở nên phức tạp qua nhiều thế hệ. 3 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 II. NỘI DUNG TÌM HIỂU 1. Trí tuệ nhân tạo AI - Artificial Intelligence hay còn gọi là Trí tuệ nhân tạo là một ngành khoa học, kỹ thuật chế tạo máy móc thông minh, đặc biệt là các chương trình máy tính thông minh. AI được thực hiện bằng cách nghiên cứu cách suy nghĩ của con người, cách con người học hỏi, quyết định và làm việc trong khi giải quyết một vấn đề nào đó, và sử dụng những kết quả nghiên cứu này như một nền tảng để phát triển các phần mềm và hệ thống thông minh, từ đó áp dụng vào các mục đích khác nhau trong cuộc sống. Nói một cách dễ hiểu thì AI là việc sử dụng, phân tích các dữ liệu đầu vào nhằm đưa ra sự dự đoán rồi đi đến quyết định cuối cùng. Trí tuệ nhân tạo khác với việc lập trình logic trong các ngôn ngữ lập trình là ở việc ứng dụng các hệ thống học máy (machine learning) để mô phỏng trí tuệ của con người trong các xử lý mà con người làm tốt hơn máy tính. Cụ thể, trí tuệ nhân tạo giúp máy tính có được những trí tuệ của con người như: biết suy nghĩ và lập luận để giải quyết vấn đề, biết giao tiếp do hiểu ngôn ngữ, tiếng nói, biết học và tự thích nghi,… 2. Machine learning Machine learning (ML) hay máy học là một nhánh của trí tuệ nhân tạo (AI), nó là một lĩnh vực nghiên cứu cho phép máy tính có khả năng cải thiện chính bản thân chúng dựa trên dữ liệu mẫu (training data) hoặc dựa vào kinh nghiệm (những gì đã được học). Machine learning có thể tự dự đoán hoặc đưa ra quyết định mà không cần được lập trình cụ thể. Quá trình học bắt đầu bằng các quan sát hoặc dữ liệu. Ví dụ, để tìm kiếm các mẫu trong dữ liệu và đưa ra quyết định tốt hơn trong tương lai dựa trên các ví dụ mà chúng tôi cung cấp. Mục đích chính là cho phép các máy 4 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 tính tự động học mà không cần sự can thiệp hay trợ giúp của con người và điều chỉnh các hành động tương ứng. 3. Học tăng cường (Reinforcement learning) Reinforcement learning là một lĩnh vực con của học máy, nghiên cứu cách thức một agent trong một môi trường nên chọn thực hiện các hành động nào để cực đại hóa một khoản thưởng (reward) nào đó về lâu dài. Các thuật toán học tăng cường cố gắng tìm một chiến lược ánh xạ các trạng thái của thế giới tới các hành động mà agent nên chọn trong các trạng thái đó. 4. Mạng nơ ron (Neural network) Khái niệm: Mạng nơ-ron nhân tạo là một chuỗi những thuật toán được đưa ra để tìm kiếm các mối quan hệ cơ bản trong tập hợp các dữ liệu. Thông qua việc bắt bước cách thức hoạt động từ não bộ con người. Nói cách khác, mạng nơ ron nhân tạo được xem là hệ thống của các tế bào thần kinh nhân tạo. Đây thường có thể là hữu cơ hoặc nhân tạo về bản chất. Mạng nơ-ron có khả năng thích ứng được với mọi thay đổi từ đầu vào. Do vậy, nó có thể đưa ra được mọi kết quả một cách tốt nhất có thể mà bạn không cần phải thiết kế lại những tiêu chí đầu ra. Đặc điểm: Trong lĩnh vực tài chính, mạng nơ ron nhân tạo hỗ trợ cho quá trình phát triển các quy trình như: giao dịch thuật toán, dự báo chuỗi thời gian, phân loại chứng khoán, mô hình rủi ro tín dụng và xây dựng chỉ báo độc quyền và công cụ phát sinh giá cả. Mạng nơ ron nhân tạo có thể hoạt động như mạng nơ ron của con người. Mỗi một nơ ron thần kinh trong nơ ron nhân tạo là hàm toán học với chức năng thu thập và phân loại các thông tin dựa theo cấu trúc cụ thể. 5 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 Neural Network có sự tương đồng chuẩn mạnh vối những phương pháp thống kê như đồ thị đường cong và phân tích hồi quy. Neural Network có chứa những lớp bao hàm các nút được liên kết lại với nhau. Mỗi nút lại là một tri giác có cấu tạo tương tự với hàm hồi quy đa tuyến tính.Bên trong một lớp tri giác đa lớp, chúng sẽ được sắp xếp dựa theo các lớp liên kết với nhau. Lớp đầu vào sẽ thu thập các mẫu đầu vào và lớp đầu ra sẽ thu nhận các phân loại hoặc tín hiệu đầu ra mà các mẫu đầu vào có thể phản ánh lại. Kiến trúc: Neural Network là sự kết hợp của những tầng perceptron hay còn gọi là perceptron đa tầng. Và mỗi một mạng Neural Network thường bao gồm 3 kiểu tầng là: Tầng input layer (tầng vào): Tầng này nằm bên trái cùng của mạng, thể hiện cho các đầu vào của mạng, bao gồm những hiểu biết mà mạng sở hữu (Là con mắt của Trí tuệ nhân tạo. Tầng output layer (tầng ra): Là tầng bên phải cùng và nó thể hiện cho những đầu ra của mạng. Tầng ra sẽ điều khiển hoạt động của AI. Để đưa các giá trị từ các input layer tới output layer chúng ta cần sử dụng connection (liên kết). Mỗi input layer sẽ nối tới một output layer để các dòng thông tin có thể hiển thị trên màn hình. Đặc biệt, mỗi connection có một thuộc tính được gọi là weight (sức nặng) biểu diễn cho sự mạnh yếu của connection. Lưu ý: Mỗi một Neural Network chỉ có duy nhất một tầng vào và 1 tầng ra nhưng lại có rất nhiều tầng ẩn. Với mạng Neural Network thì mỗi nút mạng là một sigmoid neuron nhưng chúng lại có hàm kích hoạt khác nhau. Thực tế, người ta thường sử dụng có cùng loại với nhau để việc tính toán 6 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 thuận lợi hơn. Tại mỗi tầng, số lượng nút mạng có thể khác nhau còn tùy vào bài toán hoặc cách giải quyết. Tuy nhiên, khi làm việc người ta sẽ để các tầng ẩn số với số lượng neuron khác nhau. Ngoài ra, những nơron nằm ở tầng thường sẽ liên kết đôi với nhau để tạo thành mạng kết nối đầy đủ nhất. Khi đó, người dùng có thể tính toán được kích cỡ của mạng dựa vào tầng và số lượng nơ ron. Cài đặt mạng nơ ron vào bài toán Flappy bird: Chúng ta chuyển các giá trị vào input neuron bao gồm: tung độ của chú chim, khoảng cách của chim với top của đường ống và khoảng cách của chim tới bottom của đường ống. Những thông tin này sẽ được cung cấp cho output layer thông qua connection bao gồm các weight để quyết định nhảy hay không. Weighted sum (tổng trọng số), còn được gọi là tổ hợp tuyến tính có trọng số, là phương pháp đa tiêu chí phân tích đơn giản nhất và được biết đến nhiều nhất để đánh giá một số lựa chọn thay thế cho một số quyết định. Do vậy, 7 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 weighted sum tính toán được sẽ được đưa ra output layer và thực hiện 2 phép toán cuối cùng. Weighted sum với TH input và weight ở connection như hình Phép toán đầu tiên là tính bias. Bias được thêm vào kết quả của phép nhân trọng số với đầu vào. Kết quả của phép nhân luôn là một hàm tuyến tính đi qua gốc tọa độ, sử dụng bias giúp mạng nơ ron có thể dịch chuyển hàm tuyến tính này một cách linh hoạt. Bias cũng là một tham số được học trong quá trình huấn luyện mạng nơ-ron. Nhờ vậy, bias giúp dịch chuyển mạng nơ ron vào vị trí chuẩn xác trong chiều không gian. 8 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 VD về weighted sum sau khi cộng bias Điều cuối cùng chúng ta cần thực hiện là áp dụng hàm kích hoạt. Hàm này cho phép chúng ta lấy giá trị cho đầu ra của nơ ron giữa 2 tập số, từ đó dễ dàng hơn trong việc kiểm tra số này có gần với số kia không để quyết định xem có nên nhảy hay không. Có rất nhiều hàm để thực thi công việc trên nhưng trong TH này, hàm tính tan(x) sẽ là phù hợp nhất. Hàm tan(x) khi truyền vào tham số weighted sum, nếu weighted sum dương càng lớn thì hàm tan(weighted sum) càng trả về giá trị gần 1 và nếu weighted sum âm càng nhỏ thì hàm tan(weighted sum) càng trả về giá trị gần -1. Và chúng ta có thể lấy bất kì số trong (-1, 1) để quyết định việc có nên nhảy hay không. Trong TH bài tập lớn của em, em xin chọn số 0.5, tức 9 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 là nếu giá trị của hàm kích hoạt tan(weighted sum) > 0.5 thì mạng nơ ron sẽ trả về kết quả nhảy, TH còn lại là không nhảy. 5. Giải thuật NEAT Giải thuật NEAT (Neuronevolution of Augmenting Topologies) là một giải thuật tiến hóa mạng nơ ron nhân tạo phổ biến. Trước tiên, chúng ta cần hiểu tiến hóa nơ ron (Neuronevolution) là gì ? Neuronevolution là sự phát triển nhân tạo của mạng nơ ron ứng dụng giải thuật di truyền, kết hợp giải thuật tiến hóa sinh học và mô phỏng lại để thiết kế mạng nơ ron. Neuronevolution đã cho thấy kết quả xuất sắc trong các tác vụ học tăng cường (Reinforcement learning). Học tăng cường cho thấy được sự hứa hẹn trong việc thiết kế cấu trúc mạng nơ ron, tuy nhiên vẫn còn chậm ở một số tìm kiểm khả vi. Có thể nói, giải thuật NEAT được lấy cảm hứng từ học thuyết chọn lọc tự nhiên của Charles Darwin. Để hiểu rõ hơn về giải thuật NEAT, chúng ta cần hiểu những khía cạnh cơ bản trong thuật toán này bao gồm: mã hóa gen, đánh dấu lịch sử sinh sản, hình thành loài, đánh giá năng lực, cấu trúc tối thiểu. Đầu tiên, mã hóa gen (Genetic encoding) là cách NEAT mã hóa mạng nơ ron thành 2 kiểu: Kiểu gen và Kiểu hình. Kiểu gen chính là mã hóa cơ bản của mạng nơ ron, sẽ sử dụng sinh sản (crossover) và đột biến (mutation). Kiểu hình là kết quả của mạng nơ ron, kết quả này sẽ được đánh giá về sau. 10 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 Cách thuật toán NEAT nhận biết kiểu gen và kiểu hình Cách thuật toán NEAT tạo nên sự đột biến Tiếp theo, đánh dấu lịch sử sinh sản (Historical Marking Crossover) là kĩ thuật cho phép sinh sản giữa cấu trúc mạng nơ ron, gia tăng thêm độ phức tạp của hệ sinh thái, cho phép cạnh tranh các topo của mạng nơ ron với nhau trong ổ sinh thái đó. 11 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 NEAT sẽ lấy 2 cá thể có biểu hiện xuất sắc nhất để sản sinh thế hệ mới Đánh giá năng lực (Fitness sharing) là cạnh tranh trang cùng ổ sinh thái với nhau chứ không cạnh tranh trong cả mô hình nhằm đạt một khoản thưởng (reward) nào đó. Việc tìm phương thức đánh giá không phải luôn khả thi, ví dụ trong bài toàn tìm một giai điệu mới, việc đánh giá giai điệu đó có “dễ nghe”, “hay” hay không thuộc về cảm quan của mỗi người, nên việc tìm một hàm đánh giá chính xác sẽ rất khó khăn. Nếu chi phí tính toán của phương thức đánh giá quá lớn, việc sử dụng để tìm kiếm trong không gian sẽ mất nhiều thời gian, thậm chí lâu hơn vét cạn. Cuối cùng là cấu trúc tối thiểu, đơn giản là bắt đầu hệ thống mạng nơ ron với một số lượng nhất định. 6. Ứng dụng NEAT vào Flappy Bird Đầu tiên, chúng ta tạo ra 100 cá thể chim, và mỗi cá thể chim đều có một mạng nơ ron điều khiển. Mỗi mạng nơ ron này sẽ được khởi tạo với những bias và weight hoàn toàn ngẫu nhiên. Kế tiếp, chúng ta sẽ tiến hành 12 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 kiểm thử tất cả các mạng nơ ron trong màn chơi và đánh giá mức độ dựa trên kết quả của mạng nơ ron. Việc đánh giá này sẽ dựa trên tiêu chí là quãng đường mà chim vượt qua được, cụ thể hơn là mỗi frame trong trò chơi chim vượt qua được mà không bị “gãy cánh”. Sau khi hoàn tất mô phỏng kiểm thử lần một (tất cả chim đều rơi), chúng ta sẽ thu được kết quả, từ đó đánh giá được những con chim làm vượt trội hơn so với các con chim thông thường khác. Và từ những con chim đó, NEAT sẽ tiến hành đột biến và sinh sản ra 1 thế hệ mới vượt trội hơn bao gồm 100 con thuộc loài chim mới. Vì những con chim này tới từ những con chim tốt nhất trong kiểm thử lần một nên chúng ta kì vọng rằng trong lần kiểm thử tiếp theo, thế hệ mới sẽ làm tốt hơn thế hệ cũ. Lặp đi lặp lại thao tác này nhiều lần, ta sẽ thu được “chú chim bất khả chiến bại, siêu sức mạnh” như những siêu nhân trong phim ảnh. 13 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 LẬP TRÌNH 1. Lập trình trò chơi Flappy Bird Load các dữ liệu, thư viện cần thiết và phông chữ của trò chơi: Lớp Bird: Lớp này mô phỏng đối tượng chú chim trong trò chơi Flappy Bird, có các thuộc tính cơ bản như tọa độ (x, y), tilt: độ nghiêng, tick_count: số frame đã đi qua, height: độ cao, vel: vận tốc, img_count: sử dụng để theo dõi 14 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 animation của chim, img: hình ảnh render của chim. Các thuộc tính trên được sử dụng để xử lí logic vật lý và animation cho đối tượng. Các hàm cơ bản của lớp như: Hàm __init__: constructor của Bird Hàm move(self): hàm này xử lý phương thức di chuyển của đối tượng. Để tính quãng đường rơi, ta sử dụng công thức d = v x t + x a x t2. Ngoài ra, hàm bao gồm một số thao tác xử lý logic vật lý khác như điểm rơi, độ nghiêng. Hàm jump(self): xử lý đối tượng nhảy tại trục tọa độ. Hàm draw(self): hàm này xử lý animation của bird, giữ cho chim luôn bay ở trung tâm màn hình, và khi chim rơi thì sẽ không đập cánh. Hàm get_mask(self): Sử dụng thư viện pygame để lấy border của chim theo hình ảnh, từ đó dễ dàng xử lý va chạm với cột về sau. 15 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 Lớp Pipe: Lớp này mô phỏng đối tượng ống trong trò chơi Flappy Bird, bao gồm các thuộc tính cơ bản như x: hoành độ trong trục tọa độ, height: độ cao của ống, PIPE_TOP: hình ảnh ống trên, PIPE_BOTTOM: hình ảnh ống dưới, passed: Boolean kiểm tra chim đã bay qua ống chưa. Hàm set_height(self): hàm này xây dựng độ cao của ổng trên và ống dưới 16 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 Hàm move(self): di chuyển ống Hàm draw(self): render ống trên và ống dưới dựa trên số liệu top và bottom Hàm collide(self): Kiểm tra va chạm giữa đối tượng chim và ống, nếu chim va chạm vào ống hàm trả về True, ngược lại hàm trả về False. Lớp Base: 17 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 Lớp base mô phỏng đối tượng mặt đất trong trò chơi Flappy Bird, bao gồm các thuộc tính cơ bản như y: tung độ, x1: hoành độ 1, x2: hoành độ 2. Các hàm cơ bản gồm có move(self): hàm này dùng để khiến mặt đất di chuyển, nếu di chuyển hết mặt đất đầu tiên sẽ vẽ tiếp mặt đất thứ hai tại đó, khi di chuyển hết mặt đất thứ hai liền lập tức vẽ tiếp mặt đất thứ nhất, từ đó tạo nên animation scrolling. Hàm draw(self): render 2 mặt đất di chuyển theo nguyên tắc move(self) ở trên. Ngoài ra, hàm draw_ window() để render tất cả đối tượng trên. Game loop sẽ được xử lý trong hàm main. 18 Downloaded by nguyenphuong Phuong nguyen ([email protected]) lOMoARcPSD|16991370 2. Cài đặt và ứng dụng giải thuật NEAT Cài đặt: File config-feedfoward.txt bao gồm những thông số cài đặt mạng nơ ron, bias, và thông số genomes để điều khiển fitness score, kích thước mẫu (pop_size)… Ứng dụng: Tiến hành load file config-feedfoward.txt từ local directory và bắt đầu cài đặt NEAT từ các thông số trong file. Ngoài ra, chúng ta thêm bộ xuất thông số đầu ra để tiện theo dõi các thông số các thế hệ sau này. Tiến hành khởi tạo neural network và genome vào từng chú chim một trong kích thước mẫu. Mạng nơ ron sẽ cho mỗi chú chim biết khi nào nên nhảy, và genome sẽ điều khiển thông số fitness của từng chú chim. 19 Downloaded by nguyenphuong Phuong nguyen ([email protected])