Pada tahun 2017, dua ilmuwan, John Aycock dari Kanada dan British Tara Copplestone, menerbitkan analisis tentang game klasik Entombed untuk konsol video game Atari 2600 . Mekanisme permainan ini, dirilis pada tahun 1982, sangat sederhana: arkeolog, yang dikendalikan oleh pemain, harus berjalan melalui katakomb yang bergulir dari bawah ke atas, menghindari zombie.
Atari 2600 hanya memiliki 128 byte RAM; namun, labirin yang tampaknya tak berujung itu baru di setiap peluncuran; dihasilkan dalam memori. Bagaimana para programmer mengaturnya? Berikut ini komentar dari Stephen Sidley, programmer yang membuat game ini 38 tahun yang lalu:
- . , , . , , , , , .
Wikipedia mencantumkan selusin algoritma berbeda untuk menghasilkan labirin. Yang paling menarik bagi konsol game adalah " algoritma Eller ", yang dibuat pada tahun 1982 yang sama oleh Martin Eller dari Microsoft. Algoritma Eller memungkinkan Anda membuat labirin terhubung baris demi baris tanpa loop, dan untuk menghasilkan labirin dengan ketinggian tak terbatas, cukup untuk menyimpan hanya beberapa baris terakhir dalam memori. Tampaknya inilah yang dibutuhkan Entombed! Namun sayang, algoritma Eller tidak kompatibel dengan mekanisme permainan scroller vertikal, karena dalam labirin yang dihasilkan Anda secara teratur harus melewati rintangan dari atas. Untuk menunjukkan ini, saya sedikit memodifikasi algoritma Eller sehingga labirin dibuat dalam matriks "dinding" dan "lorong", seperti dalam Entombed:
Algoritma yang lebih canggih menggunakan rekursi dan sejenisnya tidak akan muat dalam 128 byte RAM. Jadi, persyaratan untuk algoritma untuk Entombed adalah:
- Generasi demi baris labirin dengan ketinggian tak terbatas;
- Labirin yang dibuat harus memiliki bagian terputus sesedikit mungkin; (pemain memiliki kemampuan terbatas untuk "menerobos dinding", sehingga incoherence yang langka tidak menjadi masalah)
- Labirin yang dibuat harus terdiri terutama dari percabangan dan menghubungkan bagian vertikal - sehingga lorong labirin tidak memerlukan gerakan ke atas;
- Hanya beberapa garis yang dibuat terakhir yang harus digunakan untuk menghasilkan garis baru dari labirin. (Karena Atari 2600 tidak memiliki buffer video, semua garis labirin yang terlihat di layar harus disimpan dalam beberapa bentuk dalam memori utama 128 byte).
Siapa dan bagaimana membuat algoritma ini?
Dua ilmuwan yang menyebut diri mereka "arkeolog permainan video" memutuskan untuk memulai penelitian mereka dengan Entombed - sebuah permainan tentang seorang arkeolog di labirin. Selama penelitian mereka, mereka melacak Stephen Sidley dan menanyakan algoritma apa yang dia gunakan untuk menghasilkan labirin. Seperti yang telah disebutkan, Sidley mengatakan kepada mereka bahwa bahkan pembuat algoritma tidak dapat mengingat apa algoritmanya, dan Sidley sendiri, terlebih lagi. Kemudian para peneliti mencoba mencari "pecandu" yang menciptakan algoritma ini; bagian kedua dari kisah ini ditemukan dalam sebuah wawancara yang diterbitkan pada 2008:
Entombed [Duncan Muirhead] [Paul Allen Newell]. - , , , . , . , VCS [Atari 2600], . , . , , . , Towering Inferno, menggunakan bagian dari algoritma kami di sana, dan berhenti. Setelah saya pergi, biro hukum itu menyewa Stephen Sidley dan menyerahkan generator labirin kepadanya. Dia harus menghapus sebagian besar kode saya untuk memberi ruang bagi mekanik game. [Di Atari 2600, selain pembatasan parah pada jumlah RAM dan ROM, itu juga merupakan persyaratan bahwa generasi setiap baris piksel membutuhkan tepat 76 siklus catatan penulis ].
Sidley menyebutkan bahwa kode generator maze ditulis dalam 6502 perakitan tanpa komentar. Ini sendiri terlihat seperti suatu prestasi: seperti dicatat khim, di sana "serangkaian perintah sangat terbatas dan bengkok sehingga ketika menulis program, pertanyaan utama muncul," bagaimana saya bisa menulis sesuatu tentang keajaiban ini? " Namun demikian, para peneliti menggali kode permainan dan menemukan bahwa labirin dihasilkan sebagai berikut: untuk masing-masing dari delapan sel dari baris yang dihasilkan, lima sel yang sudah dihasilkan dipertimbangkan (tiga di atas dan dua di sebelah kiri), dan sesuai dengan "tabel ajaib" keadaan sel baru dipilih. (jalan, dinding, atau pilihan acak). Dua sel paling kiri selalu penuh dan tidak disimpan dalam memori. Setengah kanan labirin hanyalah bayangan cermin dari kiri.
Tabel misterius di jantung algoritme yang tidak terpecahkan
Sifat-sifat labirin yang dihasilkan tergantung pada keadaan set sel baru untuk masing-masing lima yang dihasilkan sebelumnya. Tabel dijahit menjadi Entombed, banyak peneliti bingung: "Kami tidak melihat ada hukum, bahkan ketika kami memiliki beberapa cara untuk menyajikannya dalam bentuk peta Karnaugh ." Sidley berkata dengan nada yang sama, "Bagi saya itu tetap menjadi misteri: saya tidak bisa mengungkapnya, dan menggunakannya sebagai kotak hitam." Namun, tidak adanya keteraturan dalam tabel sedikit berlebihan: misalnya, pada peta Karnot, Anda dapat melihat bahwa ketika c = 1 (dinding di kiri atas sel saat ini) X = 1 (dinding di sel saat ini) tidak akan dihasilkan .
BBC dalam laporannyatentang "arkeologi digital", dia menggunakan ungkapan yang lebih dramatis: "Tabelnya benar-benar cerdik: setiap kali Anda memulai permainan, labirin baru dibuat, yang dengannya Anda bisa pergi dari awal hingga akhir. Jika nilai-nilai dalam tabel ini bahkan sedikit berbeda, maka kemungkinan besar labirin tersebut ternyata tidak bisa dilewati. Itu hanya tidak bisa dijelaskan. " The repost di hackaday.com diformulasikan bahkan lebih percaya diri: "Sebuah meja misterius selalu menciptakan labirin lumayan, tetapi jika Anda mengubah bit di dalamnya, dan teka-teki akan menjadi tidak larut." Faktanya, labirin tidak selalu koheren, seperti yang bisa dilihat dalam video game ; dan perubahan kecil dalam tabel tidak memiliki efek nyata pada labirin yang dihasilkan: Saya membuat versi JavaScript, di mana Anda dapat bermain dengan "meja misterius" sendiri - ubah dengan benar "saat bepergian" dan saksikan bagaimana labirin berubah sebagai hasilnya. Mungkin, jaminan konektivitas labirin, yang disebutkan Paul Newell dalam wawancaranya, hilang bersamaan dengan bagian kode yang dihapus.
Arkeologi permainan video
John Aycock berkomentar tentang bagaimana Entombed menjadi objek penelitiannya: ia menyiapkan tugas rekayasa terbalik untuk murid-muridnya, dan memilih permainan yang relatif tidak banyak diketahui, karena untuk permainan populer siswa dapat menemukan kode yang sudah diuraikan di internet. Jika penemuan luar biasa seperti itu ditemukan dalam permainan yang dipilih secara acak, apakah itu berarti bahwa di hampir setiap permainan waktu itu akan ada solusi pemrograman yang brilian, Anda hanya perlu menggali sedikit lebih dalam? Stephen Sidley membandingkan desain untuk Atari 2600, dengan set instruksi yang sedikit, 128 byte RAM, dan 76 jam per baris piksel, untuk "mendaki Gunung Everest tanpa tangki oksigen" : keterbatasan platform memaksa pemrogram untuk menemukan algoritma yang cerdas.
Menggali lebih dalam bukan hanya metafora. Penelitian video game klasik diperumit oleh rapuhnya media tempat mereka merekam dan memperlakukan game lama sebagai sampah yang tidak menarik. Pada tahun 1983, Atari membuang 47 ton kartrid Atari 2600 ke tempat pembuangan sampah - tidak kurang dari selusin truk penuh! Hancur oleh rol aspal dan dituangkan dengan beton, kartrid ini diletakkan selama tiga puluh tahun sampai, pada tahun 2014, "arkeolog digital" menerima izin untuk menggali dan mengambil kartrid yang masih hidup. Tak satu pun dari kartrid gali bekerja, tetapi setidaknya salah satu dari mereka dikembalikan dengan menyolder komponen.
Perilaku Atari, yang menuangkan beton ke dalam kartrid untuk melindungi mereka dari "pencuri" - sangat khas dari pemegang hak cipta yang akan lebih mudah menyerahkan pekerjaan mereka ke pelupaan kekal daripada menderita "kehilangan keuntungan" dari fakta bahwa kekayaan intelektual mereka akan diberikan kepada seseorang secara gratis. Tetapi mungkin belum terlambat untuk melindungi "lapisan budaya virtual" abad ke-20 dengan membiarkan penyalinan program secara gratis yang telah lama kehilangan nilai komersialnya?
