Game kompetitif tak tertandingi peer-to-peer of chance? [Tutup]

15

Saya bertanya-tanya - apakah ada game yang pernah dibuat yaitu:

  • peer-to-peer tanpa satu rekan ditunjuk sebagai tuan rumah
  • kompetitif (tidak kooperatif, pemain bermain melawan satu sama lain)
  • terbukti adil (tidak ada kemungkinan pemain selingkuh)
  • Jangan memberi pemain lain informasi lebih dari yang mereka butuhkan (misalnya, tidak mengungkapkan rahasia pemain lain bahkan untuk aplikasi yang sedang berjalan)

Contoh dari permainan seperti itu adalah permainan poker di mana setiap pemain dan permainan mereka hanya bisa mengetahui tangan mereka sendiri, tetapi bukan tangan pemain lain tanpa mengandalkan siapa pun dari mereka yang menjadi tuan rumah permainan. Saya tahu ada beberapa permainan di luar sana yang terbukti adil, tetapi semua yang saya tahu ada dalam konfigurasi server-klien.

ThePiachu
sumber
1
"peer-to-peer" dan "tidak ada kemungkinan pemain selingkuh" - Itu tidak mungkin.
Kikaimaru
7
@Kikaimaru Anda salah.
sam hocevar
@Kikaimaru Sebenarnya, saya memiliki beberapa konsep tentang bagaimana ini bisa bekerja, tapi saya ingin bertanya dulu sebelum mencoba untuk menemukan kembali roda (oke, dalam hal ini mungkin pesawat).
ThePiachu
2
Saya sangat ragu bahwa ada metode yang akan mencegah kecurangan pada tingkat yang server-client melakukannya. Pemain dapat, misalnya, tahu bahwa pemain lain curang dan berhenti bermain - tanpa perlu kode apa pun (atau Anda bisa menghentikan permainan), tetapi apakah itu "tidak ada kemungkinan kecurangan"?
Kikaimaru
@Kikaimaru Jika protokol menegakkan kebenaran, mencoba menipu sama dengan tidak bermain sama sekali - jika ada lebih dari dua pemain, pemain lain masih dapat terus bermain dan upaya curang akan diabaikan tidak seperti paket IP yang tidak valid. menjadi.
sam hocevar

Jawaban:

19

Saya tidak tahu apakah game seperti itu telah dibuat, tetapi mereka memang berteori. Beberapa makalah telah dipublikasikan tentang topik ini. Anda mungkin ingin meneliti skema komitmen yang menawarkan penjelasan tentang bagaimana dua pihak yang tidak setuju dapat membalik koin sementara secara fisik jauh (lihat juga makalah 1981 ini: Coin Flipping by Telephone ).

Salah satu makalah yang sangat teliti adalah misalnya Permainan Kartu Perdagangan Peer-to-Peer yang Cheat-Proof :

Kami mengusulkan protokol peer-to-peer cheat-proof untuk menerapkan permainan kartu perdagangan online. Kami memecah tindakan umum untuk semua TCG dan menjelaskan bagaimana mereka dapat dieksekusi antara dua pemain tanpa perlu wasit pihak ketiga (yang biasanya membutuhkan server yang tidak bias). Dalam setiap aksi, pemain dicegah melakukan kecurangan atau jika mereka berbuat curang, lawan akan dapat membuktikan bahwa mereka telah melakukannya . Kami menyimpulkan dengan menunjukkan bagaimana metode ini aman dan bagaimana mereka dapat dicampurkan untuk gaya TCG lain dan game peer-to-peer lainnya.

Juga Main Curang-Bukti Bermain untuk Gaming Terpusat dan Peer-to-Peer :

Kami mengusulkan protokol yang memiliki jaminan anti-kecurangan yang terbukti, terbukti aman dan hidup , tetapi menderita penalti kinerja. Kami kemudian mengembangkan versi diperpanjang dari protokol ini, yang disebut sinkronisasi tidak sinkron, yang menghindari penalti, tidak memiliki server, menawarkan jaminan anti-kecurangan yang terbukti, kuat di hadapan hilangnya paket, dan memberikan peningkatan kinerja komunikasi yang signifikan. Teknik ini berlaku untuk fitur permainan umum serta teknik pengelompokan dan berbasis sel untuk game multipemain masif. Khususnya, kami menyediakan protokol bukti nol pengetahuan sehingga pemain berada dalam kisaran spesifik satu sama lain, dan sebaliknya tidak memiliki gagasan tentang jarak mereka. Klaim kinerja kami didukung oleh analisis menggunakan simulasi berdasarkan jejak game nyata.

sam hocevar
sumber
1
Juga lihat halaman Poker Mental di Wikipedia - en.wikipedia.org/wiki/Mental_poker . Telah ada diskusi di forum Bitcoin tentang aplikasi potensial dari bitcointalk.org/index.php?topic=1487.0
liamzebedee
Tautan hebat @liamzebedee. Artikel itu memiliki cukup banyak algoritma yang tepat yang membuat poker bekerja dengan baik peer-to-peer.
captncraig
4

Meskipun bukan game kebetulan, saya mengembangkan game AIR yang dekat dengan kebutuhan Anda.

  1. Dikembangkan menggunakan protokol multicast RTMFP Flash. Tidak ada klien yang dianggap sebagai tuan rumah.
  2. Sistem kompetitif berbasis fisika.
  3. Memverifikasi input lawan dan mendiskualifikasi game pada data yang tidak valid.
  4. Tidak mengirimkan informasi fisika tertentu karena alasan bandwidth / latensi (ini juga menonaktifkan metode curang tertentu).

Namun, harap diperhatikan ...

Saya menganggap "tidak ada kemungkinan ... menipu" pernyataan yang salah. Jika Anda tidak mengontrol semua aspek (perangkat keras & perangkat lunak), maka curang dimungkinkan.

Meskipun bukan permainan, saya pikir jaringan Bitcoin adalah contoh utama dari apa yang Anda cari.

Edit

Saya akan sedikit memperluas pertanyaan utama Anda.

Pertama, saya tidak bisa melihat permainan yang membutuhkan kondisi "terbukti adil" tanpa beberapa tingkat persyaratan otoritatif. Dari papan peringkat hingga pembayaran mikro, sistem dan otoritas terpusat berjalan bersama.

Kedua, game contoh terbaik yang bisa saya pikirkan adalah game Pokemon awal. Meskipun logistik jaringan dalam mungkin bukan peer-to-peer, itu mengikuti prinsip yang sama.

Akhirnya, platform seluler khusus dipasang untuk game peer-to-peer. Saya menganggap bidang ini sangat kurang, itulah sebabnya saya saat ini mengembangkan lini permainan peer-to-peer.

Nathan Goings
sumber
Ya, saya mungkin memiliki pengalaman dengan Bitcoin ... bitcoin.stackexchange.com/users/323/thepiachu ;)
ThePiachu
1

Beberapa potong yang mungkin membantu, tergantung pada kasus penggunaan:

Jika Anda perlu mendapatkan input simultan dari pengguna tanpa kemungkinan seseorang dapat menggunakan informasi untuk keuntungan mereka sebelum waktunya, Anda dapat menggunakan skema komitmen. Pada dasarnya ini adalah:

  1. Kedua pemain memberikan hash tindakan yang ingin mereka ambil.
  2. Setelah keduanya memberikan komitmen, keduanya dapat memberikan tindakan plaintext.
  3. Plaintext dapat dibandingkan dengan hash untuk memverifikasi bahwa tidak ada yang mengubah jawaban mereka setelah mempelajari tindakan orang lain.

Ini dapat digunakan untuk berbagai hal, termasuk nomor acak bersama (keduanya memberikan bilangan bulat melalui komitmen dan menggabungkannya setelah berbagi untuk mendapatkan nilai bersama.)

Namun itu tidak cukup untuk permainan seperti poker, karena ini membutuhkan kartu untuk diketahui hanya oleh satu orang, sambil terus dapat menggambar dari dek bersama. Wikipedia memiliki algoritma yang cukup baik untuk pengacakan bersama menggunakan skema di mana kedua pemain mengenkripsi setiap kartu secara terpisah beberapa kali. Ini mengatur situasi di mana 2 kunci diperlukan untuk mendekripsi kartu yang diberikan, dan kedua pemain memiliki 1. Artikel ini menyebutkan masalah kinerja, tapi saya tidak berpikir AES atau sejenisnya sangat mahal pada skala yang diperlukan untuk 2 pemain poker.

Jika saya mendesain algoritma saya akan meminta pemain menghitung nilai acak di awal permainan untuk digunakan sebagai seed untuk semua sisa operasi dan berbagi hash dari nilai itu. Dengan begitu mereka dapat membagikan nilai itu setelah pertandingan, dan Anda dapat memverifikasi bahwa mereka mengikuti protokol dengan benar, tanpa gangguan.

captncraig
sumber