更好的移動發電機比Neutreeko

Question

我實施了一個名爲Neutreeko（5×5板3個走卒爲每個兩名球員）的比賽和我採取蒙特卡羅樹搜索蠻力，我需要一個快速的方法爲玩家擁有的棋子產生所有可能的移動。我將棋盤狀態存儲在一個一維數組中，其中每個單元格等於'player'，'cpu'或0.

至於規則，如果棋子沿水平，垂直或對角線移動線沒有擊中牆壁或其它棋子（這意味着如果你假設在一個空的板的中心站立，你將只能在非常角部和在各邊的鄰近中間細胞允許它能最遠點這些方面共計8步）。

什麼是尋找移動不僅僅是蠻力在每個8個方向行駛，直到我打在牆上或其他棋子的更好的辦法？這也需要很多條件來確保 - 在檢查對角線時 - 我們不會在用升序索引等旅行時意外地去另一條線。當然，它可以做到，但我敢打賭，有一些遊戲理論實踐更加優雅和有效地處理它。

Answer 1

希望這是不能完全不清楚...

每片引起的容許移動一定排除，通過阻止線。有24條線（10 + 14對角線），並有320次可能的滑動移動。最好在每個方向上使用5個「環繞」對角線，共20行，每個最多20行。每件作品放在3（角落）或4條線上，當一塊棋子移動時，你更新線移動的線和4-6個受影響的線。

特定正方形的排除，即，舉動，在該正方形塊的一塊，是恆定的。所有你需要做的是從每一行中加上或減去一個常量二進制字符串。要生成一個新的位置，請檢查玩家三件棋子的每個棋子的一些位標誌，看看該棋子的排除次數是否爲零。

排除的每個移動的最大數目而變化（例如，如果一整行是滿的，有不能從A滑動到E 5個原因）。法線的總表示需要23位。

ABCDE AB，BC，CD，DE，AC，BD，CE僅需要2比特的每個（< = 3排除）AD ，BE，AE 3個比特

Answer 2

更新：

靈感來自clwhisk的建議，我有以下想法：

散列所有板的位置爲30位 - 前15位作爲計算機的位置，接下來的15位作爲玩家的位置（每個典當5位）。對於每25個選擇3個（= 2300）的計算機位置，產生22個選擇3（= 1540）匹配的玩家位置，並將哈希設置爲指向下一個棋盤位置（其中前15個比特是計算機的棋子）這可能是由其中一臺計算機棋子的移動造成的。

這樣沒有移動將需要產生，也贏得位置進行測試。看起來哈希大小似乎爲2300 * 1540 = 3,542,000，但會包括預先計算的所有三個棋子的下一個棋子狀態，包括散列獲勝位置。此外，董事會可以表示爲一個數字，而不是代表每個玩家位置的兩個比特板（在一些其他棋盤遊戲中常見）。

那麼，即使有網絡工作者，我的Firefox瀏覽器也會崩潰。所以我的另一個想法是使用2300項散列作爲二維數組的關鍵點（2300x2300; player_1_position x player_2_position），其值是可以跟隨player_1的可用動作的棋盤狀態。此外，可以嘗試散列一半的位置 - 如果它不在散列中，則位於鏡像位置。

結束更新。

這裏是一個JavaScript的例子，試圖散列所有倉板，電路板和動作 - 在我看來，有25選5 = 53130個可能的狀態董事會（不包括典當爲此我們想要移動）;並且每個棋盤狀態爲我們的棋子提供20個可能的位置。

我不確定在這個可觀的哈希中查找的速度可能與在動態生成可用的動作時相比。如預期的那樣，預先計算哈希需要幾秒鐘才能在瀏覽器上加載。

要查找可用的移動，類型：hash[board<<5|position]，

例如：

console.log(hash[31<<5|6]) 
[1048576,512,8388608] 

console.log(hash[31<<5|7]) 
[2097152,512,32,16777216,1024] 

JavaScript代碼（功能，comb和main，適於在C來自此Rosetta Code）：

var hash = {} 

function comb(m, n, c) 
{ 
    var i; 
    for (i = 0; i < n; i++) c[i] = n - i; 

    while (1) { 
     var s = 0 
     for (i = n; i--;) 
      s|=1<<c[i]-1; 

     //hash boards, positions, and moves 
     for (var j=1; j<=25; j++){ 
      var pos = 1 << (j - 1) 
      if (pos & s) 
       continue 
      hash[(s<<5)|j] = moves(pos,s) 
     }  

     /* this check is not strictly necessary, but if m is not close to n, 
      it makes the whole thing quite a bit faster */ 
     if (c[i]++ < m) continue; 

     for (i = 0; c[i] >= m - i;) if (++i >= n) return; 
     for (c[i]++; i; i--) c[i-1] = c[i] + 1; 
    } 
} 

function moves(position,board){ 
    var leftBorder = 17318416, 
     rightBorder = 1082401, 
     moves = [], 
     positionTemp = position 

    //up 
    while (positionTemp < 1<<20 && !((positionTemp<<5) & board)) 
     positionTemp <<= 5 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    positionTemp = position 

    //down 
    while (positionTemp > 1<<4 && !((positionTemp>>5) & board)) 
     positionTemp >>= 5 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    positionTemp = position 

    //left 
    while (!((positionTemp<<1) & board)){ 
     if (positionTemp & leftBorder || positionTemp == 1<<24) 
      break 
     positionTemp <<= 1 
    } 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    positionTemp = position 

    //right 
    while (!((positionTemp>>1) & board)){ 
     if (positionTemp & rightBorder || positionTemp == 1) 
      break 
     positionTemp >>= 1 
    } 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    positionTemp = position 

    //NW 
    while (!((positionTemp<<6) & board)){ 
     if (positionTemp & leftBorder || positionTemp >= 1<<20) 
      break 
     positionTemp <<= 6 
    } 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    positionTemp = position 

    //NE 
    while (!((positionTemp<<4) & board)){ 
     if (positionTemp & rightBorder || positionTemp >= 1<<20) 
      break 
     positionTemp <<= 4 
    } 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    positionTemp = position 

    //SW 
    while (!((positionTemp>>4) & board)){ 
     if (positionTemp & leftBorder || positionTemp <= 1<<4) 
      break 
     positionTemp >>= 4 
    } 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    positionTemp = position 

    //SE 
    while (!((positionTemp>>6) & board)){ 
     if (positionTemp & rightBorder || positionTemp <= 1<<4) 
      break 
     positionTemp >>= 6 
    } 

    if (positionTemp != position) 
     moves.push(positionTemp) 

    return moves 
} 

function main() 
{ 
    var buf = new Array(100); 
    comb(25, 5, buf); 
    console.log("done") 
} 


main()