“Dormammu, aku setuju”: suatu algoritma untuk kerja sama yang saling menguntungkan dengan seseorang

Refleksi pada topik kecerdasan buatan telah mengunjungi pikiran orang-orang hebat selama berabad-abad. Dengan berlalunya waktu dan perkembangan teknologi, pemikiran telah berubah menjadi implementasi, teori menjadi praktik, dan fiksi ilmiah menjadi masa depan umat manusia yang sangat nyata. Esensi utama AI adalah membantu orang. Dengan kata lain, mesin pintar harus melayani seseorang dalam ukuran penuh, tanpa melanggar hukum dasar robotika, yang diungkapkan oleh Isaac Asimov yang terkenal kejam. Tetapi interaksi seperti itu, jika Anda alasannya turun ke bumi, hanya memiliki satu vektor: kata orang - AI dilakukan. Artinya, karya kecerdasan buatan ditujukan untuk kepentingan manusia saja. Tetapi bagaimana jika AI berpikir sejalan dengan kebaikan untuk kedua sisi interaksi? Bagaimana cara mengajar mobil untuk berkompromi, bernegosiasi, dan bahkan tawar-menawar dengan seseorang? Nah, justru untuk pertanyaan-pertanyaan inilah penelitian hari ini memberikan jawaban, di mana suatu algoritma diciptakan yang memungkinkan mesin untuk mencapai kesepakatan yang saling menguntungkan dengan seseorang. Mari kita melihat lebih dekat masalah ini. Ayo pergi.

Ide penelitian

Para peneliti telah mencatat bahwa sejak Turing mulai berbicara tentang kecerdasan buatan, manusia telah mencoba untuk menciptakan sebuah mesin yang dapat melampaui itu dalam sesuatu. Dengan satu atau lain cara, kita semua akrab dengan berbagai kontes, kompetisi, dan eksperimen ketika seseorang bersaing dengan mesin (catur, poker, dan bahkan seni bela diri). Namun, sampai sekarang sangat sedikit perhatian yang diberikan pada jenis interaksi yang berbeda antara manusia dan mesin. Lagi pula, tidak selalu dalam hidup hanyalah kemenangan atau kekalahan. Terkadang konsensus sangat dibutuhkan ketika kebutuhan dan / atau keinginan dua pihak terpenuhi.

Menganggap pekerjaan AI secara eksklusif dari posisi “ya atau tidak” adalah salah, karena selalu ada opsi “mungkin”.

Para ilmuwan telah berhasil membuat algoritma yang dapat mengevaluasi situasi, menimbang pro dan kontra, memprioritaskan dan mencapai kompromi. Untuk memeriksa operasi algoritma, permainan stokastik berulang * digunakan .

Gim stokastik * adalah gim berulang dengan satu atau lebih pemain, ketika kondisinya terus berubah secara acak.

Membuat algoritma yang dapat bekerja dalam kondisi "mengambang" seperti itu bukanlah tugas yang mudah. Agar dapat bekerja secara efisien, algoritma harus memiliki beberapa fitur. Lebih jauh tentang mereka secara lebih rinci.

Pertama, algoritme tidak boleh berorientasi pada subjek, yaitu harus bekerja dalam jumlah skenario yang tidak terbatas (dalam hal ini, permainan). Fitur ini disebut oleh para ilmuwan "universalitas."

Kedua, algoritma harus belajar untuk membangun hubungan yang sukses dengan orang / algoritma tanpa terlebih dahulu membiasakan diri dengan perilaku mereka. Ini adalah "fleksibilitas." Untuk mencapai hal ini, algoritma harus memperhitungkan bahwa hampir selalu lawan-lawannya mematuhi perilaku operasional, yaitu, ingin menggunakan algoritma secara eksklusif untuk keuntungannya sendiri. Akibatnya, ia harus menentukan kapan dan bagaimana cara menarik untuk bekerja sama, orang yang kemungkinan besar tidak mau bekerja sama.

Dan akhirnya, ketiga, algoritma harus bertindak cepat, terutama saat bermain dengan seseorang. Fitur ini disebut "kecepatan belajar."

Dengan kata-kata, semuanya sangat indah, jelas dan sederhana. Namun pada kenyataannya, pencapaian karakteristik seperti itu sarat dengan kesulitan. Belum lagi fakta bahwa kemampuan beradaptasi dengan lawan bisa diperumit dengan fakta bahwa lawan sendiri tahu bagaimana beradaptasi. Ini adalah masalah, karena dua algoritma adaptif, meskipun semua upaya mereka untuk beradaptasi satu sama lain, tidak dapat mencapai kompromi.

Para ilmuwan juga mencatat bahwa selama interaksi antara dua orang, salah satu alat penting untuk mencapai hasil yang saling menguntungkan adalah hal-hal yang sulit dikaitkan dengan mesin, seperti intuisi, emosi, naluri, dan banyak lagi. Telah terbukti bahwa "pembicaraan murah" sangat menyertai hasil yang saling menguntungkan.

Bicara murah * - dalam teori permainan, ini adalah interaksi antara pemain yang tidak secara langsung mempengaruhi hasil permainan. Dengan kata lain, "percakapan di luar topik."

Peneliti memutuskan untuk menerapkan ini dalam algoritma mereka, yang membantunya lebih baik dalam mengatasi perhitungan situasi yang rumit dan mengembangkan ide umum tentang situasi dengan seseorang. Meskipun sampai sekarang masih belum jelas bagaimana algoritma akan menerapkan "keterampilan" tersebut dalam hubungannya dengan fitur utamanya (fleksibilitas, universalitas, kecepatan belajar).

Tujuan utama dari penelitian ini adalah untuk mempelajari sebanyak mungkin algoritma yang ada, untuk mengembangkan algoritma berdasarkan pembelajaran mesin dengan mekanisme untuk menanggapi sinyal dan menghasilkan mereka pada tingkat yang dapat dipahami manusia, dan untuk melakukan banyak permainan game eksperimental untuk menunjukkan kemampuan belajar dari algoritma dan kemampuannya untuk beradaptasi dengan lawan yang berbeda (orang-orang). atau algoritma lainnya).

Perilaku dan hasil penelitian

Algoritma perilaku strategis dalam permainan berulang hadir dalam banyak aspek masyarakat: ekonomi, biologi evolusi, AI, dll. Saat ini, banyak algoritma semacam itu telah dibuat, yang masing-masing memiliki kelebihannya sendiri. Secara alami, para ilmuwan memutuskan untuk menggunakannya untuk mengembangkan algoritme mereka. Dengan demikian, 25 algoritma dipilih.

Enam indikator kinerja diidentifikasi berdasarkan tiga opsi permainan: 100, 1000 dan 50.000 putaran.

Indikator kinerja:

• nilai rata-rata Round-Robin * ;
• hasil skor terbaik;
• hasil skor terburuk;
• dinamika replikator * ;
• turnamen grup 1;
• turnamen grup 2.

Round-Robin * - jenis interaksi permainan, ketika selama putaran masing-masing peserta secara bergantian bermain dengan semua peserta lainnya.

Persamaan replikator * adalah dinamika permainan nonlinier monoton deterministik yang digunakan dalam teori permainan evolusioner.

Indikator pertama (nilai rata-rata Round-Robin) memungkinkan kita untuk memahami seberapa baik algoritma mampu membangun hubungan yang menguntungkan dengan berbagai mitra game.

Indikator kedua (skor terbaik) adalah jumlah algoritme mitra dalam game yang digunakan algoritme yang diselidiki untuk mendapatkan jumlah poin tertinggi. Ini dinyatakan sebagai persentase. Indikator ini mencerminkan seberapa sering algoritma akan menjadi pilihan sambutan, mengingat informasi tentang algoritma dari mitra permainan.

Indikator ketiga (hasil terburuk berdasarkan poin) adalah penilaian kemampuan algoritma untuk mengikat kerugiannya (misses, error).

Tiga indikator yang tersisa bertujuan untuk menentukan stabilitas algoritma untuk kelompok populasi yang berbeda.

Misalnya, turnamen (grup-1) adalah serangkaian permainan yang algoritmanya dibagi menjadi 4 grup. Para pemimpin dari setiap grup maju ke final, di mana satu-satunya pemenang ditentukan. Tetapi dalam turnamen grup-2, dua algoritma terbaik dipilih dari masing-masing grup, yang pergi ke semifinal, dan kemudian pemenang pergi ke final, di mana satu-satunya algoritma terbaik ditentukan.

Menurut para ilmuwan, tidak ada algoritma yang dipilih (25 buah) yang sebelumnya berpartisipasi dalam verifikasi skala besar (banyak mitra dan indikator yang diukur). Pemeriksaan semacam itu menunjukkan seberapa baik masing-masing algoritma bekerja dalam permainan normal dengan 2 peserta, dan tidak "diprogram" untuk skenario tertentu.


Tabel 1: Hasil eksperimen yang melibatkan 25 algoritma perilaku strategis yang berbeda.

Hasil yang diperoleh hanyalah alat yang memungkinkan Anda untuk lebih memahami pro dan kontra dari algoritma tertentu. Sebagai contoh, algoritma gTFT, WSLS, Mem-1, dan Mem-2 menunjukkan hasil yang sangat baik dalam "dilema tahanan" * .

Dilema tahanan * - dalam teori permainan, keadaan di mana pemain tidak selalu siap untuk bekerja sama, bahkan jika itu akan bermanfaat bagi mereka. Dalam hal ini, pemain ("tahanan") memiliki kepentingannya sendiri dalam prioritas, dan ia tidak memikirkan keuntungan orang lain.

Namun, algoritma yang sama ini menunjukkan hasil yang buruk di semua game 2x2, yang menunjukkan inefisiensi dalam interaksi yang lebih lama. Karena itu, mereka tidak dapat beradaptasi dengan perilaku pasangan (pemain lain).

Pengamatan lucu adalah fakta bahwa algoritma Exp3, GIGA-WoLF dan WMA, yang merupakan dasar untuk algoritma World Poker Championship, juga menunjukkan hasil yang buruk. Yang cukup jelas, karena algoritma poker seharusnya tidak bekerja sama dengan pemain lain, tetapi mengungguli dan mengalahkan mereka.

Jika kami mempertimbangkan semua indikator secara keseluruhan, maka satu algoritme menonjol - S ++, yang menunjukkan dirinya dengan sempurna di semua jenis permainan dengan semua kemungkinan kombinasi dicentang. Selain itu, perlu dicatat bahwa untuk sebagian besar algoritma, pengembangan perilaku kerja sama terjadi hanya setelah ribuan putaran. Untuk S ++, proses ini hanya memakan waktu beberapa putaran, yang menjadikannya pilihan yang bagus, mengingat pentingnya indikator ini dalam permainan yang melibatkan bukan algoritma, tetapi orang yang hidup. Semakin cepat algoritma yang diuji “menyadari” perlunya dan keuntungan dari kerja sama dan kompromi, semakin mudah dan cepat akan dapat mencapainya.


Hasil percobaan "S ++ terhadap manusia."

Interaksi S ++ dengan algoritma lain menunjukkan hasil yang baik, oleh karena itu, perlu untuk memeriksa bagaimana S ++ akan berperilaku dalam bekerja dengan orang yang hidup.

Eksperimen (4 game berulang 50 atau lebih putaran) melibatkan algoritma S ++ dan MBRL-1, serta sekelompok orang. Hasil percobaan ini terlihat dalam grafik di atas. Kami melihat bahwa pembentukan kerjasama S ++ dengan salinannya sangat baik, tetapi proses ini tidak konsisten dengan orang. Selain itu, S ++ berhasil mencapai kerjasama jangka panjang dengan seseorang hanya dalam <30% putaran. Bukan hasil yang paling menggembirakan, tetapi orang-orang yang bermain dengan orang-orang juga gagal menjalin kerja sama jangka panjang.

Meskipun S ++ menonjol di antara algoritma lainnya, ini tidak memungkinkannya untuk menjadi pemenang yang jelas dalam penelitian ini. Tidak satu pun dari 25 algoritma yang dapat menunjukkan kemampuan untuk membangun hubungan kerja sama jangka panjang dengan pemain manusia.

S #: koperasi manusia dan algoritma

Seperti disebutkan sebelumnya, aspek seperti "panggilan murah" memainkan peran penting dalam mencapai kerja sama jangka panjang antara para pihak, namun teknik seperti itu belum pernah diterapkan sebelumnya di salah satu permainan di atas. Oleh karena itu, para ilmuwan memutuskan untuk membuat versi mereka sendiri, yang akan memungkinkan para pemain untuk menggunakan teknik ini, tetapi sampai batas tertentu - 1 pesan di awal setiap putaran.

Bagi seseorang, percakapan seperti itu wajar. Namun, untuk mesin yang ditujukan untuk menyelesaikan masalah dan akan melakukan ini, apa yang logis, bentuk interaksi seperti itu asing. Gagasan memperkenalkan perilaku semacam itu secara langsung mengarahkan para ilmuwan ke konsep seperti "AI yang Dapat Dijelaskan" ("AI yang dapat dijelaskan"), ketika tindakan mesin itu mudah dimengerti oleh manusia. Masalahnya adalah sebagian besar algoritma berbasis pembelajaran mesin memiliki representasi internal tingkat rendah, yang sulit untuk diungkapkan pada tingkat yang dapat dipahami oleh manusia.

Untungnya, struktur internal S ++ memiliki tingkat yang sangat tinggi, yang memungkinkannya untuk digunakan sebagai dasar untuk penerapan teknik "pembicaraan murah". S ++ memperkenalkan kerangka komunikasi yang memungkinkan Anda menghasilkan dan merespons "panggilan murah".


Bentuk baru dari algoritma S ++ telah disebut S #.

Gambar (a) menunjukkan skema algoritme, dan (b ) menunjukkan skema interaksi dengan mitra dalam permainan menggunakan teknik "pembicaraan murah". Juga pada b, kita dapat membiasakan diri dengan frasa yang dapat dihasilkan oleh algoritma S #, dan respons seperti apa yang dia harapkan untuk frasa tertentu.

Dengan demikian, S # dapat menanggapi "sinyal" (frasa dan tindakan) dari pemain mitra, yang memungkinkannya untuk memutuskan taktik yang akan diterapkan selanjutnya. Bersama dengan tingkat tinggi pembelajaran mandiri dari algoritma S ++ asli, algoritma yang dihasilkan dapat menciptakan hubungan jangka panjang yang saling menguntungkan dengan pemain, orang, atau algoritma lainnya.

Untuk memverifikasi pernyataan ini, para ilmuwan mengadakan percobaan dengan 220 orang. Sebanyak 472 pertandingan berulang dimainkan. Teknik "pembicaraan murah" juga termasuk dalam percobaan, tetapi tidak selalu. Dan identitas para pemain disembunyikan, jadi tidak ada seorang pun (baik algoritma maupun orang-orang) yang tahu dengan siapa mereka bermain.


Hasil percobaan melibatkan 220 orang.

Ketika "pembicaraan murah" tidak dimasukkan dalam proses game, interaksi manusia-orang atau orang-S tidak mengarah pada kerja sama jangka panjang. Ketika teknik ini dimasukkan dalam permainan, indikator kerja sama berlipat ganda.



Grafik (a) menunjukkan frasa seperti apa yang digunakan selama permainan seseorang dan algoritma S # (benci, ancaman, kontrol, pujian atau perencanaan).

Setelah percobaan, semua peserta diminta untuk mengevaluasi tingkat kecerdasan pasangan mereka dalam permainan, seberapa jelas niat mereka dan kegunaan berinteraksi dengan mereka. Hasil survei pada grafik (b) . Yang lebih menghibur adalah jadwalnya. Ini menunjukkan persentase berapa kali seseorang atau algoritma menganggap pasangannya dalam permainan sebagai manusia. Seperti yang Anda lihat, sebagian besar peserta manusia merasa bahwa S # adalah seseorang.

Para ilmuwan juga mencatat bahwa hasil S # bahkan lebih baik jika dibandingkan dengan bagaimana orang-orang dan pasangan S # -S # berinteraksi. Tingkat terjadinya hubungan kerja sama jangka panjang antara seseorang dan S # kira-kira pada tingkat yang sama dengan pasangan orang-orang. Dan pasangan S # -S # tanpa menggunakan teknik "pembicaraan murah" memiliki hasil yang jauh lebih baik daripada pasangan orang-orang, yang memiliki kesempatan untuk menggunakannya.

Meringkas semua hal di atas, algoritma S # menunjukkan hasil yang dapat setara dengan hasil interaksi antara orang-orang.

Game stokastik berulang

Permainan dengan tipe normal memungkinkan untuk memahami bahwa algoritma S # adalah vektor penelitian yang menjanjikan. Namun, permainan seperti itu terbatas, mereka lebih abstrak. Oleh karena itu, para ilmuwan memutuskan untuk menggunakan permainan stokastik berulang di mana para peserta harus memisahkan balok dengan berbagai bentuk dan warna. Untuk algoritma S #, frasa “Ayo berkolaborasi” dan “Saya mendapatkan lebih banyak poin” ditambahkan. Selain itu, S # terbatas dalam penggunaan teknik "pembicaraan murah" - ia dapat menggunakan frasa, tetapi tidak dapat menanggapi frasa dari pemain manusia.


Skema permainan dengan blok multi-warna (persegi, lingkaran, dan segitiga).

Inti dari permainan ini adalah sebagai berikut. Setiap pemain memiliki satu set 9 blok (berbeda, tentu saja). Setiap belokan, pemain melepaskan 1 blok dari setnya hingga ia hanya memiliki 3. Tiga blok ini harus memenuhi persyaratan (bentuk / warna yang sama atau bentuk dan warna yang berbeda pada saat yang sama). Setiap blok membutuhkan sejumlah poin (poin) tertentu. Jika blok tidak cocok, maka angka ini menjadi negatif. Diagram di atas menunjukkan 5 opsi untuk hasil permainan.


Penggunaan dan tidak digunakannya "panggilan murah".

Saat bermain di antara orang-orang, penggunaan "pembicaraan murah" tidak banyak mempengaruhi hasilnya. Namun, teknik ini sangat meningkatkan hasil dari algoritma S # dalam game dengan seseorang.

Perbedaan S # dari algoritma lain

Algoritma S # melampaui semua subjek lain, tetapi mengapa? Apa sifat dari algoritma ini yang membedakannya dari sejumlah pesaing? Ilmuwan telah menghitung sebanyak tiga.

Pertama, itu adalah kemampuan untuk menghasilkan dan merespons sinyal yang tepat (frasa dan tindakan) yang dapat dipahami oleh manusia. Ini membuat algoritma ini sangat fleksibel, dapat berkembang tergantung pada situasinya. Dan, tentu saja, ini memungkinkan Anda untuk membentuk hubungan jangka panjang yang saling menguntungkan dengan pemain lain.

Kedua, S # menggunakan serangkaian strategi yang beragam, yang memungkinkan Anda untuk beradaptasi dengan pemain mitra yang berbeda dan berbagai jenis permainan. Pada saat yang sama, algoritma yang dirancang untuk bekerja secara efisien hanya dalam satu skenario tertentu tidak dapat bekerja secara efektif di luar "zona nyaman" mereka.

Ketiga, algoritma S # mempertahankan keadaan saling menguntungkan, sementara algoritma lainnya, setelah menerima apa yang mereka inginkan, beralih ke strategi yang berbeda.


Grafik durasi keadaan kerja sama yang saling menguntungkan.

Seperti yang dapat dilihat dari grafik di atas (a) , S # membangun koneksi yang saling menguntungkan dengan pemain lebih awal dari algoritma lainnya. Ini juga memiliki keadaan kerja sama yang saling menguntungkan dengan jumlah putaran yang jauh lebih besar daripada algoritma yang bersaing (grafik (b) ).

Fleksibilitas S # terlihat jelas dari grafik (c) , di mana kita melihat bahwa ia mencapai tujuan lebih sering daripada yang lain, terlepas dari jenis permainan atau mitra.

Cukup tidak biasa adalah pernyataan para ilmuwan bahwa algoritma S # mereka telah mempelajari kesetiaan. Faktanya adalah bahwa setelah menjalin kerja sama dalam pasangan S # -S #, algoritme tidak terburu-buru untuk mematahkannya, bahkan ketika tidak ada banyak manfaat dalam hal ini. Pada saat yang sama, pada pasangan pria-ke-pria, kerja sama sering putus segera setelah mencapai manfaat jangka pendek yang diperlukan. Perilaku ini secara alami menyebabkan hasil yang buruk di akhir pertandingan untuk kedua belah pihak.

Mereka yang ingin membiasakan diri dengan laporan para ilmuwan dapat menemukannya di sini .

Bahan penelitian tambahan tersedia di sini .

Epilog

Studi ini sangat berbeda dari yang lain dalam hal ini tidak bertujuan untuk menciptakan AI yang mampu mengalahkan seseorang dalam sesuatu, tetapi pada menciptakan AI yang mampu dan bersedia untuk mencapai konsensus. Apakah ini berarti bahwa mesin pintar akan menjadi lebih manusiawi berkat algoritma ini? Mungkin , , , , .

, S# «». , . , .

Terima kasih telah tinggal bersama kami. Apakah Anda suka artikel kami? Ingin melihat materi yang lebih menarik? Dukung kami dengan melakukan pemesanan atau merekomendasikannya kepada teman-teman Anda, diskon 30% untuk pengguna Habr pada analog unik dari server entry-level yang kami temukan untuk Anda: Seluruh kebenaran tentang VPS (KVM) E5-2650 v4 (6 Cores) 10GB DDR4 240GB SSD 1Gbps dari $ 20 atau bagaimana membagi server? (pilihan tersedia dengan RAID1 dan RAID10, hingga 24 core dan hingga 40GB DDR4).

3 Dell R630 — 2 Intel Deca-Core Xeon E5-2630 v4 / 128GB DDR4 / 41TB HDD 2240GB SSD / 1Gbps 10 TB — $99,33 , , .

Dell R730xd 2 kali lebih murah? Hanya kami yang memiliki 2 x Intel Dodeca-Core Xeon E5-2650v4 128GB DDR4 6x480GB SSD 1Gbps 100 TV dari $ 249 di Belanda dan Amerika Serikat! Baca tentang Cara Membangun Infrastruktur Bldg. kelas menggunakan server Dell R730xd E5-2650 v4 seharga 9.000 euro untuk satu sen?