保存棋局状态——Zobrist Hash算法

作者：追风剑情发布于：2017-6-11 22:20 分类：Algorithms

参考博客：http://www.cnblogs.com/IThaitian/p/3616507.html

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ZobristTest
{
    /// <summary>
    /// Zobrist Hash算法是专门用来求当前棋局的Hash算法。
    /// 对于复杂的棋类状态值用64位减少hash冲突。简单棋类状态值用32位即可。
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            int hash = 0;
            int hash1 = 0;
            //定义一个四个格子的棋盘，并为每个格子赋上状态值。
            int[] board = new int[4] { 12, 35, 68, 89 };  //棋盘初始状态
            int[] board1 = new int[4] { 12, 20, 68, 89 }; //棋盘的第2个格子状态变化了
            //求board棋盘hash值
            for (int i = 0; i < board.Length; i++)
            {
                hash ^= board[i];
            }
            Console.WriteLine("棋盘初始状态Hash: "+hash);

            //------------------------------------------------
            //笨办法求新棋局状态
            //棋盘状态发生变化后重新计算hash值
            for (int i = 0; i < board1.Length; i++)
            {
                hash1 ^= board1[i];
            }
            Console.WriteLine("棋盘状态Hash1: " + hash1);
            //------------------------------------------------

            //------------------------------------------------
            //高效的方法求新棋局状态
            //利用Zobrist Hash算法，只需对变化的格子状态重新做一次异或运算就可求得新棋盘的Hash状态。
            hash ^= 35;//与变化格子的原来状态值做一次异或运算
            hash ^= 20;//与变化格子的新状态值做一次异或运算
            Console.WriteLine("棋盘状态hash: " + hash);
            //------------------------------------------------

            Console.ReadKey();
        }
    }
}

运行测试