Credit to github.com user ncsereoka - most of the framework for this package was cribbed directly from his repo risky-game
Risk® is a registered trademark of Hasbro, Inc. This code base is intended for educational or research purposes only. All rights and privileges belong to their respective owners.
This package serves as a framework for automating games of the board game Risk as a means to develop algorithmic and AI agents for research in the fields of Machine Learning, Deep Learning, Neural Networking, and general AI development.
This implementation is currently missing the following features:
- Cards
- Under published rules, cards are awarded when players capture territories, and can be traded in for units at the start of their turn. This mechanic is not currently implemented.
- Fortify
- Under published rules, a player may optionally move all but one unit from any territory they own into another adjacent territory they own. This mechanic is not currently implemented.
The game is divided into a series of Class objects. Their hierarchy is described as follows:
- Game
- State
- Player(s)
- Board
- Deck (not yet implemented)
Contains methods for rolling dice, resolving attack rounds, determining a winner, and turn order.
Stores the current state of the game in progress, including the Board itself and the Players playing the game. Contains methods to update heuristics related to the board state as a whole, generate a random board state, and generate lists of territories
(among other things)
Stores attributes related to the individuals or agent playing the game, and includes methods required to play a game. These methods include adding units to a Player's unit pool, allocating units to defend a territory, and the pattern of play used when attacking a territory (among others).
The algorithm a Player users to play a game. This implementation currenly includes a Human agent and a Random agent*.
* The Random Agent makes random legal decisions for every possible decision point with one exception - whether or not to attack. Under the published game rules, a player must decide whether or not to attack at the beginning of the turn and at the end of every combat round. In practice, setting this value to random results in non-terminating games when playing against other random agents as the density of attacks (that is to say the number of attacks that occur per turn) is too low to properly advance the game state toward conclusion. Instead, the unit counts tended to rise out of control (in at least one observed case, toward the thousands).
The board itself. Contains Territories, Continents (groups of Territories), and Borders (connections between Territories). Also contains methods to generate a Board from a database, and to identify which player owns which Territories / Continents.
The file risk/main.py serves as the entry point for the rest of the framework. Currently, this implementation assumes the use of a database backend (SQL Server in this case). The files in the SQL folder can be used to create a database to support this project. Additionally, the file ./sql/scripts/db_create.sql can be used to create the database and insert the default board all at once. Additionally, the files ./sql/schemas/sim.sql, ./sql/tables/sim/sim_games.sql, and ./sql/tables/sim/sim_rounds.sql can be used to create a schema to store simulated combats (see the ./model directory for more information).
Previous work on creating an AI to play Risk depends largely on predicting the probability that an attack against a particular territory will be successful. Statisticians generally use Markov Chains to determine nested probabilities (i.e. probability that D will occur given A, B, and C occurring in that order). While Markov Chains are very precise, they are A) computationally expensive, and B) not something I know how to implement.
The Model folder contains the file sim.py, which can be used to simulate attacks in which the Attacker keeps up the attack until either they are no longer allowed to do so or until all of the defender's units are destroyed.
The Model folder also includes a Jupyter notebook and two .json files. The .json files describe an XGBoost model and tuned hyperparameters generated from a series of simulations as described above - each combination of 1-30 Attackers and 1-30 Defenders was simulated 10,000 times each to generate a total of 9,000,000 simulated attacks. These attacks were fed into an XGBoost Classifier. This classifier then underwent hyperparameter tuning as described in the Jupyter file to produce the final model.
While not quite as accurate as the Markov Chain approach, this approach generates very close approximations of probability, and scales up well.
- Add the Card mechanic
- Add the Fortify mechanic
- Expose the board state to an Agent
- Currently, the board state is passed to the agent during specific function calls. This method makes the evaluation of board position and the planning of future moves inefficient, as separate function calls (and thus separate evaluations) would need to be made to first decide whether the agent want to attack or not and then to decide where and how to attack.
- By exposing the game state to the Agent directly, the Agent should be able to plan and then perform it's turn without creating multiple function calls
- Add functionality to Agent to determine where to place units during the Setup phase
$$
\begin{tabular}{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}\toprule 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\\n0.396226 & 0.102515 & 0.046726 & 0.024215 & 0.014092 & 0.008884 & 0.005827 & 0.003916 & 0.002727 & 0.001918 & 0.001365 & 0.000999 & 0.000744 & 0.000556 & 0.000419 & 0.000325 & 0.000250 & 0.000194 & 0.000154 & 0.000120 & 0.000095 & 0.000076 & 0.000061 & 0.000049 & 0.000040 & 0.000033 & 0.000027 & 0.000022 & 0.000019 & 0.000016 \\\n\midrule\n0.745919 & 0.338181 & 0.179840 & 0.099924 & 0.060099 & 0.038555 & 0.025549 & 0.017283 & 0.012083 & 0.008522 & 0.006078 & 0.004452 & 0.003318 & 0.002482 & 0.001873 & 0.001453 & 0.001119 & 0.000869 & 0.000687 & 0.000537 & 0.000426 & 0.000339 & 0.000274 & 0.000221 & 0.000180 & 0.000147 & 0.000121 & 0.000099 & 0.000083 & 0.000070 \\\n0.916882 & 0.657537 & 0.451730 & 0.294355 & 0.193719 & 0.130948 & 0.089683 & 0.061986 & 0.043937 & 0.031287 & 0.022460 & 0.016527 & 0.012355 & 0.009261 & 0.007003 & 0.005436 & 0.004192 & 0.003256 & 0.002577 & 0.002014 & 0.001599 & 0.001272 & 0.001029 & 0.000830 & 0.000677 & 0.000550 & 0.000454 & 0.000373 & 0.000313 & 0.000261 \\\n0.959600 & 0.805232 & 0.639524 & 0.473190 & 0.340955 & 0.244970 & 0.175010 & 0.124566 & 0.090044 & 0.065022 & 0.047142 & 0.034921 & 0.026230 & 0.019731 & 0.014959 & 0.011633 & 0.008983 & 0.006984 & 0.005532 & 0.004326 & 0.003438 & 0.002736 & 0.002214 & 0.001785 & 0.001457 & 0.001184 & 0.000977 & 0.000803 & 0.000674 & 0.000563 \\\n0.978396 & 0.887422 & 0.771827 & 0.631350 & 0.496578 & 0.382189 & 0.287988 & 0.213404 & 0.158726 & 0.117074 & 0.086200 & 0.064540 & 0.048850 & 0.036960 & 0.028140 & 0.021948 & 0.016988 & 0.013233 & 0.010494 & 0.008216 & 0.006534 & 0.005203 & 0.004213 & 0.003399 & 0.002774 & 0.002255 & 0.001860 & 0.001531 & 0.001283 & 0.001073 \\\n0.987584 & 0.932635 & 0.855927 & 0.750489 & 0.634025 & 0.520724 & 0.415333 & 0.322716 & 0.248893 & 0.188892 & 0.142127 & 0.108076 & 0.082738 & 0.063147 & 0.048392 & 0.037918 & 0.029458 & 0.023011 & 0.018286 & 0.014341 & 0.011419 & 0.009102 & 0.007375 & 0.005954 & 0.004861 & 0.003954 & 0.003263 & 0.002686 & 0.002252 & 0.001882 \\\n0.992461 & 0.958180 & 0.907681 & 0.832715 & 0.741407 & 0.642611 & 0.540364 & 0.440892 & 0.354171 & 0.278191 & 0.215182 & 0.167037 & 0.129889 & 0.100355 & 0.077627 & 0.061232 & 0.047829 & 0.037516 & 0.029904 & 0.023513 & 0.018758 & 0.014974 & 0.012147 & 0.009815 & 0.008020 & 0.006527 & 0.005388 & 0.004437 & 0.003721 & 0.003111 \\\n0.995176 & 0.972904 & 0.939053 & 0.886375 & 0.817952 & 0.738068 & 0.648179 & 0.552726 & 0.462193 & 0.376550 & 0.300540 & 0.239116 & 0.189586 & 0.148799 & 0.116520 & 0.092738 & 0.072974 & 0.057567 & 0.046082 & 0.036363 & 0.029086 & 0.023269 & 0.018906 & 0.015296 & 0.012511 & 0.010191 & 0.008418 & 0.006935 & 0.005820 & 0.004867 \\\n0.996834 & 0.982079 & 0.959210 & 0.922516 & 0.872732 & 0.811342 & 0.737662 & 0.653509 & 0.567409 & 0.479659 & 0.396057 & 0.324158 & 0.263104 & 0.210611 & 0.167563 & 0.134954 & 0.107257 & 0.085278 & 0.068666 & 0.054456 & 0.043723 & 0.035085 & 0.028570 & 0.023159 & 0.018970 & 0.015472 & 0.012791 & 0.010546 & 0.008855 & 0.007410 \\\n0.997808 & 0.987536 & 0.971429 & 0.945098 & 0.908382 & 0.861458 & 0.802587 & 0.731686 & 0.654749 & 0.571331 & 0.486696 & 0.409500 & 0.340470 & 0.278371 & 0.225429 & 0.184049 & 0.148000 & 0.118782 & 0.096332 & 0.076869 & 0.062008 & 0.049946 & 0.040789 & 0.033142 & 0.027197 & 0.022216 & 0.018389 & 0.015177 & 0.012752 & 0.010678 \\\n0.998506 & 0.991480 & 0.980368 & 0.961953 & 0.935742 & 0.901309 & 0.856553 & 0.800209 & 0.735826 & 0.661882 & 0.582046 & 0.504593 & 0.431240 & 0.361664 & 0.299454 & 0.248851 & 0.203272 & 0.165259 & 0.135374 & 0.108974 & 0.088502 & 0.071679 & 0.058784 & 0.047933 & 0.039443 & 0.032294 & 0.026778 & 0.022134 & 0.018619 & 0.015606 \\\n0.998964 & 0.994078 & 0.986308 & 0.973313 & 0.954559 & 0.929449 & 0.895981 & 0.852456 & 0.800717 & 0.738480 & 0.667650 & 0.595022 & 0.522385 & 0.449732 & 0.381425 & 0.323364 & 0.269025 & 0.222145 & 0.184243 & 0.149966 & 0.122854 & 0.100220 & 0.082648 & 0.067708 & 0.055921 & 0.045928 & 0.038176 & 0.031619 & 0.026638 & 0.022357 \\\n0.999249 & 0.995699 & 0.990034 & 0.980505 & 0.966632 & 0.947828 & 0.922350 & 0.888486 & 0.847115 & 0.795671 & 0.734767 & 0.669547 & 0.601321 & 0.529869 & 0.459556 & 0.397239 & 0.336662 & 0.282552 & 0.237490 & 0.195683 & 0.161880 & 0.133147 & 0.110511 & 0.091035 & 0.075515 & 0.062252 & 0.051894 & 0.043086 & 0.036368 & 0.030572 \\\n0.999453 & 0.996867 & 0.992728 & 0.985738 & 0.975496 & 0.961489 & 0.942276 & 0.916313 & 0.883918 & 0.842555 & 0.791972 & 0.735760 & 0.674560 & 0.607670 & 0.538866 & 0.475252 & 0.410888 & 0.351163 & 0.299730 & 0.250568 & 0.209756 & 0.174293 & 0.145838 & 0.120983 & 0.100925 & 0.083602 & 0.069957 & 0.058272 & 0.049307 & 0.041538 \\\n0.999597 & 0.997692 & 0.994638 & 0.989463 & 0.981847 & 0.971364 & 0.956857 & 0.937014 & 0.911861 & 0.879093 & 0.837991 & 0.790932 & 0.737959 & 0.677877 & 0.613555 & 0.551673 & 0.486555 & 0.423743 & 0.367704 & 0.312366 & 0.265049 & 0.222874 & 0.188296 & 0.157539 & 0.132333 & 0.110281 & 0.092721 & 0.077551 & 0.065828 & 0.055608 \\\n0.999703 & 0.998298 & 0.996042 & 0.992213 & 0.986558 & 0.978736 & 0.967840 & 0.952799 & 0.933502 & 0.907968 & 0.875290 & 0.836957 & 0.792587 & 0.740628 & 0.682977 & 0.625424 & 0.562524 & 0.499445 & 0.441057 & 0.381337 & 0.328564 & 0.280135 & 0.239410 & 0.202386 & 0.171465 & 0.143973 & 0.121784 & 0.102395 & 0.087272 & 0.073986 \\\n0.999777 & 0.998720 & 0.997023 & 0.994137 & 0.989864 & 0.983935 & 0.975636 & 0.964106 & 0.949186 & 0.929217 & 0.903280 & 0.872295 & 0.835654 & 0.791648 & 0.741377 & 0.689608 & 0.631130 & 0.570387 & 0.512192 & 0.450606 & 0.394357 & 0.341157 & 0.295200 & 0.252411 & 0.215916 & 0.182870 & 0.155777 & 0.131788 & 0.112869 & 0.096097 \\\n0.999829 & 0.999018 & 0.997715 & 0.995496 & 0.992206 & 0.987630 & 0.981203 & 0.972233 & 0.960553 & 0.944791 & 0.924095 & 0.899033 & 0.868910 & 0.832019 & 0.788891 & 0.743340 & 0.690441 & 0.633798 & 0.577835 & 0.516716 & 0.459112 & 0.402989 & 0.353167 & 0.305619 & 0.264149 & 0.225848 & 0.193898 & 0.165188 & 0.142260 & 0.121719 \\\n0.999868 & 0.999244 & 0.998240 & 0.996530 & 0.993991 & 0.990453 & 0.985472 & 0.978494 & 0.969365 & 0.956966 & 0.940547 & 0.920449 & 0.895977 & 0.865524 & 0.829232 & 0.790070 & 0.743478 & 0.692213 & 0.640108 & 0.581475 & 0.524486 & 0.467276 & 0.415031 & 0.363839 & 0.318088 & 0.274888 & 0.238134 & 0.204536 & 0.177306 & 0.152606 \\\n0.999900 & 0.999424 & 0.998659 & 0.997355 & 0.995416 & 0.992711 & 0.988895 & 0.983534 & 0.976492 & 0.966880 & 0.954062 & 0.938233 & 0.918748 & 0.894174 & 0.864403 & 0.831669 & 0.791877 & 0.746994 & 0.700146 & 0.645882 & 0.591502 & 0.535209 & 0.482245 & 0.428841 & 0.379795 & 0.332298 & 0.290948 & 0.252367 & 0.220535 & 0.191212 \\\n0.999921 & 0.999548 & 0.998947 & 0.997922 & 0.996398 & 0.994268 & 0.991260 & 0.987026 & 0.981449 & 0.973810 & 0.963572 & 0.950852 & 0.935072 & 0.914978 & 0.890342 & 0.862877 & 0.828945 & 0.789935 & 0.748360 & 0.699071 & 0.648413 & 0.594588 & 0.542607 & 0.488829 & 0.438186 & 0.387955 & 0.343240 & 0.300665 & 0.264900 & 0.231429 \\\n0.999938 & 0.999643 & 0.999169 & 0.998361 & 0.997157 & 0.995475 & 0.993095 & 0.989741 & 0.985314 & 0.979233 & 0.971052 & 0.960837 & 0.948089 & 0.931729 & 0.911477 & 0.888643 & 0.860053 & 0.826654 & 0.790418 & 0.746578 & 0.700490 & 0.650338 & 0.600705 & 0.548069 & 0.497259 & 0.445627 & 0.398594 & 0.352841 & 0.313653 & 0.276338 \\\n0.999951 & 0.999719 & 0.999346 & 0.998709 & 0.997761 & 0.996434 & 0.994557 & 0.991907 & 0.988404 & 0.983580 & 0.977072 & 0.968913 & 0.958681 & 0.945467 & 0.928980 & 0.910216 & 0.886457 & 0.858321 & 0.827321 & 0.789141 & 0.748184 & 0.702627 & 0.656496 & 0.606396 & 0.556841 & 0.505240 & 0.457103 & 0.409204 & 0.367309 & 0.326648 \\\n0.999961 & 0.999774 & 0.999473 & 0.998959 & 0.998195 & 0.997124 & 0.995609 & 0.993467 & 0.990633 & 0.986724 & 0.981439 & 0.974793 & 0.966429 & 0.955579 & 0.941961 & 0.926355 & 0.906428 & 0.882585 & 0.856004 & 0.822807 & 0.786621 & 0.745654 & 0.703380 & 0.656540 & 0.609231 & 0.558897 & 0.510927 & 0.462190 & 0.418715 & 0.375743 \\\n0.999969 & 0.999822 & 0.999584 & 0.999179 & 0.998575 & 0.997731 & 0.996533 & 0.994840 & 0.992597 & 0.989499 & 0.985302 & 0.980012 & 0.973333 & 0.964632 & 0.953655 & 0.940996 & 0.924708 & 0.905036 & 0.882862 & 0.854808 & 0.823756 & 0.787998 & 0.750406 & 0.707908 & 0.664054 & 0.616335 & 0.569803 & 0.521437 & 0.477336 & 0.432827 \\\n0.999975 & 0.999858 & 0.999669 & 0.999347 & 0.998867 & 0.998194 & 0.997241 & 0.995892 & 0.994103 & 0.991631 & 0.988275 & 0.984038 & 0.978674 & 0.971666 & 0.962787 & 0.952499 & 0.939181 & 0.922975 & 0.904549 & 0.880988 & 0.854583 & 0.823741 & 0.790804 & 0.752920 & 0.713084 & 0.668857 & 0.624817 & 0.578057 & 0.534515 & 0.489670 \\\n0.999980 & 0.999885 & 0.999733 & 0.999472 & 0.999083 & 0.998539 & 0.997768 & 0.996675 & 0.995226 & 0.993221 & 0.990498 & 0.987053 & 0.982685 & 0.976963 & 0.969693 & 0.961237 & 0.950241 & 0.936784 & 0.921379 & 0.901520 & 0.879045 & 0.852496 & 0.823783 & 0.790287 & 0.754512 & 0.714111 & 0.673149 & 0.628833 & 0.586786 & 0.542668 \\\n0.999984 & 0.999908 & 0.999785 & 0.999576 & 0.999263 & 0.998826 & 0.998206 & 0.997327 & 0.996161 & 0.994547 & 0.992351 & 0.989572 & 0.986041 & 0.981407 & 0.975505 & 0.968617 & 0.959627 & 0.948571 & 0.935842 & 0.919317 & 0.900455 & 0.877953 & 0.853343 & 0.824267 & 0.792769 & 0.756632 & 0.719369 & 0.678325 & 0.638663 & 0.596273 \\\n0.999987 & 0.999925 & 0.999825 & 0.999654 & 0.999399 & 0.999041 & 0.998535 & 0.997817 & 0.996864 & 0.995543 & 0.993747 & 0.991470 & 0.988575 & 0.984769 & 0.979912 & 0.974231 & 0.966794 & 0.957614 & 0.946998 & 0.933140 & 0.917219 & 0.898077 & 0.876957 & 0.851749 & 0.824126 & 0.792023 & 0.758448 & 0.720903 & 0.684045 & 0.644011 \\\n0.999990 & 0.999940 & 0.999860 & 0.999723 & 0.999520 & 0.999235 & 0.998830 & 0.998256 & 0.997494 & 0.996439 & 0.995001 & 0.993178 & 0.990857 & 0.987802 & 0.983896 & 0.979318 & 0.973309 & 0.965867 & 0.957226 & 0.945890 & 0.932786 & 0.916918 & 0.899263 & 0.877990 & 0.854420 & 0.826684 & 0.797272 & 0.763883 & 0.730579 & 0.693803 \\\n\bottomrule\n\end{tabular}\n
$$