logo标签列表

九子棋游戏的位板表示法

javaartificial-intelligencebitboard
3
我正在用Java编写九子棋游戏，已经实现了游戏规则和使用negamax的AI。然而，游戏基于数组，当AI在思考时（从6层开始），移动生成需要花费相当长的时间。
我的位置数组基于以下图表：
// 0        1        2
//    3     4     5
//       6  7  8
// 9  10 11    12 13 14
//       15 16 17
//    18    19    20
// 21       22       23

我有一些填满可能的磨坊和相邻位置的数组。

我决定从使用数组改为使用位棋盘，以便移动生成和其他当前使用数组的区域将更快。

我的第一步是为每个玩家创建一个位棋盘，用于跟踪玩家在棋盘上的棋子。

第二步是确定哪些位置是空闲的。我知道可以通过以下方式来实现：

freepositions = ~(player1bb | player2bb);

所以我的问题是，我如何设置/更新玩家的位棋盘来跟踪他们的棋子？
4个回答
1
考虑到玩家的比特棋盘长度为24位，其中棋盘的位置0是第一位，当玩家进行移动时，通过执行以下操作来设置比特棋盘，这样会变得非常简单：
player1bb |= (1 << pos);
0

位棋盘很有趣 :-)

我正在编写一些代码来解决这个问题，但是这里有一些希望能帮助你入门的东西：

public class BitBoard {
    public static final int White = 0;
    public static final int Black = 1;

    public long[] board = { 0, 0 };
    public int Player = 0;
    public int[] left = { 9, 9 };

    public int Opponent()
    {
        return Player == White ? Black : White;
    }

    public void makemove(int from, int to, int capture)
    {
        if (from == 0) { 
            assert left[Player] > 0 : "makemove: no left";
            left[Player]--;
        }       
        if (from != 0)
        {
            assert (board[Player] & from) != 0 : "makemove: source empty";
            board[Player] &= ~from;
        }
        assert (board[Player] & to) == 0 : "makemove: target must be empty";
        board[Player] |= to;
        if (capture != 0)
        {
            assert (board[Opponent()] & capture) != 0 : "makemove: capture empty";
            board[Opponent()] &= ~capture;
        }
    }

    public void unmakemove(int from, int to, int capture)
    {
        if (capture != 0)
        {
            assert (board[Opponent()] & capture) == 0 : "unmakemove: capture empty";
            board[Opponent()] |= capture;
        }
        assert (board[Player] & to) != 0 : "unmakemove: target empty";
        board[Player] &= ~to;
        if (from != 0)
        {
            assert (board[Opponent()] & capture) != 0 : "unmakemove: source must be empty empty";
            board[Player] |= from;
        }
        if (from == 0) { 
            assert left[Player] < 9 : "unmakemove: too many left";
            left[Player]++;
        }           
    }

    public void generatemoves()
    {
        // determine phase

        // 

    }
}

没有完全测试，但以下代码展示了如何使用：

import java.math.*;

public class NineMenBitboard {
    static int tst;

    //   A  B  C  D  E  F  G
    // 1 0        1        2
    // 2    3     4     5
    // 3       6  7  8
    // 4 9 10 11    12 13 14
    // 5      15 16 17
    // 6   18    19    20
    // 7 21       22       23

    // positions

    static int A1 = 1 << 0;
    static int D1 = 1 << 1;
    static int G1 = 1 << 2;
    static int B2 = 1 << 3;
    static int D2 = 1 << 4;
    static int F2 = 1 << 5;
    static int C3 = 1 << 6;
    static int D3 = 1 << 7;
    static int E3 = 1 << 8;
    static int A4 = 1 << 9;
    static int B4 = 1 << 10;
    static int C4 = 1 << 11;
    static int E4 = 1 << 12;
    static int F4 = 1 << 13;
    static int G4 = 1 << 14;
    static int C5 = 1 << 15;
    static int D5 = 1 << 16;
    static int E5 = 1 << 17;
    static int B6 = 1 << 18;
    static int D6 = 1 << 19;
    static int F6 = 1 << 20;
    static int A7 = 1 << 21;
    static int D7 = 1 << 22;
    static int G7 = 1 << 23;

    // mills

    static int hor1 = A1 | D1 | G1;
    static int hor2 = B2 | D2 | F2;
    static int hor3 = C3 | D3 | E3;
    static int hor4_1 = A4 | B4 | C4;
    static int hor4_2 = E4 | F4 | G4;
    static int hor5 = C5 | D5 | E5;
    static int hor6 = B6 | D6 | F6;
    static int hor7 = A7 | D7 | G7;

    static int ver1 = A1 | A4 | A7;
    static int ver2 = B2 | B4 | B6;
    static int ver3 = C3 | C4 | C5;
    static int ver4_1 = D1 | D2 | D3;
    static int ver4_2 = D5 | D6 | D7;
    static int ver5 = E3 | E4 | E5;
    static int ver6 = F2 | F4 | F6;
    static int ver7 = G1 | G4 | G7; 

    public static void main(String[] args) {
        // sample on how to loop bits

        BitBoard game = new BitBoard();
        game.makemove(0, A1, 0);
        game.makemove(A1, A4, 0);


        System.out.println();

        tst = 255;

        for(int looper = tst, i = Integer.highestOneBit(looper); looper != 0; looper &= ~i, i = Integer.highestOneBit(looper))
        {
            System.out.println(i);
        }       

        System.out.println(tst);
      }
}

还添加了一个循环来展示如何遍历位置。

玩得开心。我也会编写这个游戏，因为我想刷新我的AB剪枝技能:-)

位棋盘的真正优势在于在执行makemove和unmakemove时保留一些额外的数据。我的第一个添加是跟踪每个玩家形成的磨子计数和磨子位置。这将极大地改善移动生成（以及后来的棋盘评估）。 - Jacco
我有类似的位棋盘代码。我正在使用置换表进行Negascout算法的优化。如果你想分享更多的代码，请告诉我。 - Ivan-Mark Debono
我们可以分享代码。我考虑在以后的阶段将其放在Github上。我完成了带有磨损棋子跟踪的makemove/unmakemove。看起来可以工作，但需要进行一些检查。我运行了一个Perft(7)，在53秒内得到了1,873,562,112个着法。我应该发布Perft代码让你检查吗？ - Jacco
请发送电子邮件至blastedw（at）hotmail（dot）com或在FB上添加我。 - Ivan-Mark Debono
0
这里是Perft代码。我正在执行所有的第一步，但在将来的版本中，我可能只会执行6个独特的步骤（其他步骤将只导致镜像评估）。
public long Perft(int depth)
{
    long nodes = 0;

    ArrayList<Integer> moves = generateMoves();

    if (depth == 1) 
    {
        //for(int move : moves)
        //  System.out.println(moveStr(move));
        return moves.size();
    }

    for (int move : moves) {
        int capture = 1 << (move >> 10) >> 1; 
        int to = 1 << ((move >> 5) & 31) >> 1;
        int from = 1 << (move & 31) >> 1;           
        makemove(from, to, capture);
        //System.out.print(this);
        nodes += Perft(depth - 1);
        unmakemove(from, to, capture);
    }
    return nodes;       
}

我将走法打包成整数，如你所见。

以下是我的第一个完全搜索结果：

  • 1 24
  • 2 552
  • 3 12144
  • 4 255024
  • 5 5140800
  • 6 99274176 (3.107毫秒)
  • 7 1873562112 (53秒)
  • 8 花费时间太长
我的Ply 6的性能测试在5.79秒内返回2164535个节点。但是我的性能测试会复制棋盘，生成走法，执行走法并撤销它。 - Ivan-Mark Debono
哎呀，节点计数不一致 :S 好吧，我要开始调试了 :-) - Jacco
0

我知道你已经实现了它，但是你应该像这样实现它

//  0        1           2
//     8     9       10
//        16  17  18
//  7 15  23      19 11  3
//        22   21 20
//    14    13       12
//  6       5            4

这样你就可以移动到位置 pos >> 1 表示前一个位置，<< 1 表示下一个位置，pos << 8 表示下一个字节的相同位置，pos >> 8 表示前一个字节的相同位置。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接