在lua中生成TTT遊戲樹

Question

我正在嘗試在lua中編寫一個tic-tac-toe遊戲，並計劃使用minimax算法來決定非人爲移動。其中的第一步涉及從單個輸入狀態生成所有可能的電路板狀態的樹。我試圖遞歸做到這一點，但似乎無法弄清楚如何。 （我認爲）我在概念上理解這應該如何完成，但是在lua中執行它時遇到困難。

我想按照以下方式構建我的樹。每個節點都是一個包含兩個字段的列表。

{ config = {}, children = {} } 

配置是表示空，X整數（0,1,2）的列表，和O，並且限定了TTT板狀態。孩子是一個列表節點，它是所有可能的棋盤狀態，離開當前節點。

這裏是我的功能，我現在必須建立博弈樹

function tree_builder(board, player) 
    supertemp = {} 

    for i in ipairs(board.config) do 

     --iterate through the current board state. 
     --for each empty location create a new node 
     --representing a possible board state 

     if board.config[i] == 0 then 
      temp = {config = {}, children = {}} 

      for j in ipairs(board.config) do 
       temp.config[j] = board.config[j] 
      end 

     temp.config[i] = player 
     temp.children = tree_builder(temp, opposite(player)) 
     supertemp[i] = temp 
     end 

    end 
    return supertemp 
end 

的函數被調用方式如下：

start_board = {config = {1,0,0,0}, children = {} } 
start_board.children = tree_builder(start_board, 1) 

當我註釋掉函數的遞歸元素（「temp.children = builder（temp，opposite（player））」這一行），並且只生成第一級的子級。輸出是正確的。當通過代碼，在概念上等同於所謂的（我使用love2D因此，格式化是不同的）：

for i in pairs(start_board.children) do 
    print (start_board.children[i].config) 

的三個孩子分別是：

1,1,0,0 
1,0,1,0 
1,0,0,1 

但是，一旦我添加了遞歸元素，以下對於相同的三個孩子輸出

1,1,2,1 
1,1,2,1 
1,1,2,1 

我一直在上網查詢的幫助，大部分我所發現的是自然的概念或涉及differen實施t語言。我相信我錯誤地實現了遞歸元素，但無法圍繞原因爲什麼。

Answer 1

不明白opposite(player)是什麼意思temp.children = tree_builder(temp, opposite(player))。

請注意，遞歸需要一個結束條件。

這是我對你的結構下的解決方案：

local COL = 3 
local ROW = 3 

local function printBoard(b) 
    local output = "" 
    local i = 1 
    for _,v in ipairs(b.config) do 
     output = output .. v .. ((i % COL == 0) and '\n' or ',') 
     i = i + 1 
    end 
    print(output) 
end 

local function shallowCopy(t) 
    local t2 = {} 
    for k,v in pairs(t) do 
    t2[k] = v 
    end 
    return t2 
end 

local MAX_STEP = COL * ROW 

local ING = 0 
local P1 = 1 
local P2 = 2 
local TIE = 3 

local STATUS = { [P1] = "P1 Win", [P2] = "P2 Win", [TIE] = "Tied" } 

local start_board = { config = {P1,0,0,0,0,0,0,0,0}, children = {} }  

local function checkIfOver(board, step) 
    local config = board.config 
    local over = false 
    --check rows 
    for i=0,ROW-1 do 
     over = true 
     for j=1,COL do 
      if 0 == config[i*COL+1] or config[i*COL+j] ~= config[i*COL+1] then 
       over = false 
      end 
     end 
     if over then 
      return config[i*COL+1] 
     end 
    end 
    --check cols 
    for i=1,COL do 
     over = true 
     for j=0,ROW-1 do 
      if 0 == config[i] or config[i] ~= config[i+COL*j] then 
       over = false 
      end 
     end 
     if over then 
      return config[i] 
     end 
    end 
    --check diagonals 
    if config[1] ~= 0 and config[1] == config[5] and config[5] == config[9] then 
     return config[1] 
    end 
    if config[3] ~=0 and config[3] == config[5] and config[5] == config[7] then 
     return config[3] 
    end 
    if step >= MAX_STEP then  
     return TIE 
    else 
     return ING 
    end 
end 

local function treeBuilder(board, step) 
    --check the game is over 
    local over = checkIfOver(board, step) 
    if over ~= ING then 
     printBoard(board) 
     print(STATUS[over], '\n---------\n') 
     return 
    end 
    local child 
    local childCfg 
    for i,v in ipairs(board.config) do 
     if 0 == v then 
      child = { config = {}, children = {} } 
      childCfg = shallowCopy(board.config) 
      childCfg[i] = (step % 2 == 0) and P1 or P2 
      child.config = childCfg 
      table.insert(board.children, child) 
      treeBuilder(child, step + 1) 
     end 
    end 
end 

treeBuilder(start_board, 1)