用于XML文件生成的机器学习算法

I have a game application with characters that have to cross mazes. The game can generate thousands of different mazes and the characters can move according to users choice and cross the maze manually. We needed to add the possibility to show a correct way out of each maze. Therefore we added the possiblity to move the characters according to an xml file.

我有一个游戏应用程序的字符必须通过迷宫。游戏可以产生成千上万个不同的迷宫，角色可以根据用户的选择移动并手动穿越迷宫。我们需要增加一种可能性来显示出走出每一个迷宫的正确方法。因此，我们增加了根据xml文件移动字符的可能性。

This XML file is very complex, usually around thirty-fifty thousands of rows. lets say its in the following structure (but much more complex):

这个XML文件非常复杂，通常大约有35万行。它的结构如下(但要复杂得多):

  <maze-solution>
  <part id="1">
  <sector number="1">
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1250></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>run</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>light</equipemnt>
        <movement>
            <start-position>4223></start-position>
            <angle>233.43</angle>
            <duration>0.32</duration>
        </movement>
        <action-type>walk</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1231></start-position>
            <angle>84.134</angle>
            <duration>0.454</duration>
        </movement>
        <action-type>run</action-type>
        <character>2</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>932></start-position>
            <angle>34.43</angle>
            <duration>0.50</duration>
        </movement>
        <action-type>duck</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>   
  </sector>
  <sector number="2">
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1250></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>run</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>light</equipemnt>
        <movement>
            <start-position>4223></start-position>
            <angle>233.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>walk</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1231></start-position>
            <angle>84.134</angle>
            <duration>0.454</duration>
        </movement>
        <action-type>run</action-type>
        <character>2</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>932></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>duck</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>   
  </sector>
  <sector number="3">   
  </maze-solution>

At the moment, we have the ability to analayze each maze using a CNN algorithm for image classification and generate an xml that represents a way out of the maze - meaning that if the characters will be moved according to that file, they will cross the maze. That algorithm has been tested and can not be changed by any means.

目前，我们有能力使用CNN算法对每个迷宫进行图像分类，并生成一个表示出迷宫的方法的xml——这意味着如果字符将根据该文件移动，它们将穿越迷宫。该算法已经过测试，无法进行任何修改。

The problem is that most of the times the generated file is not the best one possible (and quite often it is very noticeable). There are different, faster, better ways to cross the maze.

问题是，大多数时候生成的文件并不是最好的(而且通常非常明显)。有不同、更快、更好的方式穿越迷宫。

We also have thousands (and we can get as many as needed) files that were created manually for saved mazes and therefore they are representing an elegant and a fast way out of the maze. The ideal goal is that someday, our program will learn how to generate such a file without people creating them manually.

我们还有数以千计的文件(我们可以得到任何需要的文件)，这些文件是为保存的迷宫手工创建的，因此它们代表了一种优雅的快速走出迷宫的方式。理想的目标是有一天，我们的程序将学习如何生成这样一个文件，而不需要人工创建它们。

To conclude, we have plenty of XML files generated by a program compared to the hard-coded XML files. There are thousands of pairs - The file the program generated, and the "ideal" file version that a person created. (and we can get infinite number of such pairs) Is there a way, using those thousands of pairs, to make a second step algorithm that will "learn" what adjustments should be made in the generated XML files to make them more like the hard-coded ones?

总之，与硬编码的XML文件相比，程序生成了大量的XML文件。有数千对——程序生成的文件，以及一个人创建的“理想”文件版本。(我们可以得到无数这样的对)是否有一种方法，使用这数千对，来进行第二步算法，以“了解”生成的XML文件中应该做哪些调整，使它们更像硬编码的文件?

I'm not looking for a specific solution here but for a general idea that will get me going. I hope i made myself clear but if I missed some info let me know and I will add it.

我不是在寻找一个具体的解决方案，而是寻找一个能让我前进的总体思路。我希望我说得很清楚，但是如果我漏掉了一些信息，请告诉我，我会添加的。

4 个解决方案

#1

I think you're barking up the wrong tree. A machine learning algorithm to convert the output from you "immutable" algorithm to better solutions based on user-provided solutions seems like a lot more trouble than it's worth.

我想你找错人了。一种机器学习算法，将你的“不可变”算法的输出转换为基于用户提供的解决方案的更好的解决方案，似乎比它的价值要麻烦得多。

To me, this sounds like an application of Dijkstra's algorithm, since you're trying to find the shortest path in a maze, and that's literally what this algorithm is designed for. Of course, any shortest-path algorithm your heart desires would also suffice, but Dijkstra's is one of the more common approaches. Based on this comment you provided on your post:

对我来说，这听起来像是Dijkstra算法的一个应用，因为你要在迷宫中寻找最短路径，这就是这个算法设计的目的。当然，任何你想要的最短路径算法也足够了，但是Dijkstra的算法是比较常见的方法之一。基于你在你的文章中提供的评论:

The shortest duration solution isn't always the best, there are many different factors, amount of life lost during the way, energy wasted (an in-game life and energy of course), and difficulty etc etc. The hand-written solution is sometimes longer in terms of duration but has less risks and less resources used and wasted

最短的时间解决方案并不总是最好的,有很多不同的因素,大量的生活中失去,能源浪费(当然一个游戏生命和能量),以及等等困难。有时手写的解决方案是持久的,但更少的风险和更少的资源使用和浪费

the edge weights on your graph are not just distance, but should factor in all of these costs associated with navigating the maze. Since this is very complex, it might also be useful or interesting to provide multiple "best" solutions using different calculations of edge weight which minimize the use of each the resources individually (time, life, energy, ...) as well as one or more that minimizes some combined score.

你图上的边的重量不只是距离，还应该考虑到在迷宫中航行的所有成本。由于这非常复杂，使用不同的边重计算提供多个“最佳”解决方案可能也很有用或很有趣，这些解决方案可以最小化每个资源的单独使用(时间、生命、能量……)，也可以提供一个或多个使某些组合分数最小化的解决方案。

One other thing: if this is true:

还有一件事:如果这是真的:

the comparing is not that easy

比较并不容易

how are you determining that user solutions are better?

您如何确定用户解决方案更好?

Lastly, you said the following in your original post (emphasis mine):

最后，你在原文中说了以下内容(重点是我的):

At the moment, we have the ability to analayze each maze using a CNN algorithm for image classification and generate an xml that represents a way out of the maze - meaning that if the characters will be moved according to that file, they will cross the maze. That algorithm has been tested and can not be changed by any means.

目前，我们可以使用CNN的图像分类算法对每个迷宫进行分析，并生成一个表示走出迷宫方法的xml——这意味着如果这些字符将根据该文件移动，它们将穿过迷宫。该算法已经过测试，无法进行任何修改。

But why? The way this is phrased makes it sound like you wrote the algorithm, so why can't it be changed?

但是为什么呢?它的表达方式让它听起来像是你写的算法，所以为什么不能改变它呢?

#2

I agree with wlyles answer. Here are my thoughts:

我同意wlyles的回答。这里是我的想法:

There is an important question: How did you developers decide which was the best way? Do you know the exact weights of importance for the relevant measuring key data. For example total durations importance could be 0.2; live lost = 0.2; special items = 0.1; extra lives gained = 0.4; If you know this, you can easily compare a lot of different solutions to find your best one. But with your optimal solutions you should be able to generate such metrics or train a CNN with differnt solutions and their quality (0-1).

有一个重要的问题:您的开发人员如何决定哪一种方法是最好的?你知道有关测量关键数据的确切权重吗?例如，总持续时间的重要性可以是0.2;生活失去了= 0.2;特殊项目= 0.1;增加的生命数= 0.4;如果你知道这一点，你可以很容易地比较许多不同的解决方案来找到你最好的解决方案。但是有了您的最佳解决方案，您应该能够生成这样的度量，或者培训一个具有不同解决方案和质量的CNN(0-1)。

You do need different solutions of the maze to compare them though! If you dont have those solutions, you have to create them. It is not possible to fix your xml easily. Maybe there are parts of the xml that you can keep, but you need to write something to create new movement solution(s). Either by writing an algorithm which takes uses your weights to create the best solution or by creating a lot of different solutions and then comparing them to find your best one.

你确实需要不同的迷宫解决方案来比较它们!如果你没有这些解决方案，你必须创造它们。不可能轻松地修复xml。也许您可以保留xml的某些部分，但是您需要编写一些内容来创建新的移动解决方案。通过编写一个算法，使用你的权重来创建最好的解决方案，或者创建很多不同的解决方案，然后进行比较，找到最好的解决方案。

Maybe I got you wrong, but I dont think little adjustments in the xml file help, you need bigger changes in the xml (to the relevant parts at least).

也许我理解错了，但是我认为xml文件的一些调整并没有多大帮助，您需要对xml进行更大的修改(至少对相关部分)。

This might be obviously, but you dont really want to use the xml directly, but a parsed version of it. Otherwise you wont get any usable solution.

这可能很明显，但您并不想直接使用xml，而是使用解析后的xml。否则你将得不到任何可用的解决方案。

#3

As you mentioned in your question and comments, you don't want change algorithm for finding the best path and only, you are look for finding the best solution from generated solutions.

正如你在你的问题和评论中提到的，你不希望改变算法来找到最好的路径，你只希望从生成的解决方案中找到最好的解决方案。

You should notice that machine learning approaches are designed for optimizing some solutions by changing some factors like changing paths according weights in your issue to find best solution or close to best. But your issue is another story because you just need to a algorithm for checking XML files and finding the best without any changing in solutions.

您应该注意到，机器学习方法是为优化某些解决方案而设计的，方法是根据问题中的权重更改路径，以找到最佳解决方案或接近最佳解决方案。但是您的问题是另一个问题，因为您只需要一个算法来检查XML文件并找到最好的，而不需要改变解决方案。

To sum up, you need to a some testing approaches that it's very hard for each person that find one of them without knowing your scope of programs exactly.

总而言之，您需要一些测试方法，对于每个人来说，在不知道您的程序范围的情况下找到其中的一个是非常困难的。

#4

I fully understand the issue. My probability teach in college used to ask the same question a lot of times during the semester : If you have a perfectly shuffled deck of cards and you shuffled one more time. Was the deck more or less random?

我完全理解这个问题。我在大学教书的时候经常问同样的问题:如果你有一副洗得整整齐齐的牌，你又洗了一次。甲板是多还是少是随机的?

The answer was based on the criteria you were using to determine how random the deck was. Were you using the ranks of the cards or the suits. And what game were you playing. Bridge, 5 card stud, or 7 hand.

答案是基于你用来确定甲板的随机性的标准。你用的是牌的等级还是衣服的等级?你在玩什么游戏?桥，5张卡片，或7只手。

Over the years I played many games of cards with friends. I used to get upset when one friend used to shuffle the cards 8 and 10 times and slow down the game. Always thought of my professor.

这些年来，我和朋友们玩了很多纸牌游戏。我曾经因为一个朋友拖牌8次和10次而感到心烦意乱。总是想着我的教授。

About 25 years later I took a post graduate Probability course that included modeling. I had a final project that I had to pick. I wrote a program that shuffled decks of cards and used for the criteria the types of poker hand that were dealt for both 5 hand and 7 hand poker.

大约25年后，我参加了一个研究生概率课程，其中包括建模。我有一个最后的项目要选。我编写了一个程序，对牌组进行洗牌，并使用5手和7手牌的扑克类型作为标准。

My first results were strange. When I shuffled 1 and 8 times I got exactly same results. Also with 2 & 9, and then with 3 & 10. I finally found the issue. When you did a perfect shuffle by dividing the cards into 2 piles of 26 and then shuffled alternating the cards between the two pile, and did this 7 times you got the exact same deck as when you started.

我的第一个结果很奇怪。当我洗牌的时候，我得到了同样的结果。还有2和9，然后是3和10。我终于找到了问题所在。当你做了一个完美的洗牌，把牌分成两堆，总共26张，然后在两堆之间交替，这样做7次你得到的牌和开始时完全一样。

Lesson learned. Change the method of shuffling so it wasn't perfect. It is the same with your problem. As you developed different solutions you have to go back and reevaluate the criteria and in some cases go back and get additional inputs.

教训。改变洗牌的方法，使之不完美。这和你的问题是一样的。当你开发出不同的解决方案时，你必须回过头来重新评估这些标准，在某些情况下，返回并得到额外的输入。

I'm wondering if Dijkstra algorithm can help. You basically have a graph and like Dijkstra trying to get best path. With any graph solution you have Nodes with neighbors and trying to connect neighbors. So best solution is to first determine the nodes and neighbors. You input isn't clear as where the nodes and neighbors are located.

我想知道Dijkstra算法是否有帮助。你基本上有一个图，像Dijkstra试图找到最佳路径。对于任何图形解决方案，你都有节点和邻居，并试图连接邻居。所以最好的解决方案是首先确定节点和邻居。输入不清楚节点和邻居的位置。