能解残局吗？ - Githubissues

sbl1996 commented 2 weeks ago

我觉得残局不需要AI，通过搜索就能够解决。残局的解空间一般不大，只要能导入到环境中，遍历所有可行动作应该就能解出来了。
如果是训练AI来解残局可能不太合适，AI强化学习训练依靠奖励，而残局只有在解出时给予奖励，其他时候都没有奖励，所以不适合训练AI。
如果是用普通对局训练好的AI来解残局，也不太合适。因为残局的情况与一般对局相差很大，比如残局中玩家的卡的数量一般非常少，这种分布与通常对局相差很大，导致模型很容易输出错误结果，可能反而不如用随机搜索。

yybbwc commented 2 weeks ago

只靠搜索就行了？以前有人说要做自动解残局机，但现在还没有成功。哦，他现在也关注了你的项目，ID名是小张。我感觉还是有些难点吧。

要为AI提供奖励的话，可以以血量为锚点。超过一定血量就给奖励，然后逐步提高血量——这也是制作残局的方法。

sbl1996 commented 2 weeks ago

主要难点是搜索空间有多大，以及搜索过程是否会陷入无限循环以及如何打破无限循环。我的库的实现可以做到普通PC每秒搜索1万步，一天是8亿步，如果能覆盖搜索空间大小，就可以解出来。当然这是理论可能性，实际还有一些如何做合适的树搜索并行化等考虑。

sbl1996 commented 2 weeks ago

如果有中间奖励的话，可以用比暴力搜索更好的方法，减少搜索步数。

sbl1996 commented 2 weeks ago

主要难点是搜索空间有多大，以及搜索过程是否会陷入无限循环以及如何打破无限循环。我的库的实现可以做到普通PC每秒搜索1万步，一天是8亿步，如果能覆盖搜索空间大小，就可以解出来。当然这是理论可能性，实际还有一些如何做合适的树搜索并行化等考虑。

游戏王每一步的可能性数量并不大，除了以下情况，一般每一步的可行动作数量不超过16：

从整个卡组或额外卡组中选择一张卡，可选的卡的数量为N，可能性数量就为N，如果是同时选多张卡，则为组合数
选择种族或数字，因为种族或数字的可能性很多
选择某些卡作为素材进行特殊召唤，同样因为组合数很多

yybbwc commented 2 weeks ago

可以用机器解下面这个残局吗？它有一些特点：

我方与对方的手卡·墓地·场上·除外都只有一张通常怪兽卡——场面简单
需要印卡，但只能印一张——需要理解卡池
可能的局面大概在十万以下——理论上用机器只需要几秒钟就能解开它

--[[message
维护：2024-06-18
简语：您能帮助「童话动物·小兔子」渡过难关吗？
标签：#枯岳说书人 #顽雨沉风 #test #测试
]]
Debug.SetAIName("test")
Debug.ReloadFieldBegin(DUEL_ATTACK_FIRST_TURN + DUEL_SIMPLE_AI, 4)
Debug.SetPlayerInfo(0, 100, 0, 0)
Debug.SetPlayerInfo(1, 5950, 0, 0)

local d = {}
local f = {}

d["印卡源"] = Debug.AddCard(55948544, 1, 1, LOCATION_EXTRA, 0, POS_FACEUP_ATTACK)

Debug.AddCard(27288416, 1, 1, LOCATION_MZONE, 2, POS_FACEUP_ATTACK)

Debug.AddCard(27288416, 1, 1, LOCATION_DECK, 2, POS_FACEUP_ATTACK)
Debug.AddCard(27288416, 1, 1, LOCATION_DECK, 2, POS_FACEUP_ATTACK)
Debug.AddCard(27288416, 1, 1, LOCATION_DECK, 2, POS_FACEUP_ATTACK)
Debug.AddCard(27288416, 1, 1, LOCATION_DECK, 2, POS_FACEUP_ATTACK)
Debug.AddCard(27288416, 1, 1, LOCATION_DECK, 2, POS_FACEUP_ATTACK)
Debug.AddCard(27288416, 1, 1, LOCATION_DECK, 2, POS_FACEUP_ATTACK)

Debug.AddCard(20129614, 0, 0, LOCATION_MZONE, 2, POS_FACEUP_ATTACK)

Debug.ReloadFieldEnd()
aux.BeginPuzzle()

f["不被连锁"] = function()
  Duel.SetChainLimit(aux.FALSE)
  return true
  end
do
  local k1, k2, k3, k4
  --~ 印卡过多时的提示
  k1 = "印卡过多"
  --~ 现在的印卡数量
  k2 = 1
  --~ 手卡印卡数量的上限
  k3 = 0
  --~ 印卡总数量的上限
  k4 = 0
  --~ 「调用这个效果」的效果
  --~ 「调用这个效果」的玩家
  f["_印卡"] = function(o1, o2)
    local k5, k6
    --~ 要印的卡的卡编
    k5 = Duel.AnnounceCard(o2)
    --~ 卡
    k6 = Duel.CreateToken(o2, k5)
    if k2 <= k3 then
      k2 = k2 + 1
      Duel.SendtoHand(k6, nil, REASON_RULE)
    else
      if k2 <= k4 then
        k2 = k2 + 1
        Duel.SendtoDeck(k6, o2, 0, REASON_RULE)
      else
        Debug.ShowHint(k1)
        o1:Reset()
        end
      end
    end
  --~ 印卡的启动源
  --~ 手卡印卡数量的上限
  --~ 印卡总数量的上限
  f["印卡"] = function(o1, o2, o3)
    local k5
    k3 = o2
    k4 = o3 or o2
    Debug.ShowHint("点对方额外卡组，可印卡\n只能印手卡 " .. k3 .. " 张\n最多可印 " .. k4 .. " 张")
    k5 = Effect.CreateEffect(o1)
    k5:SetType(EFFECT_TYPE_IGNITION)
    k5:SetProperty(EFFECT_FLAG_BOTH_SIDE + EFFECT_FLAG_UNCOPYABLE + EFFECT_FLAG_CANNOT_NEGATE + EFFECT_FLAG_CANNOT_DISABLE)
    k5:SetTarget(f["不被连锁"])
    k5:SetRange(LOCATION_EXTRA)
    k5:SetOperation(f["_印卡"])
    o1:RegisterEffect(k5)
    end
  end

f["印卡"](d["印卡源"], 1)

OhnkytaBlabdey commented 2 weeks ago

解残局是搜索问题，和pvp对战问题不一样。之前做的那个暴力破解，也是遍历搜索，没做并行化。

yybbwc commented 2 weeks ago

解残局是搜索问题，和pvp对战问题不一样。之前做的那个暴力破解，也是遍历搜索，没做并行化。

做了并行化就能解开吗？

yybbwc commented 1 week ago

主要难点是搜索空间有多大，以及搜索过程是否会陷入无限循环以及如何打破无限循环。我的库的实现可以做到普通PC每秒搜索1万步，一天是8亿步，如果能覆盖搜索空间大小，就可以解出来。当然这是理论可能性，实际还有一些如何做合适的树搜索并行化等考虑。

在目前的算力下，单靠搜索是无法解开残局的。

我有一个印卡残局，需要印十张卡，其中有九张卡是全卡池唯一确定的，且它们需要按特定顺序印。

目前的卡池有13338张卡，往低一点算大概是13000张。九张卡的排列数往低一点算，大概是5的阶乘。

单单是把卡印对而不考虑卡的行动，那么搜索空间就已经达到：

13000^9 * 5!

在这个数字面前，一天八亿步还差得远呢……

sbl1996 / ygo-agent

能解残局吗？ #2