********************** VAMPIRES Vs WEREWOLVES ********************** Command line to launch the client, default values for each parameter are precised between brackets (please just fill the host and port): .\bin\Twilight <host = 127.0.0.1> <port = 5555> <pseudo = Towelie> <max_depth = 4> <action_method = 4> <max_groups = 3> The whole "Twilight" project is written in C++, and generated with Microsoft Visual Studio 2017. STRUCTURE OF THE CODE The game is represented by classes: - a Group (in Group.h) is a number of vampires/werewolves/humans at a certain Point (in Point.h) of the map, it can also be a random battle between two groups - an Action is a list of Moves (in Action.h) to represent a possible turn of a player - a Map (in Map.h) holds the information about every Group in the map at a current state of the game - a State (in State.h) contains a Map, the player's turn, its probability if it was generated by a random battle The implementation of the Map interface used is MapGrid, holding a 2D array of structures containing the information about a Point in the map. NEXT STATES GENERATION In order to drastically reduce the number of possible actions a player can make at a current state of the game, and thus increase the depth of the game tree explored by the algorithm, no more than a dozens of customized actions per friendly group are generated (often less) by the actions_customized method of State object (in State.cpp) according to the current state of the game. A priority group of humans is a group of humans that can be captured before the opponent where the difference of distance between its closest gentil group and its vilain group is minimal. The method basically considers for a Group the moves in direction of the closest priority human groups, the closest non priority human group, the closest friendly group, the closest opponent group... The maximum number of friendly groups that this method can generate is also limited, still in order to reduce the size of the game tree to explore. For each Action, only the biggest Group is allow to split if the maximum number of groups is not reached. ALGORITHM The algorithm used is the expect Minimax with alpha-beta pruning algorithm, expect_minimax_alphabeta in minimax.h header file. Ths algorithm takes into account the probability of every outcome after a random battle. The method uses an object Chrono (in Chrono.h) to interrupt the exploration of the game by the algorithm in case the time spent for a turn reaches the 2 seconds limit. The algorithm also adapts its strategy to the opponent by speculating the maximum number of groups the opponent algorithm is allowed to split into. It makes the algorithm very strong against opponents who don't split. Finally, the IA can change its depth according to the current state of the game. For instance, when there is no human groups, the depth can be increased by 2. All these techniques allows the algorithm to have a default depth of 4 and to split into maximum 3 groups. HEURISTIC To evaluate the utility of a state, the algorithm uses a heuristic that basically considers groups of humans which can be captured before the opponent as owned. Thus, the total utility is equal to: 2 * (gentils - vilains) + (gentil_humans - vilain_humans). The number of monsters is multiplied by 2 to give more importance to actual groups than potential humans. When one of the player is 1.5 times more numerous than the other, the utility is different in order to favor the outnumber situations: 2 * (gentils - vilains) becomes equal to gentil or -vilain. For a terminal state (ie at least one of the two players lost every units), the utility is equal to: gentils + vilains + humans + 1 if gentil is winning, and the opposite if vilain is winning. So this utility is strictly greater (or lesser) than every utility that can be obtained in a state which is not terminal. It's important that a winning state has the greatest utility and a loosing state the worst. But these utilities cannot be too big, otherwise the IA will go into random battles every time it's possible to win, even if it's obviously not the best move. The utility and heuristic methods can be found in Map.cpp file.