• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

ddyer

Members
  • Content count

    108
  • Joined

  • Last visited

Community Reputation

262 Neutral

About ddyer

  • Rank
    Member

Personal Information

  • Location
    Los Angeles
  1. I've added a new entry for my MCTS blog, for "Six Making", where I encountered a strongly counter-intuitive behavior by my MCTS framework.   http://www.gamedev.net/blog/2012/entry-2261672-mcts-ai-development-for-six-making/  
  2. Six Making is a fairly standard 2 player abstract strategy game. http://boardspace.net/sixmaking/english/Six-MaKING-rules-Eng-Ger-Fra-Ro-Hu.pdf Vis-a-vis other games in the same class, the interesting point is that it's in the class where winning is akin to solving a puzzle - finding or constructing a winning position - rather than accumulating a material advantage which eventually leads to a win. The first stage of development was a completely vanilla MCTS with 5 seconds per move, which proved to be very strong. As a practical matter for online play, I downgraded the initial version by making it play faster to produce an AI that could be beaten with a little practice. The surprise came when I tried (as a routine experiment) to make an even stronger AI by giving it more time. To my surprise, a robot given 30 seconds per move lost every game when played against the same robot given 5 seconds per move. 5 seconds/move also won against 300 seconds per move. This was so surprising and counter-intuitive that it inspired an extended investigation, partly as a hunt for bugs, partly as a quest to understand MCTS behavior better. The immediate cause turned out to be the limit on the size of the UCT tree. There is, and pretty much has to be, a hard limit on the size of the tree to prevent the robot running out of memory. Various strategies are employed to avoid hitting the limit by restricting growth of the tree, and by pruning parts of the tree that can't (or aren't likely to) affect the result of the search; but the limit ultimately remains. I found that by stopping the search when this limit is reached (a) at certain phases of the game, the longer-thinking robots stopped early. and (b) the normal more-time-is-better relationship returned. Phase 2: I investigated if this new stop condition applied to other games as well, and generally speaking it did not. Other games using the same engine seemed to continue getting stronger, given more time, even if the size limit was reached. Lots of thought, study of game trees, and some new tools to help visualize game trees, eventually resulted in this insight: The "random playout" portion of the search, below the leaf nodes of the tree, yields the "average" value of the game below that point. In some games, the average is also typical because the children are pretty similar, Hex and Go are in this class. In others, some children are very good and some are very bad and the average is not particularly representative of the true value (because real players don't make random moves, they try to make the best). Sixmaking is in this class. If you consider the state of the lowest levels of the tree when it is frozen by the memory limit, those nodes evaluations are still close to the "average" of the move evaluation. They've been selected for exploration, but have not yet been explored. As you continue running random games from those leaves, random deviations from those average values will be amplified. When you amplify noise, you get worse results.
  3. Six Making is a fairly standard 2 player abstract strategy game. http://boardspace.net/sixmaking/english/Six-MaKING-rules-Eng-Ger-Fra-Ro-Hu.pdf Vis-a-vis other games in the same class, the interesting point is that it's in the class where winning is akin to solving a puzzle - finding or constructing a winning position - rather than accumulating a material advantage which eventually leads to a win. The first stage of development was a completely vanilla MCTS with 5 seconds per move, which proved to be very strong. As a practical matter for online play, I downgraded the initial version by making it play faster to produce an AI that could be beaten with a little practice. The surprise came when I tried (as a routine experiment) to make an even stronger AI by giving it more time. To my surprise, a robot given 30 seconds per move lost every game when played against the same robot given 5 seconds per move. 5 seconds/move also won against 300 seconds per move. This was so surprising and counter-intuitive that it inspired an extended investigation, partly as a hunt for bugs, partly as a quest to understand MCTS behavior better. The immediate cause turned out to be the limit on the size of the UCT tree. There is, and pretty much has to be, a hard limit on the size of the tree to prevent the robot running out of memory. Various strategies are employed to avoid hitting the limit by restricting growth of the tree, and by pruning parts of the tree that can't (or aren't likely to) affect the result of the search; but the limit ultimately remains. I found that by stopping the search when this limit is reached (a) at certain phases of the game, the longer-thinking robots stopped early. and (b) the normal more-time-is-better relationship returned. Phase 2: I investigated if this new stop condition applied to other games as well, and generally speaking it did not. Other games using the same engine seemed to continue getting stronger, given more time, even if the size limit was reached. Lots of thought, study of game trees, and some new tools to help visualize game trees, eventually resulted in this insight: The "random playout" portion of the search, below the leaf nodes of the tree, yields the "average" value of the game below that point. In some games, the average is also typical because the children are pretty similar, Hex and Go are in this class. In others, some children are very good and some are very bad and the average is not particularly representative of the true value (because real players don't make random moves, they try to make the best). Sixmaking is in this class. If you consider the state of the lowest levels of the tree when it is frozen by the memory limit, those nodes evaluations are still close to the "average" of the move evaluation. They've been selected for exploration, but have not yet been explored. As you continue running random games from those leaves, random deviations from those average values will be amplified. When you amplify noise, you get worse results.
  4. The random playout part needs no special treatment for threads, but the UCT tree-building and feedback steps need to be carefully synchronized.   The most devilish part is, if your search optimization includes any pruning of the tree, considering what happens if you remove part of the tree that is in-use by some other thread.  
  5. http://www.gamedev.net/blog/2012/entry-2260725-mcts-ai-development-for-tammany-hall/
  6. This is a set of notes charting the development of a MCTS AI for Tammany Hall. The MCTS framework I use provides a few hooks to plug in the specifics for a particular game. The most important hooks are to generate a list of candidate moves, to generate a random candidate move, and to execute a chosen move. At the point this blog starts, the game engine is complete, able to generate and execute moves, and needs an AI. Tammany Hall is an area control game for 3-5 players, where players alternate between placing "bosses", collecting "influence" tokens, and conducting "elections" where the combination of bosses and influences feed into the score. Every move involves explicit interaction with the other players choices. The miracle or MCTS is that sometimes a move generator is all that's needed to play a somewhat plausible game. Not in this case. Phase 0: eliminate obviously bad moves. Some moves which are legal are so obviously bad that they can be eliminated from consideration. For example, expending votes in an election where you have no chance to win, or expending more influence (votes) than are needed to guarantee a win. Also in this category are generating moves that are functionally duplicates. AIs with this improvement always defeat those with only the baseline implementation, if only because they effectively get more playouts in a fixed allocation of time. Phase 1: Change from win/loss scoring to proportional scoring. The intent of this is to encourage the bot to always improve its score, even when it is far enough behind that it never wins. This makes the UCT feedback more sensitive to the actual outcome. This is particularly appropriate for games such as Tammany where the winning condition is a score rather than a situation such as checkmate. Tammany AIs with this improvement always win over win/loss bots. Phase 2: Add preliminary minimal evaluation weights to balance the dilution caused by similar moves. The basic concept is to seed "tree" moves with fake results from some number of imaginary playouts, and to seed "random" moves so that the probability of a move is proportional to its likelyhood in actual play. This is where simple heuristics such as "occupy empty wards" can be implemented. AIs with this method, and any plausible set of weights, defeat AIs without them. -- at this point in development, we leave the zone where each change is a miracle that immediately superceeds the previous version. The general mode I use is to play robot-vs-robot games, where all robots play using the same algorithm. Note the stupidist thing the losing bot does, imagine a new factor or change of weights that would change the stupid thing. One has to run multiple randomized trials to validate incremental improvements in the algorithm. Many supposed improvements don't generalize, or have unanticipated consequences. Phase 3: Add more specific weighting. Favor placing bosses in wards that influence more ethnic cubes. Discourage playing multiple bosses in the same ward. Phase 4: Consider if additional boss/cube placement swings the weight of influence in a ward in your favor, essentually "if the election happened now, could we win". Phase 5: Give the player in the lead less credit for his voting position, to encourage attacking him even if not strictly well founded. Phase 6: Adjust influence placement emphasis so that placing an outvoted boss, and then "slander" to immediately eliminate the opponent is more likely. Give bonuses for using this tactic against the players when they cannot retaliate due to turn order. Add weights to discourage slander that doesn't directly benefit us. Phase 7: Reduce the overall weight of the move biases, now that they are much more specific. This was based on the observation that UCT moves were not moving far from their a-priori positions as determined by the weights. Phase 8: Add move weighting for votes. The basic algorithm for generating "vote" moves is to generate all possible legal votes that otherwise pass the filter for pointless votes. This suffers from the same "dilution" effect that cube placement moves do; There might be a dozen ways to generate a vote of 4 chips, so without adjustment, a vote of 7 will be under-considered compared to a vote of 1. At this point in the development, many new ideas do not pan out, and the process or trying them out is very time consuming. My standard method for this game is to play a 4 player game all the way to the end, with 2 robots playing the "improved" algorithm and 2 robots playing the current standard algorithm. Score +2 if the two experimental AIs finish first and second. +1 if they finish first and third, - 1 if they finish second and fourth -2 if they finish third and fourth 0 otherwise. At about 40 minutes per game, it takes a long time to validate a genuine improvement, and shortcuts (running only a few games) risk approving a non-improvement, or rejecting a genuine improvement. For example, using this methodology to compare the current "best" algorithm to one a few steps back on the improvement chart, achieved a score of +7 out of a possible +34 on 17 games. It appears that the scope for further improvements by tinkering with move weighting (to encourage or discourage certain types of moves) is pretty small.
  7.  This is a set of notes charting the development of a MCTS AI for Tammany Hall.  ...   see http://www.gamedev.net/blog/2012/entry-2260725-mcts-ai-development-for-tammany-hall/
  8. You could run a very long search from the starting position, and save some fraction of the resulting tree. That would speed up the first few moves in some circumstances; but consider that you can only save a very small part of the precomputed tree, both as a practical matter, and because it would be mostly useless.   The problem is that a successful search tree is full of holes, corresponding to the nodes that were pruned out by alpha-beta.  As soon as your opponent steps off a path that you actually investigated, your saved tree is irrelevant.   So even if your search took 24 hours, reached 20 ply, and evaluated billions of terminal nodes, saving the entire result is almost pointless.   For the same reason, keeping the search tree and using it to seed the search tree for the next move, after the opponent responds, is mostly useless.  You have to discard 99% of the saved tree, and save only 1% of the time in the new search.
  9. I avoid this kind of problem by structuring my evaluator to calculate score for one player at a time, and subtracting the two. This has the advantage that the internal logic in the evaluator has only to add up positives and negatives for one player, which is easy to keep straight.   It also has the advantage that the same framework is easily adapted to more than 2 players.
  10. There's nothing sacred about uniformly selecting from the set of all possible moves.  Tricks (such as selecting the piece to move first) do change the distribution, but the proof is in the result, and in practice you can do a lot of not-quite legal things in the random phase of simulation to make it produce better results.  The requirement is to give good feedback up the tree, it doesn't matter how.
  11.   I think there's a bug, or at least something that I'm missing.   Does anyone have any ideas or suggestions about what the problem could be?    Thanks again!   The easiest bug to make and fix is to not adjust the value of the outcome for each node in the tree while traversing up to the root.  In simple two player games, this is to negate the outcome for each node as you ascend the tree.
  12. In situations where you will always lose, every move looks the same, so the choice of move is likely to appear random.  You can tweak this by adding a small bias to the evaluation function, so that losing in N moves is slightly better than losing in N-1 moves.   Of course, the #1 probability is that you have a bug propagating the win/loss values up the tree.
  13. The problem with building your own framework from scratch is that your mistakes will take a long time to become apparent.  A lot of things that seem perfectly fine on a small project with no users will not work well in practice.   Attach yourself to an existing game site whose games you like and dig in.
  14. Just try them all :) In complex games with many arbitrary factors, using a MCTS (Google it) search can be very effective.    You don't personally have to have any idea what strategy is best, and you won't have to rejigger your whole strategy every time something changes in the game.
  15. The quoted code for "cubic" cannot be correct. cubic(255,255,255,85,0.811) = 276 no way can a correct interpolated result be greater than any of the inputs.