受Prolog启发的商业解决方案已经运行了10多年

对于大多数甚至已经听说过Prolog的程序员来说,这只是计算机像恐龙一样大的时代的一个奇怪的产物。一些人在研究所里被遗忘了。而且只有专家,像A4一样狭窄,在现代世界中也遇到过类似的情况。碰巧的是,早在2003年,我就在商业Flash游戏中使用了Prolog的一些解决方案,十多年来,它们使法国人感到高兴。而且,我采用这种半声明性的决定不是因为我读了Bratko印象深刻,但是因为我们的项目确实需要它。我仍然会定期尝试在现代水平上重现该解决方案,因为它在现代游戏行业中将非常有用,但是不幸的是,每次有更重要的事情要做时...总的来说,我将告诉您所有有关此问题的信息。





该Flash游戏的屏幕截图仍然欢迎您访问toox.com/jeux/jeux-de-cartes/coinche



问题及其相关性的陈述



Quosh,Belote和Tarot是法国国家比赛。根据规则,这与封闭游戏中的偏好游戏大致相同,并且一对游戏是一对游戏,因此通过讨价还价,您的伴侣打算在讨价还价中宣布贿赂多少张王牌,您可以大致了解他拥有哪种牌。这场比赛很长,而能够以某种方式结束比赛的AI的存在至关重要,因为其中一名玩家可以简单地离开桌面,决定自己毫无希望地输了,而获胜者自然希望将其推到得分板上的最终比分。在这种情况下,AI将为失去的玩家完成游戏。但是既然有了AI,为什么不让我们在空白处烦恼AI-shki来开始游戏。因此,我们向大众推出了这些出色的游戏,并很快发现法国人的游戏方式基本上有两种选择。如上面的屏幕截图所示,所有桌子中大约有一半正等待着有生之徒的到来,直到有胜利的人都坐满了,而另一半则降下并开始与三个AI对抗。



原则上,由于游戏已关闭,因此人们可以原谅机器人,以免出现轻微的错误计算和其他天赋。主要是因为看不到机器人卡。 “在具有simak的玩家面前”,“在具有ace的视野之下”以及类似的简单规则(我摆脱了法国客户)使我们能够制造出最低可接受的投掷器。它在ifs的一周内就被取消了。另一方面,游戏以“二为二”进行,点数计为一对,并且很自然地,玩家不希望自己的愚蠢伙伴“从第二位国王”进入,也就是说,手中有一位国王和其他一些小卡片,他便采取了行动。这套西服,而不是让对手打出一张A,而是用一张小卡片让它过去,然后与他的国王一起进行这套西服的下一步行动。 (实际上,在这些游戏中,第二古老的卡是10,但在下文中,我将用俄语说)。但是,如果王牌由于某种原因离开比赛,而您拥有女王/王后和其他一些小东西,则几乎就像第二位国王。特别是如果您预购了王牌。例如,您不是在玩使用32张牌的Belote,而是在塔罗牌玩的塔罗牌,其中一叠有78张牌(有些人猜测是同一张牌)。在某些情况下,甚至没有第三任皇后,但第四位杰克也可以收受贿赂。通常,所有这些都会导致大量的边缘情况,以至于ifs上的一个愚蠢的假人以某种方式变得完全无法接受的复杂。此时,我说:“ said!我读了很多例如,您不会玩使用32张牌的Belote,而是玩塔罗牌(Tarot),其中一盘游戏有78张牌(有些人猜测是同一张牌)。在某些情况下,甚至没有第三任皇后,但第四位杰克也可以收受贿赂。通常,所有这些都会导致大量的边缘情况,以至于ifs上的一个愚蠢的假人以某种方式变得完全无法接受的复杂。此时,我说:“ said!我读了很多例如,您不会玩使用32张牌的Belote,而是玩塔罗牌(Tarot),其中一盘游戏有78张牌(有些人猜测是同一张牌)。在某些情况下,甚至没有第三任皇后,但第四位杰克也可以收受贿赂。通常,所有这些都会导致大量的边缘情况,以至于ifs上的一个愚蠢的假人以某种方式变得完全无法接受的复杂。此时,我说:“ said!我读了很多简短而感动!” 然后我离开办公室几天,在咖啡馆里拿着笔记本电脑坐下,几天后产生了一些东西。



关键思想



声明式的Prolog是基于什么的?关于事实,例如:



('', '').
('', '').


根据条款或规则,例如,如果A是母亲B,那么A是女孩:



() :- (, ).


当然,我了解到,在我们这个时代,一切并不是那么简单,总的来说,这甚至有点不雅,但是当人们相信形式逻辑时,在这样的例子中没有什么可理解的。容忍度为:



(A, B) :- (A, B).
(, ) :- (, ), (, ).


然后你这样问我:



?-  (X, '')


而非常合乎逻辑的序言回答了您:



X = ''
X = ''


这个想法是让用户不要以序言系统将规则应用到事实以得出答案的顺序和数量来动摇头。但是,当然不是那么简单。序幕上挤满了拐杖,功能性补充,各种推理分支的工具等等,并且仍然经常出现无限递归的情况。



在那部鼓舞人心的Bratko的书中,整整一章专门介绍了如何在内部实现序言机器。简而言之,它深入研究所有规则的树,尝试将每个规则依次应用到它所知道的所有事实和变量的集合以获取新状态,并且如果无法应用该规则,它将回滚到上一步并尝试另一个选择。



此外,如果您设法将有用的内容拼凑在一起,则计算机将获取规则列表,然后从下一步开始,从列表的最开始查找要应用的规则。此外,如果在规则中找到了变量,则机器会记住已应用的规则,记住这些变量的状态。这称为充实。如果它可以找到使问题成立的变量的实例化,则将打印该实例化。然后她可以去寻找下一个具体化对象,依此类推。在上面的人工示例中,系统找到了两个满足条件的具体化。



我想以某种方式类似地制定游戏规则,但当然不是字面意义。拥有在Prolog中调试程序的经验,我根本不急于面对这种调试以及产品上的这些间接费用。





首先,所有这些都不应该作用于一堆分散的事实,而应该作用于游戏状态树-一个模型,并将其工作结果也应用于同一棵树。其次,我想编写规则,以使特定值,变量和算术表达式可以位于同一位置,并且系统应适当地处理此问题,而不必问程序员其他问题,也不需要其他语法。第三,当然,放弃无限递归至关重要,但是仍然需要重复一些规则的应用。第四,规则系统应该以一种非常方便的人类可读格式编写,以便一眼就能看出作者想说些什么。最后,第五,所有这些都需要与一些方便的日志记录和调试工具绑定在一起,以便可以轻松地遵循此系统的原理并理解为什么某些规则不符合预期的原因。



当然,这不是通用的一阶谓词逻辑求解器,而是简单的游戏规则声明系统。从实际意义上讲也是非常好的。为此,我在以下项目之一中提出了Logrus这个名字。我将绕过引擎开发的所有中间阶段,立即描述最终版本。



Logrus库的结果语法



会有很多语法。



1)在运行时,决策树以某些类的形式存储,但是,我附在它上面的第一件事是,一旦工作,它就是JSON中的Import and Export。事实证明,这样做也是很方便的,因为如果您的数据结构没有太大变化,则可以从文件更新规则而无需重新编译。事实证明,以JSON形式进行编写非常方便,以至于在以下项目之一中,当程序员急忙时,有时他们只是写了一些常规命令,而不是编写常规命令state.AplayJSON("...");并将所需的操作作为JSON字符串插入其中。当然,这并不能很好地影响性能,但是如果不是经常性的并且仅响应用户的点击,那么这并不可怕……其余所有我将立即使用JSON进行说明。我大概从内存中重现JSON,因为那是很长一段时间了。严格来说,JSON不能保证对象中节点的顺序,但是大多数库仍然尊重它,因此这里和下面的节点顺序得到积极使用。



2)Rule成为引擎的主要结构单元。规则由条件和动作组成。通常,规则以数组的形式出现,并一次一一地应用:



[{"condition":{}, "action":{}},
 {"condition":{}, "action":{}}]


3)每个规则都包含一个条件-这是一个树模板,可能包含变量。系统将查看状态树是否与变量的任何值的模板匹配。如果发现这样的具体化,它将触发一个动作。例如:



{"condition":{
    "player":{
        "$X":{"gold" : "<20", "name":"$NAME"}
    }},
    "action":{}}


这样的构造意味着,为了触发树中的动作,必须在顶层有一个“玩家”节点,其中一个或几个子节点,每个子节点具有“金”字段,其值小于20,且“名称”。如果满足此条件,则将调用该动作,并将其作为输入传递给X变量-节点的键,以及NAME变量中的玩家的名称。如果存在多个合适的节点,因此有多个可能的实例,则将在输入中找到的每个实例被调用几次。



4)最初,那里的一切都没有那么灵活,但是后来在会议上有关Unity的许多演讲中都知道的Valyard,用一种解析器将我们搞砸了,该解析器将算术表达式解析为快速决策树,灵活性最终以强烈的色彩绽放。



5)C $变量名开始。它们可以显示为键,例如$ X,然后将选择多个实例化,例如可以将工作表值(例如$ NAME)插入到算术表达式中:例如:{“ gold”:“ <$ X * 10” }然后它可以用来检查条件,只有那些拥有比其序数乘以10的黄金多的玩家才能通过检查,最后可以直接在某些表达式中计算它们,例如:{“ gold”:“ $ X = 3 + $ this“}其中$ this是调用计算的当前点的值。该节点的通过将变量$ X的值具体化为3 +玩家拥有的黄金量。在可能性中想到的是没有实现,只有一个-变量不能首先出现在算术表达式的右侧,这将是一个错误,到将其用作参数时,它必须已经以其他几种方式具体化了。



6)表达式中的变量可以根据需要多次出现,而第一次提及该变量时会指定该变量,接下来的变量将作为相等性的检验。例如,这样的结构将采用第一个玩家,检查他的钱,然后寻找另一个将第一个玩家作为目标的玩家。如果找不到它,它将回滚到具体点X将选择下一个玩家,检查钱,依此类推,直到通过所有可能的选项X和Y。通过换行,程序员将更改检查的顺序,而不是最终结果:



{ "player":{
    "$X":{"gold":">20"},
    "$Y":{"target":"$X"}
}}


7)动作也是一个树模板,可以包含变量和算术表达式,并且游戏状态树将进行更改以与其匹配。例如,此模板将以玩家Y的形式为玩家X分配一个对手,但是如果由于某种原因不存在玩家Y,则会创建它。并且“多余的”播放器将被完全删除。从屏幕截图创建游戏时,删除符号为null,但是如果有人需要通过键插入空白值,则我将其替换为保留字。我认为总的来说,这个原则很明确,并且在游戏中执行的动作的含义基本相同。



{
    "condition":{
    "player":{
        "$X":{"gold":">20"},
        "$Y":{"target":"$X"}}},
    "action":{
        "$X":{"target":"$Y"},
        "superfluous":"@remove"}
}


8)动作也可以不是树模板,而是规则的数组。它们中的每一个都不会从头开始检查,而是会以调用操作的初始实例进行检查。也就是说,可以有一组完整的规则,它们都将使用X变量。



{
    "condition":{
        "player":{
            "$X":{}, "$Y":{"target":"$X"}}},
    "action":[
        {"condition":{}, "action":{}},
        {"condition":{}, "action":{}}]
}


9)子规则不能从状态树的根部应用,而可以从操作应用过程中达到的某个点应用。在这种情况下,所有条件和所有动作都将以此点为根。看起来像这样:



{
    "condition":{
        "player":{
            "$X":{}, "$Y":{"target":"$X"}}},
    "action":{
        "$X":{"@rules":[
            {"condition":{}, "action":{}},
            {"condition":{}, "action":{}}]}
}


10)可以将规则的重复指定为另一个节点,这在必要时实现了有限深度的递归。但是实际上,这种决定通常是没有必要的。通过将其放入动作中,还可以根据需要重复使用一系列规则:



{
    "condition":{},
    "action":{},
    "repeat":5
}


11)规则树可以从几个JSON文件中加载,它们的树结构只是彼此叠加在一起。将规则分成单独的有意义的块很方便。可能有些Include也会有用,现在我不记得它是如何与我们一起安排的。



12)记录!任何规则都可以具有“ @log”:true节点,这导致该规则在描述解决过程的日志中开始变得非常详细。我们尝试什么具体化,推理的哪些分支被压制,以及为什么。日志记录是分层的,也就是说,嵌套规则可以是“ @log”:false,并且记录在日志中及其下方的所有内容都不会被记录。理想情况下,我希望该节点能够留在条件树中的任何位置,以便仅查看模板的一个级别中正在发生的事情,但是我似乎尚未完成这种扩展。如果没有它,调试可能会进行得很好,因此它被推迟到“某天”。



13)打字。这个玩具太旧了,以至于今天的一些程序员甚至还没有出生。它是用ActionScript2编写的,它通过运行时可用的原型具有动态类型和继承。在所听到的现代语言中,只有Python可以这种方式工作。但是,绑定这个想法并不是特别困难。我可以使用':'键符号来完成它,例如:“ $ X:int”,但是如果第一次出现的变量没有任何指定类型,可能会很棘手。而且,可能与三元运算符混淆。



就像他们说的那样,它在纸上很光滑,但实际使用需要许多不同的拐杖。这是我记得的那些:



14)一个节点和一个节点可能不是由一个节点而是由多个条件进行检验。例如,这种条件首先检查是否有20多个钱,然后指定表示该钱数量的变量。如果服务符号“ @”不在行的开头,则意味着重新输入该节点,进一步输入的重新标识没有任何用处。也许使用了服务符号,而其他一些,但我认为没有什么可以阻止您使用此符号:



{
    "player":{
        "$X":{"gold":"<20", "gold@cnt":"$COUNT"}
    }
}


15)进行了可以完全不使用任何节点的算术运算。根据序言的传统,它们被称为“ _”,并且可以有很多:



{
    "_":"$SUM=$A+$B",
    "_@check":"@SUM <20"
}


16)由于有一个通过树的验证,因此它通过“ @parent”关键字向下下降。当然,这并没有增加可读性,但是没有它是不可能的。当然,这里的路径函数类似物直接建议自己,它将重定向到树中的指定位置,但是我不记得我是否最终实现了它:



{
    "condition":{
        "player":{
            "$X":{}, "$Y":{"target":"$X"}}},
    "action":{
        "$X":{"rules":[
            {
                "condition":{
                    "@parent":{"@parent":{"…":"…"}}
            }
        ]},
    }
}


17)现在,该动作可以直接提取某些类方法。这可提高可读性,我更喜欢#include的类似物,但实际上,您不能将歌曲中的单词扔掉。我想知道如果现在在C#中重新激活该库,是否可以在实践中不用它呢?



18)现在,该规则还有一个附加设置,可以不对发现的所有凝结物重复操作,而仅对第一个凝结物重复操作。我现在不记得它叫什么了,但是由于某种原因,这个拐杖对某些规则很有用。



使用结果



一旦库开始被积极使用,所有的AI-shki都将很快转移到库中,这使得拥有两倍的智能AI成为可能,而所花费的编程资源却减少了三倍。 AI规模的中间数据直接存储在树中的事实大有帮助。尤其是,规则本身在游戏状态树中写入了有关已离开游戏的每套西装的牌的信息。



已经在下一个项目中,检查游戏规则并可能从每个位置移动到同一引擎。通常,不仅对于快速原型制作,而且对于规则简单的游戏,这都是非常有用的。最后,带有逻辑的可下载JSON可以替代程序员用代码完成的一半工作,并且还可以提高灵活性。



当然,就执行速度而言,所有这一切都明显不如ifs混乱,尤其是在AS2的原型和动态对象的实现中,但并不是很多,以至于无法推广到生产中。



下一步是将规则检查转移到客户端计算机,并确定AI的操作。供玩家互相检查。我什至想出了一种算法来做到这一点,尽管事实上我们并不知道敌方卡的值,但这是一个完全不同的故事。



多年过去了,我换了十次工作,每次更新简历时,我都去了toox.com,惊讶地发现我的工作仍在继续。我什至停下来玩另一场比赛。进入Belot后,我偶然遇到了一组提供最大可能点数的卡片。得到这样一个集合的可能性是三百万分之一。



总有一天,我会聚精会神,对C#和Unity3d进行Logrus的现代翻版,例如,为我梦dream以求的六角形策略师。但这不是今天,今天我要上床睡觉。已经成功地完成了传播值得传播的思想的责任。



总而言之,有一些轶事



我们位于新西伯利亚学院。我们在研究所租了一个办公室。客户是法国人,完全不熟悉当地习俗。因此,在共同工作的第三个月或第四个月,他来拜访我们,结识了我们。周末我在当地的“ Zolotaya Dolina”酒店登记入住,星期一,他对经理说,让我们早上十点钟乘坐出租车与我见面,我们将和程序员结识。然后带Vovchik到10点。一般来说,他们开车去研究所,敲门,从另一侧看望守望者的祖母,从锁着的门后面完全不了解地看着他们。在这么早的时候,没有科学家或程序员在建筑物中租用办公室。他们从字面上唤醒了她。



这是另一种情况。我们的塞巴斯蒂安·佩雷拉(Sebastian Pereira)打电话给经理,说他们奇迹般地设法闯入电视,不久我们就会在我们的网站上出现在电视上。大约8小时后。因此,您该怎么做才能使其更可靠地工作... 1月2日准时运行...没什么时间...因此Vovchik乘坐出租车,开始完全在宿舍和公寓里收集程序员,然后带他们去办公室。那天,我有生以来第一次见到我们的系统管理员。到目前为止,他的工作全部是远程完成的。因此,我们扭曲了每个可能的人。特别是,我通过将一堆ifs放回原处来破坏了整个系统,在这里,我们查看了出席率图,然后突然看到了它如何开始上升。在x15处某个位置,服务器崩溃了。但是管理员说一切都很好,轻轻地掉下来,现在他将升起。当天服务器又崩溃了三遍。



All Articles