在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)