| dbo:abstract
|
- 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: constant indices white_pawn:= 1 white_rook:= 2 # etc. black_king:= 12 function init_zobrist: # fill a table of random numbers/bitstrings table:= a 2-d array of size 64×12 for i from 1 to 64: # loop over the board, represented as a linear array for j from 1 to 12: # loop over the pieces table[i][j] = random_bitstring function hash(board): h:= 0 for i from 1 to 64: # loop over the board positions if board[i] != empty: j:= the piece at board[i], as listed in the constant indices, above h:= h XOR table[i][j] return h 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 mempengaruhi 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: 'pawn at this square' (XORing out the pawn at this square) 'rook at this square' (XORing in the rook at this square) 'rook at source square' (XORing out the rook at the source square) 'nothing at source square' (XORing in nothing at the source square). Ini membuat hashing Zobrist sangat efisien untuk melintasi . Di , teknik ini juga digunakan untuk deteksi . 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. Universitas Budi Luhur (in)
- Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures ) is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert Lindsey Zobrist. It has also been applied as a method for recognizing substitutional alloy configurations in simulations of crystalline materials. Zobrist hashing is the first known instance of the generally useful underlying technique called tabulation hashing. (en)
|
| rdfs:comment
|
- Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures ) is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert Lindsey Zobrist. It has also been applied as a method for recognizing substitutional alloy configurations in simulations of crystalline materials. Zobrist hashing is the first known instance of the generally useful underlying technique called tabulation hashing. (en)
- 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. (in)
|
