Zobrist Hash
Zobrist Hashing (juga biasa disebut Kunci Zobrist atau Tanda Tangan Zobrist) adalah sebuah konstruksi fungsi hash yang digunakan didalam program komputer seperti permainan abstract board games, mirip catur dan Go, untuk mengimplementasi tabel transposisi, sebuah jenis tabel hash yang terindeks dari posisi board dan digunakan untuk menghindari analisis pada posisi yang sama lebih dari satu. Zobrist hashing diambil nama dari penemunya yaitu Albert Lindsey Zobrist. Hal ini juga sudah diterapkan sebagai metode untuk mengenali konfigurasi alloy dalam simulasi kristalisasi bahan.
Perhitungan nilai hash
Zobrist hashing memulai secara acak untuk menggenerate bitstring untuk setiap kemungkinan elemen pada permainan board, i.e untuk setiap bagian kombinasi dan posisi (dalam permainan catur, dalam 12 bagian x 64 posisi board, atau 14 x 64 jika raja masih berada di benteng dan bidak tertangkap secara terpisah). Sekarang konfigurasi board apapun bisa diretas/pecah menjadi komponen independen/posisi komponen, yang dipetakan ke bitstring secara acak dari hasil sebelumnya. Zobrist Hash yang terakhir dihitung dengan menggabungkan bitstring tersebut menggunakan bit XOR. Contoh psudokode dari permainan catur:
Penggunaan Nilai Hash
Jika bitstring cukup panjang, perbedaan posisi board akan hampir dipastikan memiliki nilai hash yang berbeda; namun seberapapun panjangnya bitstring akan membutuhkan sumber daya komputer untuk di manipulasi. Panjang bitstring (kunci) yang paling banyak digunakan adalah 64 bits. Banyak mesin game hanya menyimpan nilai hash di tabel transposisi, sebenarnya menghilangkan posisi informasi itu sendiri hanya untuk mengurangi penggunaan memori, dan asumsi bahwa terjadi tabrakan hash tidak akan terjadi, atau tidak akan banyak memengaruhi hasil tabel jika mereka menggunakannya.
Zobrist hashing adalah contoh hashing tabulasi pertama yang diketahui. Hasilnya adalah 3-wise independent hash familiy. Secara khusus ini sangat kuat.
Sebagai contoh, dalam catur, masing-masing dari 64 kotak dapat setiap saat kosong, atau berisi salah satu dari 6 buah permainan, yang hitam atau putih. Artinya, setiap kuadrat dapat berada dalam salah satu dari 1 + 6 x 2 = 13 keadaan yang memungkinkan setiap saat. Jadi seseorang perlu menghasilkan paling banyak 13 x 64 = 832 bitstring acak. Diberi posisi, orang mendapatkan hash Zobristnya dengan mencari tahu bagian mana yang berada di kotak mana, dan menggabungkan bitstring yang relevan bersama-sama.
Memperbarui Nilai Hash
Daripada menghitung hash untuk seluruh papan setiap kali, seperti pseudocode di atas, nilai hash dari papan dapat diperbarui hanya dengan XORing keluar dari bitstring (s) untuk posisi yang telah berubah, dan XORing dalam bitstring untuk yang baru posisi. Misalnya, jika pion pada papan catur digantikan oleh benteng dari kotak lain, posisi yang dihasilkan akan dihasilkan oleh XORing hash yang ada dengan bitstring untuk:
Ini membuat hashing Zobrist sangat efisien untuk melintasi pohon permainan .
Di komputer, teknik ini juga digunakan untuk deteksi superko .
Penggunaan Lebih Luas
Metode yang sama telah digunakan untuk mengenali konfigurasi paduan pengganti selama simulasi Monte Carlo untuk mencegah pemborosan upaya komputasi pada keadaan yang telah dihitung.
Sumber dan atribusi
Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 28949365 (2026-02-11T03:13:57Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.