Saturday, July 30, 2016

Сунь-цзы "Искусство войны"

Я давно хотел прочитать эту книгу, так как видел ее во всех блуждающих по интернету списках "ОБЯЗАТЕЛЬНО ПРОЧИТАТЬ!!!! ЭТИ КНИГИ РЕКОМЕНДУЮТ ВСЕ!!!". Более того, название "Искусство войны" всегда было на слуху, и, с учетом моих взглядов на мир, я решил, что эта книга является универсальным трактатом не только для военных и увлеченных тактикой, но и для любого живущего на земле человека. Отчасти я оказался прав.

Вообще, если бы меня попросили описать "Исскуство войны" одной фразой, я бы переделал свое любимое высказывание "Лучше быть здоровым и богатым, чем бедным и больным" в "Буешь здоровым и богатым, тогда будет хорошо. Будешь бедным и больным, обязательно погибнешь". Сунь-цзы безусловно мудр и описывает очень важные вещи, но эти вещи ты вроде как понимаешь какой-то далекой частью сознания, и они довольно очевидны, но о применении их никогда не задумываешься.

Издание, которое попало мне в руки состояло из самого трактата на 10% и на 90% из комментариев и примечаний. Комментарии были довольно содержательны, с глубоким анализом существующих трактовок и множеством интереснейших исторических примеров. Но все же главной ценностью книги является сам трактат, который открыл мне несколько очень значимых мыслей. Я приведу здесь самое важное, что узнал и дам этому несколько иную трактовку, касательно того, как тот или иной совет можно применить в реальной, современной жизни.

Все мы знаем, что война это страшная и античеловечная вещь, но почему-то она существует. Существует она как и все в этом мире, ради чьей-то выгоды. Сунь-цзы говорит, что лучше всего когда войны нет. Лучший правитель и полководец тот, кто добивается победы без войны и без боя, без лишних потерь как человеческих, так и экономических. Война - один из способов, помогающих достичь определенной цели, но Сунь-цзы рассматривает ее исключительно как крайнюю меру. Причина довольно проста: затраты на ведение боевых действий могут превысить полученную выгоду. На войну следует идти только тогда, когда выгода от нее превосходит пологаемые затраты. Если есть стотысячное войско, то его содержит семьсот тысяч крестьян плюс нужно учесть, что затраты на клей и лак для колесниц, приемы послов, починку оборудования, перевозку составляют 1000 золотых в день (все цифры основаны на определенных фактах китайской истории, но мысль здесь ясна). Более того, на войну следует идти только когда 100% уверен в победе. Что нужно сделать, чтобы на 100% быть уверенным в победе, Сунь-цзы и описывает в своем трактате.

В переводе на реальную жизнь я бы мог сформулировать мысль так: не ввязывайтесь в какое-то дело, не сопоставив предполагаемые затраты и выгоды от него. Причем затраты нужно учитывать не только прямые, но и косвенные. Например, при самой бытовой ситуации, - переезде в более дешевую квартиру, в районе подальше, можно посчитать затраты на транспорт (бензин) в течение месяца для поездки на работу, в ближайший гипермаркет, в кино, стоимость доставки пиццы, или что вы там еще делаете. Кроме этого, один из самых важных ресурсов человека - это время. Подумайте сколько времени в этом случае вы потеряете и сможете ли вы его как-то возместить. Таким образом выигрывая в арендной плате, вы можете проиграть в других вещах суммарно больше. Возможно, пример звучит так себе, но это первое, что пришло в голову. Мысль такая: имейте цель, ищите как этой цели добиться, взвесьте затраты и выгоду и так решайте - двигаться вам по выбранному пути или нет.

Война это путь обмана - мысль, прошитая золотыми нитями через весь текст. Китайские воины не играли в благородных рыцарей, не утверждали лицемерно о честности и правдивости, а сообщали сразу, что будут лгать, хитрить и пользоваться любой слабостью противника. Я всегда думал, что это какая-то негласная правда, но оказывается уже несколько тысяч лет это установленная прописная истина. Очень важно на войне разными хитростями заставлять противника действовать так, как тебе угодно и не действовать так, как угодно противнику. Можно забирать у противника то, что ему дорого, чтобы отвлечь его силы от того, что нужно тебе. Можно подбрасывать ему ложную выгоду, чтобы он шел туда, куда нужно тебе. Можно показывать что ты слабый, чтобы он атаковал, а ты зажал его в тиски, можно, наоборот, показывать, что ты сильный, чтобы он отсутупил от нужного тебе места. Но чтобы знать как влиять на противника, нужно знать все про него: его силы, командование, настроения в армии и так далее. Для этого Сунь-цзы советует обязательно использовать шпионов и посвящает этому целую главу. Очень важно не дать противнику узнать ничего о себе, чтобы он повелся на твои хитрости и притворства. Для этого Сунь-цзы советует держать все в тайне, даже от своей армии, или даже лгать своим солдатам, чтобы дезинформировать противника.

Несмотря на то, что наша жизнь не война, и обманывать нехорошо, и шпионов под рукой нет, эту мысль также можно обратить и в наше повседневное русло. Смысл тут таков, что инициатива и контроль над всем, что происходит должны быть у вас в руках. В каждой ситуации нельзя расчитывать на авось. Нужно грамотно все расчитать, правильно понять обстановку и действовать так, чтобы добиться максимальной выгоды. Я поясню: допустим вы устраиваетесь на работу. Если вы делаете это впервые, вы понятия не имеете чего вам ждать на собеседовании. Здесь вы можете, конечно, слепо довериться своей интуиции и приготовить то, что считаете нужным для позиции, а можете поступить по-другому. Если вы опытный работник, с большой вероятностью, вы понимаете, что будет на собеседовании, но быть на 100% уверенным вы не можете. В этом случае, вам нужно узнать каков процесс собеседования в конкретной компании, и самое надежное узнать это у сотрудников компании. Если там есть знакомые, то все проще, если нет, можно спросить у менеджера по персоналу, или вообще найти разговорчивого сотрудника и пообщаться с ним. На собеседование вы придете с ответами на то, что вас точно будут спрашивать и, с большой вероятностью, вы получите работу.

Кстати, одним из самых важных моментов трактата я считаю высказывание Сунь-цзы, насчет того, что, зайдя глубоко на территорию противника, нужно грабить. Подвоз продовольствия через территорию чужого государства затруднен, поэтому нужно питаться за счет противника. Это значит, что в любой ситуации вы не просто должны получить выгоду в конце, вы должны получать ее в процессе, чтобы не изнурить свои силы и снизить затраты. Сунь-цзы также сообщает, что нельзя вести затяжную войну - ресурсы страны слишком быстро истощаются, а значит выгода от войны уменьшается. Эта мысль говорит нам - делайте все быстро. Не истощайте себя томительными ожиданиями и откладываниями. Нужно решать проблемы максимально активно, добиваясь любой ценой того, что вам нужно.

Полководец, вообще, (полководец - это вы, война - это ваши проблемы, а страна - это ваша жизнь) в понимании Сунь-цзы сверхчеловек. Это он выигрывает войну, он должен знать все про противника, он должен держать в голове план победы. Поэтому Сунь-цзы требует от полководца иметь все положительные качества, такие как ум, храбрость, строгость, гуманизм и беспристрастие. Если какого-то из этих качеств нет, существует вероятность, что победы такой полководец не достигнет. Не считайте, что вы, в мирное время, сможете достигнуть 100%  успеха, обладая одним или парой положительных качеств. Вы должны развивать в себе все: и смелость, и волю, и ум, и любовь к людям, и критическое мышление. Не думайте, что без чего-то одного все получится.

В программировании есть такое понятие как транзакция. Смысл в том, что есть какая-то группа из операций, которые нужно провести (например вставить сколько-то элементов и удалить другие) и эти операции либо выполняются все успешно, либо не выполняются вообще (ни одно). Так вот Сунь-цзы говорит так обо всем на войне. Либо вы используете все по-максимуму, либо проигрываете. Очень много внимания Сунь-цзы уделяет выбору местности и действиям в ней. Однако он также говорит, что местность это инструмент победы, и если правильно им пользоваться, победы можно достичь. Но это не значит, что выбрав лишь местность правильно вы обязательно победите. Также как и с качествами - для успеха следует уделять внимание всем аспектам, на него влияющим. Оставите что-то без внимания, 100% вероятности победить уже не будет.

Воины дерутся свирепо, только если отступать некуда и они смотрят в лицо смерти. Сунь-цзы прямо советует отрезать пути к отступлению перед битвой и говорить солдатам, что они идут на смерть. Тогда они не будут смерти бояться, а будут драться так, чтобы получить шанс на жизнь. По этой же причине, Сунь-цзы советует никогда не зажимать противника в угол, иначе его солдаты будут драться так, что смогут нанести тебе поражение. Это, вроде, довольно знаменитая техника в реальной жизни - отрезать себе пути к отступлению. От блокирования самому себе социальных сетей на работе, чтобы не отвлекаться, до увольнения с работы, чтобы начать новую жизнь

Итак, последняя мысль, которой я хотел бы уделить внимание, показалась самой важной для меня. Победу можно подготовить у себя, но реализовать ее, может только противник, показав свою слабость. Вы можете набрать сильную армию, сделать все по-правилам, укрепиться на правильной территории. Вы достаточно сильны, чтобы победить, но и противник достаточно силен, чтобы защищаться. Победить вам удастся только если противник допустит ошибку, значит ваша победа зависит от противника в равной степени, как и от вас. Вы можете сделать в жизни все правильно, подготовиться, натренироваться, прорепетировать, но всегда нужно ждать подходящей ситуации и выбирать правильный момент для реализации своих сил.

Я искренне советую всем прочитать эту книгу, так как она, как минимум интересна множеством исторических примеров, наполнена умнейшими мыслями китайской философии, и помогает понять некоторые очень важные вещи. Меня же, после прочтения, очень заинтересовала китайская история и мировоззрение древних китайцев, поэтому я, конечно же, добавлю в свой бесконечный список несколько книжек на эту тему.

Читайте интересные книжки!

Thursday, July 14, 2016

Ian Millington "Artificial intelligence for games"

The basic insight, that this book gave me is that AI is not a rocket science. Actually, Ian Millington says that AI is a handful of algorithms, which when combined performs a smart and interesting behaviour. Algorithms are generally simple and often has an O(n^2) complexity. The general value of this book, however, is that it gives you a good understanding of how AI should work in your game and how to build flexible, optimised and convenient architecture of your AI engine. I guess, it is not necessary to learn all these algorithms, that are in the book (however you definitely need to know, which algorithm solves which problem). If you plan to work with AI it is worth to get acquainted with this book. Here I will write general things that I think it is worth to keep in mind, without a detailed description of algorithms (when needed it can be found on the Internet).

I guess this will be last technical post which is so long. For future technical readings, I will write a short resume for each chapter. There will be more posts, but they will be shorter and more informative.

There are three key moments in AI engine:
  1. Movement
  2. Decision making
  3. Strategy
Movement and Decision-making are a single character behaviour algorithms, while Strategy is a group behaviour algorithm.

There are plenty of movement algorithms. In the most general way, we can divide it to Kinematic and Steering algorithms. Kinematic algorithms take static data (like current position and orientation and target position and orientation) and perform a stationary movement, without acceleration. Steering algorithms perform more complex behaviour with changing of acceleration and with using prediction methods to obtain a smarter movement method. The common interface for this set of algorithms is Steering, that contains all the kinematic data (like position, orientation, velocity and angular velocity) and the accelerations for both linear and angular. Each frame the game calls method update(steering, maxSpeed, time) for class Kinematic for each object in the game and this method updates current position, velocity and orientation of the character. From the whole diversity of steering algorithms, I want to pay attention to collision and wall avoidance algorithms. The most simple solution here is to cast a cone for each character and check if something lays within this cone. But this approach can produce some mistakes, like two characters can actually avoid each other if they continue to go straight, but can be in each other cones as well. Or two characters can collide, but neither of them is inside the cone.  The better solution here is to check if the characters will collide if they continue to move with the same speed. For wall avoidance, the simplest solution is to cast a ray and check if it crosses the wall. However, the trickiest thing here is the angles. The better solution is to cast multiple rays, but you can get stuck in the acute corner, so you need to be accurate with this. However, more rays mean more processing time, so it is worth to find the optimal number of rays.

Every moving algorithm works only with one variable (like position/orientation, velocity/rotation or acceleration). Very often we need to combine different movement behaviours into one. There are plenty of ways to do it. The first approach is weighted blending. In this, you need to determine weights for each behaviour and then sum up it together. This method has a bad side like you will not actually get a collision avoidance if other behaviours affect the result. Another way to do this is to use some arbitration system, which will decide which behaviour to choose in given moment of time. You can blend this two solutions.

The next big topic in movement is coordinated movement. The simplest method here is fixed formation, where you assign each character to each slot in a formation and treat one slot as a leader. The more scalable way is to use emergent formations like to set for each character another character as a target. We can totally remove the leader of the formation, by assigning invisible leader in the centre of mass of the formation. For more complex behaviours we can use the whole formation as a character, so we can make formations from other formations. Another interesting feature here is slot roles. We can have each slot with appropriate role (like melee or ranged) and character with another role cannot take it. This approach has some problems like if you have some melee fighters left, but without any available melee slots. In this case, the solution is soft rules. Soft rules mean that each slot has a cost for each type of unit. The problem for AI is to place a unit in such a way to obtain a minimum cost.

There are some algorithms with tricky situations like 3d movement or motor control in the book, but I would not pay attention to it here.

Pathfinding is a huge topic in AI. There are some implementations of Dijkstra and A* in the book. In brief, these two algorithms are similar. They work with directed weighted graphs, and have two lists for nodes they have already visited and nodes they want to visit right now. The difference between these two algorithms is that Dijkstra uses the exact cost for estimation of overall path cost, however, A* uses heuristics for this purpose. There are some optimisations for A* in the book, to increase execution time or memory expenses, but these situations seem like very rare.

The main problem of pathfinding is the world representation because we need to turn the continuous world into the discrete graph. The simplest case here is to turn the world into tiles and use them as the nodes of the graph. The second way is to use Dirichlet domains. It requires the level designer to put some characteristic points into the level. The Dirichlet domain is the cone that cast from the character point down to the bottom of the level. The next way to divide the world is the point-of-view method. In this method, we choose inflexion points near the convex vertices and use it as nodes of the graph. To check if they have a connection we just check if one point is visible from another point by ray casting. The last method is polygonal meshes, where you use each floor polygon as a node.

For huge levels, with different available actions, you can use hierarchical pathfinding. It looks like formations of formations but for pathfinding. It looks like if you need to go from one city to another you have the cities graph on the top of your hierarchy. If you have found a path between cities, you go deeper and try to find the path from your home to the airport. After you found it you start to search for the path to your bus stop and so on. To check where to go in the lower level you need to specify the exit nodes from the level. On each step, you do not need to process all the graph, but only the part that you need to execute now.

It is not necessary to use distance as a cost for pathfinding graph and positions for nodes. There is a solution for continuous pathfinding in the book (where the graph is changing over time) which uses different objects for the nodes and the costs.

The next chapter of the book is about decision making. When AI needs to represent smart behaviour it should decide what it should do next. For this kind of situations, decision trees can be used. The decision tree is the tree with decisions in the leaves and conditions in the nodes. Every edge represents an answer for the node condition. Decision trees should be balanced, and there are couple  algorithms for balancing it in the book. Also, there is an algorithm for the dynamic generating of the decision tree, when AI gets in different situations. The next way to implement decision making is state machines. State machines can be hierarchical and include another state machine as a state. There are tricky moments in the handling of hierarchical state but they are very easy to solve in the exact situation. Decision trees and state machines could be combined to one structure.

States, however, can be not clear and so fuzzy logic comes out. Fuzzy logic supposes that you can be in plenty of states partially. Unlike solid logic, where you do use logic operators like AND and OR, in fuzzy logic, you replace them with min() and max() functions respectively.

In the Goal Oriented Behaviour, every character has its own set of goals and actions that lead to fulfilling some goal. Every action has a positive value for some action and may have a negative value for some another action. The character uses these values to chose the only right decision.

In a rule-based system, you have a database of knowledge and the set of rules. When you parse the database you check which rule should be triggered now.  The most popular algorithm for matching rules is Rete. It represents rules as an acyclic directed graph, where each node of the graph represents some patterns of the rule, that leads to concrete action.

For merging decisions of different decision-making systems, you can use Blackboard architectures. In this algorithm, every decision-making system watches the blackboard where different data is represented. If the decision-making system found something that it needs to change it asks for having a control of the blackboard. Then special arbiter choose which system will have a control in the next iteration gives the control and system make some changes on the blackboard. Then you start again.

The last part of the AI engine is Strategy and tactics. It responds for the group AI behaviour. One of the most common methods in tactical AI is waypoint tactics. The level designer adds the waypoints to the level, that represents, for example, safe location for the characters. We can have different types of waypoints for the same level and then combine it to the graph. We can add the actions that will look for an appropriate waypoint to the decision tree of the character and this will cause smart behaviour. The waypoints can be generating automatically. There are couple ways: you can watch a player's behaviour and detect some waypoints or we can pre-test every point in the game if it is a candidate to the waypoint.

For tactical representation to the level, we can use an influence maps. Briefly, the approach is about calculating military influence for each position in the map. Every military unit has it's own influence formula, that calculates an influence with some decreasing, depending on the distance. For more realistic distribution we can use some algorithms from graphics, like filters (e.g. blur) or cellular automata.

We can force our AI to learn from the situation. We can keep death counter and kill counter for each position in the game, that have some deaths or kills. AI can avoid positions with large death counter, and try to place itself with the position with large kill counter.

For the tactical pathfinding, each edge of the graph will have different weight, depending on the goal of the character. We can tweak heuristics for A* here, for example.

For the group behaviour. it is better to use hierarchical AI. The general AI will issue orders for the army, the commander AI will issue the orders for the group, etc. We can also use the tactical waypoints to represent specific group behaviour (like tactically effective positions for taking a room). Every member of the AI team needs to send a signal about what he going to do now, and others should coordinate their intentions with it.

The next chapter is about learning, about neuro-networks and other stuff. The basic thing that you need to remember here is that in most cases you do not need learning. If you are implementing it, it means that likely you are doing something wrong. Usually, learning is needed before production, to not involve a level designer or a tester for it. But basically it is hard to debug learning algorithms and it can cause some problems. But it can help you to build a decision tree, or make your AI learn from the player.

Next chapter is about board games. There are some set of games, where you can predict every case of play. You can create a graph of all the cases and estimate the best set of moves. For this purpose, you can use minimax algorithm (that will maximise your profit for your turn and minimise it for opponent's turn to predict the overall path of the game). You can also use a technique that called open books. It consists of pre-computed costs of a different set of moves in some database, so for chess, for example, you don't need to force your AI to think in the first few steps.

For the games where you cannot build a tree of the game (because it is very huge) you can generalise some information to the larger cases, and use minimax for not exact moves.

The next set of chapters is about useful techniques that you can apply in your AI engine. First of all is Level of detail technique, that is very common in graphics. The whole point is to use less detail when you don't need. Like, don't use pathfinding in the city that you don't see on the screen. Or you can use only general modelling of some features in the city, like economics or the crime level, but not how these things happened.

The next technique is about world representation and how to build an event system for you AI. There are couple approaches that you can use like broadcasting or register individual listeners, I guess it is quite clear for all. You can also have the event-based approach for sense management, and register listeners for each character. Then either event manager or the character can check all the limitations and decide can the character, for example, hear the sound or not.

You can also find the basic approach to building an AI for each game genre in the end of the book. I will not describe it here because I think it is quite clear what techniques you should use for your own game. There is a very good questionnaire in the book if you have some difficulties with it.

I definitely will use this book if I decide to implement AI in my game. It is a step by step guide for building an AI, so you can actually call it a handbook for every AI developer.