使用Lua生成TTT游戏树。

2013-12-13 8:49:54
收藏：0
阅读：258
评论：1

我正在尝试在lua中编写井字棋游戏，并计划使用minimax算法来决定非人类移动。这涉及从单个输入状态生成所有可能的棋盘状态树的第一步。我正在尝试递归地执行此操作，但似乎无法弄清楚如何做。 （我认为）我概念上知道应该如何做，但在lua中实现起来有些困难。

我试图以以下方式构建我的树结构。每个节点都是具有两个字段的列表。

{ config = {}, children = {} }

Config是整数列表（0,1,2），代表空、X、O，定义TTT的板状态。Children是节点列表，这些节点是当前节点一步之遥的所有可能的棋盘状态。

这是我目前用于构建游戏树的函数

function tree_builder(board, player)
    supertemp = {}

    for i in ipairs(board.config) do

        --遍历当前的版状态。
        --对于每个空位置创建一个新节点
        --表示可能的版状态

        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

我一直在搜索在线帮助，并且我发现大多数内容都是概念性的或涉及其他语言的实现。我相信我错误地实现了递归元素，但是无法理解原因。

点赞
用户1474999
用户1474999

在 temp.children = tree_builder(temp, opposite(player)) 中不理解 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
    --检查行
    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
    --检查列
    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
    --检查对角线
    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 )
    --检查游戏是否结束
    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 )
2013-12-13 18:18:50

作者:

用户3023418

用户3023418
推荐文章