Bagaimana mungkin game deterministik dalam menghadapi floating-point non-determinisme?

Untuk membuat game seperti jaringan RTS, saya telah melihat sejumlah jawaban di sini menyarankan untuk membuat game sepenuhnya deterministik; maka Anda hanya perlu mentransfer tindakan pengguna satu sama lain, dan ketinggalan apa yang ditampilkan sedikit untuk "mengunci" input semua orang sebelum bingkai berikutnya diberikan. Maka hal-hal seperti posisi unit, kesehatan, dll. Tidak perlu terus diperbarui melalui jaringan, karena simulasi setiap pemain akan persis sama. Saya juga mendengar hal yang sama yang disarankan untuk membuat replay.

Namun, karena perhitungan floating-point adalah non-deterministik antar mesin, atau bahkan antara kompilasi berbeda dari program yang sama pada mesin yang sama, apakah ini benar-benar mungkin dilakukan? Bagaimana kita mencegah fakta itu menyebabkan perbedaan kecil antara pemain (atau tayangan ulang) yang bergejolak di sepanjang permainan ?

Saya pernah mendengar beberapa orang menyarankan menghindari angka floating-point sama sekali dan menggunakan intuntuk mewakili hasil bagi sebagian, tetapi itu tidak terdengar praktis bagi saya - bagaimana jika saya perlu, misalnya, mengambil kosinus sudut? Apakah saya serius perlu menulis ulang seluruh perpustakaan matematika?

Perhatikan bahwa saya terutama tertarik pada C #, yang sejauh yang saya tahu, memiliki masalah yang sama persis seperti C ++ dalam hal ini.

Apakah floating-point deterministik?

Saya melakukan banyak membaca tentang masalah ini beberapa tahun yang lalu ketika saya ingin menulis RTS menggunakan arsitektur berbaris yang sama yang Anda lakukan.

Kesimpulan saya tentang floating-point perangkat keras adalah:

• Kode rakitan asli yang sama kemungkinan besar bersifat deterministik asalkan Anda berhati-hati dengan flag titik mengambang dan pengaturan penyusun.
• Ada satu proyek RTS open source yang mengklaim mereka mendapatkan kompilasi C / C ++ deterministik di berbagai kompiler menggunakan perpustakaan wrapper. Saya tidak memverifikasi klaim itu. (Jika saya ingat benar itu tentang STREFLOPperpustakaan)
• JIT bersih. Diijinkan sedikit kelonggaran. Khususnya diizinkan untuk menggunakan akurasi yang lebih tinggi daripada yang dibutuhkan. Juga menggunakan set instruksi yang berbeda pada x86 dan AMD64 (saya pikir pada x86 menggunakan x87, AMD64 menggunakan beberapa instruksi SSE yang perilakunya berbeda untuk denorm).
• Instruksi kompleks (termasuk fungsi trigonometri, eksponensial, logaritma) sangat bermasalah.

Saya menyimpulkan bahwa tidak mungkin untuk menggunakan tipe floating in built in .net secara deterministik.

Kemungkinan Solusi

Karena itu saya membutuhkan penyelesaian. Saya mempertimbangkan:

1. Implementasikan FixedPoint32dalam C #. Meskipun ini tidak terlalu sulit (saya memiliki implementasi setengah jadi) rentang nilai yang sangat kecil membuatnya mengganggu untuk digunakan. Anda harus berhati-hati setiap saat sehingga Anda tidak meluap, atau kehilangan terlalu banyak presisi. Pada akhirnya saya menemukan ini tidak lebih mudah daripada menggunakan bilangan bulat secara langsung.
2. Implementasikan FixedPoint64dalam C #. Saya menemukan ini agak sulit dilakukan. Untuk beberapa operasi, bilangan bulat menengah 128bit akan bermanfaat. Tapi .net tidak menawarkan tipe seperti itu.
3. Gunakan kode asli untuk operasi matematika yang deterministik pada satu platform. Menghasilkan overhead panggilan delegasi pada setiap operasi matematika. Kehilangan kemampuan untuk menjalankan lintas platform.
4. Gunakan Decimal. Tetapi lambat, membutuhkan banyak memori dan dengan mudah melempar pengecualian (pembagian 0, meluap). Ini sangat bagus untuk penggunaan finansial, tetapi tidak cocok untuk game.
5. Terapkan floating-point 32 bit khusus. Kedengarannya agak sulit pada awalnya. Kurangnya intrinsik BitScanReverse menyebabkan beberapa gangguan ketika menerapkan ini.

SoftFloat saya

Terinspirasi oleh posting Anda di StackOverflow , saya baru saja mulai menerapkan tipe floating-point 32 bit dalam perangkat lunak dan hasilnya menjanjikan.

• Representasi memori kompatibel dengan biner dengan IEEE floats, jadi saya dapat menafsirkan ulang cast ketika mengeluarkannya ke kode grafis.
• Ini mendukung SubNorms, infinities dan NaNs.
• Hasil pastinya tidak identik dengan hasil IEEE, tetapi itu biasanya tidak masalah untuk gim. Dalam kode semacam ini hanya penting bahwa hasilnya sama untuk semua pengguna, bukan akurat untuk angka terakhir.
• Performanya layak. Tes sepele menunjukkan bahwa ia dapat melakukan sekitar 75MFLOPS dibandingkan 220-260MFLOPS dengan floatpenambahan / perkalian (Utas tunggal pada i66 2,66GHz ). Jika ada yang memiliki tolok ukur floating point yang baik untuk .net, silakan kirim ke saya, karena tes saya saat ini sangat sederhana.
• Pembulatan dapat ditingkatkan. Saat ini memotong, yang kira-kira sama dengan pembulatan ke nol.
• Itu masih sangat tidak lengkap. Saat ini pembagian, gips dan operasi matematika yang rumit tidak ada.

Jika ada yang ingin berkontribusi tes atau meningkatkan kode, cukup hubungi saya, atau mengeluarkan permintaan tarik di github. https://github.com/CodesInChaos/SoftFloat

Sumber ketidakpastian lainnya

Ada juga sumber ketidakpastian lainnya di .net.

• iterasi di atas Dictionary<TKey,TValue>atau HashSet<T>mengembalikan elemen dalam urutan yang tidak ditentukan.
• object.GetHashCode() berbeda dari menjalankan ke menjalankan.
• Implementasi Randomkelas bawaan tidak ditentukan, gunakan milik Anda sendiri.
• Multithreading dengan penguncian naif mengarah untuk menyusun ulang dan hasil yang berbeda. Berhati-hatilah untuk menggunakan utas dengan benar.
• Ketika WeakReferencekehilangan target mereka tidak pasti karena GC dapat berjalan kapan saja.

Jawaban untuk pertanyaan ini berasal dari tautan yang Anda poskan. Khususnya Anda harus membaca kutipan dari Game Bertenaga Gas:

Saya bekerja di Game Bertenaga Gas dan saya dapat memberi tahu Anda secara langsung bahwa matematika floating point bersifat deterministik. Anda hanya perlu set instruksi dan kompiler yang sama dan tentu saja prosesor pengguna mematuhi standar IEEE754, yang mencakup semua PC dan 360 pelanggan kami. Mesin yang menjalankan DemiGod, Supreme Commander 1 dan 2 mengandalkan standar IEEE754. Belum lagi mungkin semua game RTS peer to peer lainnya di pasar.

Dan kemudian di bawah yang itu adalah ini:

Jika Anda menyimpan replay sebagai input pengontrol, mereka tidak dapat diputar pada mesin dengan arsitektur CPU, kompiler, atau pengaturan optimisasi yang berbeda. Di MotoGP, ini berarti kami tidak dapat membagikan replay yang disimpan antara Xbox dan PC.

Permainan deterministik hanya akan bersifat deterministik saat menggunakan file yang dikompilasi secara identik dan berjalan pada sistem yang mematuhi standar IEEE. Simulasi atau replay jaringan yang disinkronkan lintas platform tidak akan mungkin.

Gunakan aritmatika titik tetap. Atau pilih server yang otoritatif dan sesekali sinkronkan status permainan - itulah yang dilakukan MMORTS. (Setidaknya, Elements of War bekerja seperti ini. Itu ditulis dalam C # juga.) Dengan cara ini, kesalahan tidak memiliki kesempatan untuk menumpuk.

Sunting: Tautan ke kelas titik tetap (Pembeli Waspadalah! - Saya belum menggunakannya ...)

Anda selalu bisa kembali ke aritmatika titik tetap . Seseorang (membuat rts, tidak kurang) telah melakukan pekerjaan kaki pada stackoverflow .

Anda akan membayar penalti kinerja, tetapi ini mungkin atau mungkin tidak menjadi masalah, karena .net tidak akan terutama tampil di sini karena tidak akan menggunakan instruksi simd. Tolok Ukur!

NB Rupanya seseorang di intel tampaknya memiliki solusi untuk memungkinkan Anda menggunakan pustaka primitif kinerja intel dari c #. Ini dapat membantu membuat vektor kode titik tetap untuk mengimbangi kinerja yang lebih lambat.

Saya telah mengerjakan sejumlah judul besar.

Jawaban singkat: Mungkin saja jika Anda sangat keras, tetapi mungkin tidak sepadan. Kecuali jika Anda menggunakan arsitektur tetap (baca: konsol) itu rewel, rapuh dan dilengkapi dengan sejumlah masalah sekunder seperti terlambat bergabung.

Jika Anda membaca beberapa artikel yang disebutkan, Anda akan mencatat bahwa sementara Anda dapat mengatur mode CPU ada beberapa kasus aneh seperti ketika driver cetak mengganti mode CPU karena berada di ruang alamat yang sama. Saya punya kasus di mana aplikasi dikunci bingkai ke perangkat eksternal, tetapi komponen yang salah menyebabkan CPU melambat karena panas dan melaporkan secara berbeda di pagi dan sore hari, membuatnya berlaku mesin yang berbeda setelah makan siang.

Perbedaan platform ini ada pada silikon, bukan perangkat lunak, jadi untuk menjawab pertanyaan Anda C # juga terpengaruh. Instruksi seperti gabungan multiply-add (FMA) vs ADD + MUL mengubah hasilnya karena hanya dibulatkan secara internal satu kali, bukan dua kali. C memberi Anda lebih banyak kontrol untuk memaksa CPU melakukan apa yang Anda inginkan pada dasarnya dengan mengecualikan operasi seperti FMA untuk menjadikan hal-hal "standar" - tetapi dengan mengorbankan kecepatan. Secara intrinsik tampaknya paling cenderung berbeda. Pada satu proyek saya harus menggali buku acos tables berusia 150 tahun untuk mendapatkan nilai perbandingan untuk menentukan CPU mana yang "benar". Banyak CPU menggunakan perkiraan polinomial untuk fungsi trigonometri tetapi tidak selalu dengan koefisien yang sama.

Rekomendasi saya:

Terlepas dari apakah Anda melakukan langkah-kunci integer atau menyinkronkan, menangani mekanik game inti secara terpisah dari presentasi. Jadikan permainan ini akurat, tetapi jangan khawatir tentang akurasi di lapisan presentasi. Juga ingat Anda tidak perlu mengirim semua data dunia jaringan pada kecepatan bingkai yang sama. Anda dapat memprioritaskan pesan Anda. Jika simulasi Anda 99,999% cocok, Anda tidak perlu mengirim sesering untuk tetap berpasangan. (Mengesampingkan pencegahan.)

Ada artikel yang bagus tentang mesin Sumber yang menjelaskan satu cara untuk pergi tentang sinkronisasi: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Ingat, jika Anda tertarik untuk terlambat bergabung, Anda harus menggigit peluru dan tetap menyinkronkan.

Perhatikan bahwa saya terutama tertarik pada C #, yang sejauh yang saya tahu, memiliki masalah yang sama persis seperti C ++ dalam hal ini.

Ya, C # memiliki masalah yang sama dengan C ++. Tetapi juga memiliki lebih banyak.

Misalnya, ambil pernyataan ini dari Shawn Hawgraves:

Jika Anda menyimpan replay sebagai input pengontrol, mereka tidak dapat diputar pada mesin dengan arsitektur CPU, kompiler, atau pengaturan optimisasi yang berbeda.

"Cukup mudah" untuk memastikan bahwa ini terjadi di C ++. Namun dalam C # , itu akan menjadi jauh lebih sulit untuk dihadapi. Ini berkat JIT.

Menurut Anda apa yang akan terjadi jika penerjemah menjalankan kode Anda ditafsirkan sekali, tetapi kemudian JIT melakukannya untuk yang kedua kalinya? Atau mungkin itu menafsirkannya dua kali pada mesin orang lain, tetapi JIT setelah itu?

JIT tidak deterministik, karena Anda memiliki sedikit kendali atas itu. Ini adalah salah satu hal yang Anda menyerah untuk menggunakan CLR.

Dan Tuhan membantu Anda jika satu orang menggunakan .NET 4.0 untuk menjalankan permainan Anda, sementara orang lain menggunakan Mono CLR (menggunakan perpustakaan .NET tentu saja). Bahkan .NET 4.0 vs. .NET 5.0 dapat berbeda. Anda hanya perlu lebih banyak kontrol atas detail level rendah dari platform untuk menjamin hal semacam ini.

Anda harus bisa lolos dengan matematika fixed-point. Tapi itu saja.

Saya menyadari setelah menulis jawaban ini bahwa itu sebenarnya tidak menjawab pertanyaan, yang secara khusus tentang nondeterminisme floating-point. Tapi mungkin ini berguna baginya jika dia akan membuat game berjaringan dengan cara ini.

Bersamaan dengan berbagi input yang Anda siarkan kepada semua pemain, akan sangat berguna untuk membuat dan menyiarkan checksum dari status permainan penting, seperti posisi pemain, kesehatan, dll. Saat memproses input, nyatakan bahwa checksum status permainan untuk semua pemain jarak jauh dalam sinkronisasi. Anda dijamin tidak memiliki sinkronisasi (OOS) bug untuk diperbaiki dan ini akan membuatnya lebih mudah - Anda akan memiliki pemberitahuan sebelumnya bahwa ada yang tidak beres (yang akan membantu Anda mengetahui langkah-langkah reproduksi), dan Anda harus dapat menambahkan lebih banyak status permainan masuk dalam kode yang dicurigai untuk memungkinkan Anda untuk menandai apa pun yang menyebabkan OOS.

Saya pikir ide dari blog yang ditautkan masih memerlukan sinkronisasi berkala agar dapat hidup - saya telah melihat cukup banyak bug di game RTS jaringan yang tidak menggunakan pendekatan itu.

Jaringan bersifat lossy, lambat, latensi, dan bahkan mungkin mencemari data Anda. "Floating point determinism", (yang terdengar buzzwordy cukup membuat saya skeptis) adalah yang paling tidak Anda khawatirkan dalam kenyataan ... khususnya jika Anda menggunakan langkah waktu yang tetap. dengan langkah waktu variabel Anda perlu interpolasi antara langkah waktu tetap untuk menghindari masalah determinisme juga. Saya pikir ini biasanya apa yang dimaksud dengan perilaku "floating point" non-deterministik - hanya saja langkah-langkah waktu variabel menyebabkan integrasi berbeda - tidak ada hubungannya dengan perpustakaan matematika atau fungsi tingkat rendah.

Sinkronisasi adalah kuncinya.

Anda membuatnya deterministik. Untuk contoh yang bagus, lihat Dungeon Siege GDC Presentation tentang bagaimana mereka membuat lokasi di dunia menjadi jaringan.

Juga ingat bahwa determinisme juga berlaku untuk peristiwa 'acak'!