Pada artikel ini, saya akan berbagi pengalaman menumbuhkan kecerdasan buatan sederhana (AI) menggunakan algoritma genetika, dan juga berbicara tentang set minimum perintah yang diperlukan untuk membentuk perilaku apa pun.
Hasil dari pekerjaan ini adalah bahwa AI, yang tidak mengetahui aturannya, secara independen menguasai permainan tic-tac-toe dan menemukan kelemahan bot yang bermain melawannya. Tetapi saya mulai dengan tugas yang bahkan lebih sederhana.
Set instruksi
Semuanya dimulai dengan menyiapkan serangkaian perintah yang bisa dimiliki AI. Bahasa tingkat tinggi berisi ratusan operator yang berbeda. Untuk menyoroti minimum yang diperlukan, saya memutuskan untuk beralih ke bahasa Assembler. Namun ternyata mengandung banyak perintah.
Saya membutuhkan AI untuk membaca dan mengeluarkan data, bekerja dengan memori, melakukan perhitungan dan operasi logis, membuat transisi dan loop. Saya menemukan bahasa Brainfuck, yang hanya berisi 8 perintah dan dapat melakukan perhitungan apa pun (mis. Turing selesai). Pada prinsipnya, ini cocok untuk pemrograman genetika, tetapi saya melangkah lebih jauh.
Saya bertanya-tanya: berapa jumlah minimum perintah yang diperlukan untuk mengimplementasikan algoritma apa pun? Ternyata - satu!
Prosesor URISC hanya berisi satu perintah: kurangi dan lewati instruksi berikutnya jika yang dikurangkan lebih dari yang dikurangi. Ini cukup untuk membangun algoritma apa pun.
Oleg Mazonka melangkah lebih jauh, ia mengembangkan tim
BitBitJump dan membuktikan bahwa itu selesai menurut Turing. Perintah berisi tiga alamat, menyalin satu bit dari yang pertama ke alamat memori kedua dan mentransfer kontrol ke alamat ketiga.
Setelah meminjam ide Oleg, untuk mempermudah pekerjaan, saya mengembangkan tim SumIfJump. Perintah berisi empat operan: A, B, C, D dan melakukan yang berikut: menambahkan data dari sel ke alamat A ke alamat B, jika nilainya lebih besar dari yang ditentukan *, ia pergi ke alamat C, jika tidak ia pergi ke alamat D.
Catatan* Dalam hal ini, 128 digunakan - setengah dari panjang genom.
Ketika operan A mengakses sel memori N0, data sedang input, dan ketika masuk ke sel N1, kemudian output.
Di bawah ini adalah kode SumIfJump pada FreePascal (analog Delphi gratis).
procedure RunProg(s: TData); var a, b, c, d: TData; begin Inc(NStep); if NStep > MaxStep then begin ProgResult := 'MaxStep'; Exit; end; a := s; b := s + 1; c := s + 2; d := s + 3; a := Prog[a]; b := Prog[b]; c := Prog[c]; d := Prog[d]; if a = 0 then begin ProgResult := 'Input'; Exit; end; if a = 1 then begin ProgResult := 'Output'; Exit; end; Prog[b] := Prog[b] + Prog[a]; if Prog[b] < ProgLength div 2 then RunProg(c) else RunProg(d); end;
SumIfJump mengimplementasikan kode modifikasi sendiri. Itu dapat menjalankan algoritma apa pun yang tersedia dalam bahasa pemrograman biasa. Kode ini mudah dimodifikasi dan tahan terhadap manipulasi apa pun.
Tugas sederhana
Jadi, AI kami hanya memiliki satu tim. Sementara tic-tac-toe adalah permainan yang sangat sulit baginya, dan saya mulai dengan yang lebih sederhana.
Bot memberikan nomor acak, dan AI harus membaca data dan memberikan jawaban. Jika angkanya lebih besar dari rata-rata (dari kisaran angka acak), AI harus memberikan angka kurang dari rata-rata dan sebaliknya.
Genom AI kami terdiri dari 256 sel dengan nilai dari 0 hingga 255. Setiap nilai adalah memori, kode, dan alamat. Jumlah langkah eksekusi kode dibatasi hingga 256. Operan dibaca satu demi satu.
Awalnya, genom dibentuk oleh satu set angka acak, sehingga AI tidak tahu apa yang harus dimainkan. Selain itu, ia tidak tahu bahwa ia perlu memasukkan dan mengeluarkan data secara berurutan, merespons bot.
Populasi dan seleksi
Populasi pertama terdiri dari 256 AI yang mulai bermain dengan bot. Jika AI melakukan tindakan yang benar, misalnya, meminta input data, dan kemudian menampilkan sesuatu, maka AI menerima poin. Semakin banyak tindakan yang benar, semakin banyak poin.
16 AI yang mencetak poin terbanyak memberi 15 keturunan dan terus berpartisipasi dalam permainan. Keturunan adalah mutan. Mutasi terjadi dengan mengganti satu sel acak dalam salinan induk dengan nilai acak.
Jika tidak ada AI yang mencetak poin dalam populasi pertama, populasi berikutnya akan terbentuk. Dan seterusnya sampai beberapa AI mulai melakukan tindakan yang benar dan memberikan keturunan yang "benar".
Evolusi
| N | Tonggak sejarah |
|---|
| 1 | AI tidak melakukan apa-apa. Program ini mengambil 256 langkah dan berakhir. |
| 2 | Mulai meminta data. |
| 3 | Dia mulai meminta data dan mengeluarkan sesuatu. Urutan permintaan dan tanggapan kacau. |
| 4 | Input dan output data terjadi secara berurutan, kadang-kadang terjadi kesalahan. Dalam setengah kasus, AI memberikan jawaban yang benar. |
| 5 | Memberikan jawaban yang benar secara teratur, tetapi terkadang kesalahan terjadi. |
| 6 | Memberi jawaban yang benar dalam 30 ribu iterasi. Pilihan diunggah. |
Di antara peristiwa-peristiwa penting, ribuan generasi berlalu. Program ini diluncurkan dalam beberapa utas pada Core i7. Perhitungannya memakan waktu sekitar 15 menit.
Poin menarik
- Ketika "pemimpin" AI membuat kesalahan acak dan tidak mendapatkan poin yang cukup, populasi mulai menurun, karena keturunan terbentuk dari orang tua "sekunder".
- Kebetulan di sungai dengan orang luar yang menandai waktu, mutasi yang sukses terjadi, memberikan peningkatan eksplosif dalam poin yang terakumulasi. Setelah itu, aliran ini menjadi pemimpin.
- Kadang-kadang untuk waktu yang lama tidak ada mutasi yang berhasil, dan bahkan 500 ribu generasi tidak cukup untuk menyelesaikan seleksi.
Kesimpulan
Kesimpulannya, saya melakukan hal yang sama dengan permainan tic-tac-toe. Ukuran genom digunakan seperti dalam kasus pertama. Jumlah langkah ditingkatkan menjadi 1024, dan ukuran populasi menjadi 64 (untuk perhitungan lebih cepat). Perhitungannya butuh waktu sedikit lebih lama. Semuanya terjadi sesuai dengan skenario yang sama.
Pada awalnya, AI bermain melawan "pengacak." Saya menelepon bot yang berjalan secara acak. Cukup cepat, AI mulai memukulinya, mengisi satu baris. Selanjutnya, saya mempersulit tugas dengan menambahkan sedikit alasan ke pengacak: untuk menduduki garis, jika mungkin, atau untuk mempertahankan. Namun, dalam kasus ini, AI menemukan kelemahan bot dan mulai memukulnya. Mungkin cerita tentang ini adalah topik untuk artikel terpisah.
Anak itu meminta saya untuk menulis sebuah program sehingga AI bermain di antara mereka sendiri, dan tidak dengan bot. Ada ide untuk melakukan hal yang sama untuk bermain catur atau pergi, namun, untuk ini saya sudah tidak punya cukup waktu.
Satu-satunya metode yang saya gunakan untuk mendapatkan individu baru adalah mutasi. Anda juga dapat menggunakan crossover dan inversi. Mungkin metode ini akan mempercepat mendapatkan hasil yang diinginkan.
Pada akhirnya, muncul ide: untuk memberikan AI kemampuan untuk mengelola semua proses pada PC dan memperjuangkan sumber daya komputer. Hubungkan PC ke Internet, dan gunakan kumpulan pertanian bitcoin lama sebagai kekuatan komputasi ...
Seperti yang dikatakan, melakukan percobaan serupa, blogger
Mikhail Tsarkov :
Mungkin mereka akan mengambil alih dunia, tetapi bagaimana jika?
Referensi
- Algoritma Genetika
- Copy Bit - Mesin Komputasi Sederhana / Oleg Mazonka
- URISC - Wikipedia
- Turing Completeness - Wikipedia