Game Boy Supercomputer

Pada kecepatan lebih dari 1 miliar frame per detik, ini bisa dibilang yang tercepat dari cluster konsol 8-bit di dunia.


Distributed Tetris (1989)

Bagaimana cara membangun komputer seperti itu?

Resep

Ambil segenggam silikon, terapkan pelatihan penguatan, pengalaman dengan superkomputer, hasrat untuk arsitektur komputer, tambahkan keringat dan air mata, aduk 1000 jam hingga mendidih - dan voila.

Mengapa ada orang yang membutuhkan komputer seperti itu?

Singkatnya: bergerak ke arah meningkatkan kecerdasan buatan.


Salah satu dari 48 papan Komputer Neural IBM digunakan untuk percobaan

Dan ini adalah versi yang lebih detail

Tahun 2016. Pembelajaran mendalam ada di mana-mana. Pengenalan gambar dapat dianggap sebagai tugas yang diselesaikan berkat jaringan saraf convolutional, dan minat penelitian saya berusaha keras untuk jaringan saraf dengan memori dan pembelajaran yang diperkuat.



Secara khusus, dalam karya kepengarangan Google Deepmind ditunjukkan bahwa adalah mungkin untuk mencapai tingkat seseorang atau bahkan melampaui itu di berbagai game untuk Atari 2600 (konsol game rumah, dirilis pada tahun 1977), menggunakan algoritma pembelajaran sederhana yang didukung oleh Deep Q-Neural Network. Dan semua ini terjadi hanya ketika melihat gameplay. Itu menarik perhatian saya.


Salah satu game dengan Atari 2600, Breakout. Mesin itu dilatih menggunakan algoritma pembelajaran penguatan sederhana. Setelah jutaan iterasi, komputer mulai bermain lebih baik daripada manusia.

Saya mulai bereksperimen dengan game Atari 2600. Breakout, meskipun mengesankan, tidak bisa disebut rumit. Kesulitan dapat ditentukan oleh tingkat kesulitan sesuai dengan tindakan Anda (joystick) dan hasil Anda (poin). Masalah muncul ketika efeknya harus menunggu lama.


Ilustrasi masalah menggunakan game yang lebih kompleks sebagai contoh. Left - Breakout (ATARI 2600) [penulis salah, ini adalah game Pong / kira-kira. trans.] dengan respons yang sangat cepat dan umpan balik yang cepat. Kanan - Mario Land (Nintendo Game Boy) tidak memberikan informasi instan tentang efek tindakan, pengamatan yang tidak relevan dalam waktu yang lama dapat muncul di antara dua peristiwa penting.

Untuk membuat pembelajaran lebih efektif, orang dapat membayangkan upaya untuk mentransfer beberapa pengetahuan dari game yang lebih sederhana. Tugas ini sekarang tetap belum terselesaikan, dan merupakan topik aktif untuk penelitian. Sebuah tugas yang baru-baru ini diterbitkan dari OpenAI sedang mencoba mengukur hal itu.

Kemampuan untuk mentransfer pengetahuan tidak hanya akan mempercepat pelatihan - saya percaya bahwa beberapa masalah belajar tidak dapat diselesaikan sama sekali tanpa adanya pengetahuan dasar. Kami membutuhkan efisiensi data. Ambil game Prince of Persia:



Tidak ada poin jelas di dalamnya.
Butuh 60 menit untuk menyelesaikan permainan.



Apakah mungkin untuk menerapkan pendekatan yang sama yang digunakan saat menulis karya pada Atari 2600? Seberapa besar kemungkinan Anda bisa sampai pada akhirnya dengan menekan tombol acak?

Pertanyaan ini mendorong saya untuk berkontribusi pada komunitas, yang terdiri dari mencoba menyelesaikan masalah ini. Faktanya, kita memiliki tugas ayam dan telur - kita membutuhkan algoritma yang lebih baik yang akan memungkinkan kita untuk mengirimkan pesan, namun, ini memerlukan penelitian, dan eksperimen memakan waktu, karena kita tidak memiliki algoritma yang lebih efisien.


Contoh transfer pengetahuan: bayangkan bahwa kami pertama kali belajar memainkan permainan sederhana, seperti yang ada di sebelah kiri. Kemudian kita menyimpan konsep seperti "ras", "mobil", "trek", "menang" dan belajar warna atau model tiga dimensi. Kami berpendapat bahwa konsep umum dapat "dibawa" antar gim. Kesamaan game dapat ditentukan oleh jumlah pengetahuan yang ditransfer di antara mereka. Misalnya, game Tetris dan F1 tidak akan serupa.

Oleh karena itu, saya memutuskan untuk menggunakan pendekatan ideal kedua, menghindari perlambatan awal, secara dramatis mempercepat sistem. Tujuan saya adalah:
- Lingkungan dipercepat (bayangkan bahwa Prince of Persia dapat diselesaikan 100 kali lebih cepat) dan peluncuran simultan 100.000 game.
- lingkungan yang lebih cocok untuk penelitian (kami berkonsentrasi pada tugas, tetapi tidak pada perhitungan awal, kami memiliki akses ke berbagai permainan).

Awalnya, saya berpikir bahwa bottleneck kinerja entah bagaimana tergantung pada kompleksitas kode emulator (misalnya, basis kode Stella besar, dan bergantung pada abstraksi C ++ - bukan pilihan terbaik untuk emulator).

Konsol

Secara total, saya bekerja di beberapa platform, dimulai dengan salah satu game pertama yang pernah dibuat (bersama dengan game Pong) - Arcade Space Invaders, Atari 2600, NES dan Game Boy. Dan semua ini ditulis dalam C.

Saya berhasil mencapai frame rate maksimum 2000-3000 per detik. Untuk mulai mendapatkan hasil eksperimen, kami membutuhkan jutaan atau milyaran frame, sehingga jaraknya sangat besar.


Space Invaders bekerja di FPGA - mode debugging kecepatan rendah. Penghitung FPGA menunjukkan jumlah siklus jam yang telah berlalu.

Dan kemudian saya berpikir - bagaimana jika kita dapat mempercepat lingkungan yang tepat dengan besi. Misalnya, Space Invaders asli pergi ke CPU 8080 dengan frekuensi 1 MHz. Saya berhasil meniru CPU 8080 40 MHz pada prosesor Xeon 3 GHz. Tidak buruk, tetapi setelah saya meletakkan semua ini di dalam FPGA, frekuensinya naik menjadi 400 MHz. Itu berarti 24.000 FPS dari satu aliran - setara dengan 30 GHz Xeon! Apakah saya menyebutkan bahwa Anda dapat menjejalkan 100 8080 prosesor menjadi FPGA rata-rata? Ini sudah menghasilkan 2,4 juta FPS.


Space Invaders dengan akselerasi perangkat keras 100 MHz, seperempat kecepatan penuh


Lebih dari seratus core di dalam Xilinx Kintex 7045 FPGA (ditunjukkan oleh warna-warna cerah; titik biru di tengah adalah logika umum untuk demonstrasi).


Jalur eksekusi tidak rata

Anda mungkin bertanya, bagaimana dengan GPU? Singkatnya, kita membutuhkan konkurensi seperti MIMD , bukan SIMD . Sebagai seorang mahasiswa, saya bekerja selama beberapa waktu untuk mengimplementasikan pencarian pohon Monte Carlo pada GPU (pencarian semacam itu digunakan di AlphaGo).

Pada saat itu, saya menghabiskan waktu berjam-jam mencoba untuk mendapatkan GPU dan perangkat keras lainnya bekerja pada prinsip SIMD (IBM Cell, Xeon Phi, AVX CPU) untuk mengeksekusi kode seperti itu, dan tidak ada yang datang darinya. Beberapa tahun yang lalu, saya mulai berpikir bahwa akan menyenangkan untuk dapat secara mandiri mengembangkan perangkat keras yang dirancang khusus untuk memecahkan masalah yang terkait dengan pelatihan penguatan.




Konkurensi MIMD

ATARI 2600, NES atau Game Boy?

Pada 8080, saya mengimplementasikan Space Invaders, NES, 2600, dan Game Boy. Dan inilah beberapa fakta tentang mereka dan manfaatnya masing-masing.


NES Pacman

Space Invaders hanyalah pemanasan. Kami berhasil membuat mereka bekerja, tetapi itu hanya satu pertandingan, jadi hasilnya tidak terlalu berguna.

Atari 2600 sebenarnya adalah standar dalam penelitian pembelajaran penguatan. Prosesor MOS 6507 adalah versi sederhana dari 6502 yang terkenal, desainnya lebih elegan dan lebih efisien daripada 8080. Saya memilih 2600 bukan hanya karena batasan tertentu terkait dengan game dan grafiknya.

Saya juga menerapkan NES (Nintendo Entertainment System), berbagi CPU dengan 2600. Ada permainan yang jauh lebih baik daripada 2600. Tetapi kedua konsol menderita dari pipa pemrosesan grafis yang terlalu rumit dan beberapa format kartrid yang perlu didukung.

Sementara itu, saya menemukan kembali Nintendo Game Boy. Dan itulah yang saya cari.

Mengapa Game Boy sangat keren?

1049 game klasik dan 576 game untuk Game Boy Color

Secara total, lebih dari 1000 game, variasi yang sangat luas, kualitas tinggi, beberapa di antaranya cukup kompleks (Prince), game dapat dikelompokkan dan diberikan kompleksitas untuk penelitian transfer pengetahuan dan pelatihan (misalnya, ada pilihan untuk Tetris, game balap, Mario). Untuk menyelesaikan permainan Prince of Persia, Anda mungkin perlu mentransfer pengetahuan dari beberapa game serupa lainnya yang poinnya ditunjukkan dengan jelas (dalam Prince ini bukan).


Nintendo Game Boy adalah platform penelitian transfer pengetahuan favorit saya. Pada grafik, saya mencoba mengelompokkan permainan berdasarkan kompleksitas (subyektif) dan kesamaan (konsep seperti balap, melompat, menembak, berbagai permainan seperti Tetris; apakah ada yang bermain HATRIS?).

Game Boy klasik memiliki layar yang sangat sederhana (160x144, warna 2-bit), sehingga pemrosesan awal menjadi sederhana, dan Anda dapat berkonsentrasi pada hal-hal penting. Pada 2600, bahkan game sederhana memiliki banyak warna. Selain itu, pada objek Game Boy diperlihatkan jauh lebih baik, tanpa berkedip dan tanpa perlu mengambil maksimum dua frame berturut-turut.



Tidak ada tata letak memori yang gila, seperti NES atau 2600. Sebagian besar game dapat dibuat bekerja dengan 2-3 pemetaan.

Kode ringkas - Saya berhasil menyesuaikan seluruh emulator di C dalam tidak lebih dari 700 baris kode, dan implementasi Verilog saya muat dalam 500 baris.

Ada versi sederhana yang sama dari Space Invaders seperti di arcade.



Dan inilah dia, Game Boy dot-matrix 1989 saya dan versi FPGA yang bekerja melalui HDMI pada layar 4K.



Dan inilah yang tidak bisa dilakukan Game Boy lama saya:


Tetris dipercepat dengan besi - merekam dari layar secara real time, kecepatannya adalah 1/4 dari maksimum.

Apakah ada manfaat nyata untuk ini?

Ya ada. Sejauh ini, saya telah menguji sistem dalam kondisi sederhana, dengan jaringan aturan eksternal yang berinteraksi dengan masing-masing Game Boys. Lebih khusus lagi, saya menggunakan algoritma A3C (Advantage Actor Critic), dan saya berencana untuk menggambarkannya dalam posting terpisah. Rekan saya menghubungkannya ke jaringan convolutional pada FPGA, dan itu berfungsi.


Bagaimana FGPA berkomunikasi dengan jaringan saraf


A3C yang didistribusikan


Mario land: kondisi awal. Keystroke acak tidak akan membawa kita jauh. Pojok kanan atas menunjukkan waktu yang tersisa. Jika kita beruntung, kita akan segera mengakhiri permainan setelah menyentuh gumba. Jika tidak, butuh 400 detik untuk "kalah".


Mario tanah: setelah satu jam bermain, Mario belajar berlari, melompat dan bahkan membuka ruang rahasia, merangkak ke dalam pipa.


Pac Man: setelah sekitar satu jam pelatihan, jaringan saraf bahkan bisa menyelesaikan seluruh permainan satu kali (dengan memakan semua poin).

Kesimpulan

Saya ingin berpikir bahwa dekade berikutnya akan menjadi periode ketika superkomputer dan AI menemukan satu sama lain. Saya ingin memiliki perangkat keras yang memungkinkan saya untuk mengatur diri saya ke tingkat tertentu untuk beradaptasi dengan algoritma AI yang diinginkan.


Dekade berikutnya

Kode untuk Game Boy di C.

Debugging

Orang sering bertanya kepada saya: apa yang paling sulit? Itu saja - seluruh proyek cukup menyakitkan. Sebagai permulaan, tidak ada spesifikasi untuk Game Boy. Segala sesuatu yang kami pelajari, kami dapatkan berkat rekayasa balik, yaitu, kami meluncurkan tugas perantara, seperti permainan, dan menyaksikan bagaimana itu dilakukan. Ini sangat berbeda dari debugging perangkat lunak standar, karena di sini kita men-debug perangkat keras yang menjalankan program. Saya harus menemukan cara yang berbeda untuk mencapai ini. Dan saya berbicara tentang betapa sulitnya memonitor suatu proses ketika beroperasi pada frekuensi 100 MHz? Oh, dan tidak ada printf di sana.


Salah satu pendekatan untuk mengimplementasikan CPU adalah mengelompokkan instruksi pada fungsinya. Dengan 6502 jauh lebih mudah. LR35092 menjejalkan banyak omong kosong “acak” dan ada banyak pengecualian. Saya menggunakan tabel ini ketika bekerja dengan CPU Game Boy. Saya menggunakan strategi serakah - saya mengambil instruksi terbesar, menerapkannya dan menghapusnya, lalu mengulanginya. 1/4 dari instruksi adalah ALU, 1/4 adalah register loading, yang dapat diimplementasikan dengan cepat. Di sisi lain spektrum ada segala macam hal yang terpisah, seperti "unggah dari HL ke SP dengan tanda," yang harus diproses secara terpisah.


Debugging: jalankan kode pada perangkat keras yang Anda debug, tulis log implementasi Anda dan informasi tambahan (di sini perbandingan kode Verilog di sebelah kiri dengan C-emulator saya di sebelah kanan ditampilkan). Kemudian jalankan diff untuk log untuk menemukan inkonsistensi (biru). Salah satu alasan untuk menggunakan otomatisasi adalah bahwa dalam banyak kasus saya menemukan masalah setelah jutaan siklus eksekusi ketika satu flag CPU menyebabkan efek bola salju. Saya mencoba beberapa pendekatan, dan yang ini ternyata yang paling efektif.


Anda akan membutuhkan banyak kopi!


Buku-buku ini berusia 40 tahun. Sungguh menakjubkan menggeledah mereka dan melihat dunia komputer melalui mata para pengguna saat itu - saya merasa seperti tamu dari masa depan.

Permintaan Penelitian OpenAI

Pada awalnya saya ingin bekerja dengan game dalam hal memori, seperti yang dijelaskan dalam posting dari OpenAI.

Anehnya, mendapatkan Q-learning agar bekerja dengan baik pada input yang mewakili kondisi memori ternyata sulit.

Proyek ini mungkin tidak memiliki solusi. Tidak disangka mengetahui bahwa belajar-Q tidak akan pernah berhasil bekerja dengan memori di Atari, tetapi ada kemungkinan bahwa tugas ini akan sangat sulit.

Menimbang bahwa permainan di Atari hanya menggunakan memori 128 b, tampaknya sangat menarik untuk memproses 128 b ini alih-alih bingkai layar penuh. Saya mendapat hasil yang beragam, jadi saya mulai mencari tahu.

Dan meskipun saya tidak dapat membuktikan bahwa tidak mungkin untuk belajar dari ingatan, saya dapat menunjukkan bahwa anggapan bahwa ingatan mencerminkan keadaan permainan sepenuhnya adalah salah. CPU Atari 2600 (6507) menggunakan memori 128 b, tetapi masih memiliki akses ke register tambahan yang hidup di sirkuit terpisah (TIA, adaptor untuk TV, sesuatu seperti GPU). Register ini digunakan untuk menyimpan dan memproses informasi tentang objek (raket, roket, bola, tabrakan). Dengan kata lain, mereka tidak akan dapat diakses jika kita hanya mempertimbangkan ingatan. NES dan Game Boy juga memiliki register tambahan yang digunakan untuk mengontrol layar dan gulir. Hanya satu memori yang tidak mencerminkan kondisi permainan sepenuhnya.

Hanya 8080 yang secara langsung menyimpan data dalam memori video, yang memungkinkan Anda untuk mengekstrak seluruh kondisi permainan. Dalam kasus lain, register "GPU" terhubung antara CPU dan buffer layar, sementara di luar RAM.



Fakta menarik: jika Anda melakukan penelitian tentang sejarah GPU, maka 8080 mungkin menjadi "akselerator grafis" pertama - ini memiliki register geser eksternal yang memungkinkan Anda untuk memindahkan penjajah ruang angkasa dengan satu perintah, yang membongkar CPU.




Eof