Hot answers tagged

21

tl;dr: None of these algorithms are practical for modern work, but they are good places to start pedagogically. You should always prefer to use Alpha-Beta pruning over bare minimax search. You should prefer to use some form of heuristic guided search if you can come up with a useful heuristic. Coming up with a useful heuristic usually requires a lot of ...


16

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search. However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an ...


12

Good question! AlphaZero, though a major milestone, is most definitely not an AGI :) AlphaGo, though strong at the game of Go, is narrowly strong ("strong-narrow AI"), defined as strength in a single problem or type of problem (such as Go and other non-chance, perfect information games.) AGI, at minimum, must be about as strong as humans in all problems ...


11

Great question! NN is very promising for this type of problem: Giraffe Chess. Lai's accomplishment was considered to be a pretty big deal, but unfortunately came just a few months before AlphaGo took the spotlight. (It all turned out well, in that Lai was subsequently hired by DeepMind, although not so well for the Giraffe engine;) I've found Lai's ...


11

No, GANs are not used. It's reinforcement learning at what it does best. The tree search is an interesting addition and assists with navigating the sheer scale of the game. Although the agent was playing itself to become better, there wasn't 2 separate networks (generator and discriminator). The agent learned through RL and didn't have the error ...


9

A DeepStack-style algorithm only requires that you have a way of approximating equilibrium counterfactual values for subtrees at the leaves of lookahead trees from each of its decision points. So if I'm acting at the beginning of the pre-flop and I only have the time and memory available to look ahead to the start of the flop, then I need to approximate the ...


9

Assuming it is a turn-based game and, for each turn, there's an optimal choice that will lead to the winning state (zero-sum), you can basically simplify the question to "What is the optimal sequences of moves for me to win, considering the current situation that is presented on the board?". So you will need to perform your algorithm every turn as the ...


9

I would set up a list of goals for your bot. These could be 'maintain a minimum level of health', 'knock out human player', 'block way to location X', etc. This obviously depends on the domain of your MMO. Then you can use a planner to achieve these goals in the game. You define a set of actions with preconditions and effects, set the current goal, and the ...


8

So far, I have considered only three algorithms, namely, minimax, alpha-beta pruning, and Monte Carlo tree search (MCTS). Apparently, both the alpha-beta pruning and MCTS are extensions of the basic minimax algorithm. Given this context, I would recommend starting out with Minimax. Of the three algorithms, Minimax is the easiest to understand. Alpha-Beta, ...


8

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are: inserting elements testing if elements are already in there Pretty much every programming language should already have support for a data ...


8

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here: http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf A few key points: In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM....


8

Oliver Mason's answer is great for specific methods and tools to use, but I wanted to pull out a more general principle which was mentioned in a comment. The distinction your friend is making is not one that would be generally recognised. One of my university lecturers defined AI as something like "an artificial system that exhibits behaviour that resembles ...


7

I'm a chess player and my answer will be only on chess. Training a neural network with reinforcement learning isn't new, it has been done many times in the literature. I'll briefly explain the common strategies. The purpose of a network is to learn position evaluation. We all know a queen is stronger than a bishop, but can we make the network know about it ...


7

For Gomoku, it seems a bit of an overkill to use neural networks or the genetic algorithm as both take a while, and more often than not, don't go how you want it to. The Gomoku game tree is rather large, but you can get a decent AI from minimax, game tree pruning, and a good heuristic function (that includes counting half and full 2s,3s,4s,...etc.) as ...


7

A heuristic search using MCTS + minimax + alphabeta pruning is a highly efficient AI planning process. What the AI techniques of reinforcement learning (RL) plus neural networks (NNs) typically add to this is a way to establish better heuristics. My intuition tells me that this is way harder and far more complex. It's not actually that much more complex ...


7

Monte Carlo Tree Search is not usually thought of as a machine learning technique, but as a search technique. There are parallels (MCTS does try to learn general patterns from data, in a sense, but the patterns are not very general), but really MCTS is not a suitable algorithm for most learning problems. AlphaZero was a combination of several algorithms. ...


7

John's answer is correct in that MCTS is traditionally not viewed as a Machine Learning approach, but as a tree search algorithm, and that AlphaZero combines this with Machine Learning techniques (Deep Neural Networks and Reinforcement Learning). However, there are some interesting similarities between MCTS itself and Machine Learning. In some sense, MCTS ...


7

This is basically reinforcement learning. The state space contains your moves, and the value function are the value you store at the end. And your rewards are the end results. And you have episodic game. It is an AI method. Consider looking at value iteration, policy iteration, SARSA, Q-learning. The difference between neural network method and yours is you ...


6

I would like to use reinforcement learning to make the engine improve by playing against itself. I have been reading about the topic but I am still quite confused. Be warned: Reinforcement learning is a large complex subject. Although it might take you on a detour from game-playing bots, you may want to study RL basics. A good place to start is Sutton &...


5

We know what Lee's strategy was during the game, and it seems like the sort of thing that should work. Here's an article explaining it. Short version: yes, we know what went wrong, but probably not how to fix it yet. Basically, AlphaGo is good at making lots of small decisions well, and managing risk and uncertainty better than humans can. One of the things ...


5

Instead of having the AI learn what action to take, you can alternatively train it to judge how "good" a position is. In order to determine what move to make, you don't ask the AI "This is the current state, what move should I make", you iterate through all possible moves, and feed the the resulting state into the AI asking "How good do you think this new ...


5

This is fairly boilerplate advice, but, since you're brand new to AI, I'd personally suggest writing a classical Tic-Tac-Toe AI, ideally using minimax. I suggest this because minimax is fundamental to AI, and there are many webpages devoted to this subject, such as How to make your Tic Tac Toe game unbeatable by using the minimax algorithm and Tic Tac Toe: ...


5

A closely related question and a minimal implementation written in Python. That program implements the reinforcement learning technique 'Q-Learning'. The idea is for the program to take in an observation of the environment (which could be a screenshot if learning a computer game, or sensor data for a robot) and output a decision in the form of a vector of ...


5

Typically, Monte-Carlo Tree Search (MCTS) actually is the go-to "solution" for such problems with large branching factors. I can understand that "vanilla" MCTS may still have unsatisfactory performance, but there is a plethora of extensions/enhancements available. I don't have experience with the specific game you mentioned (Connect6), but from a quick look ...


5

Genetic algorithms and Neural Networks both are "general" methods, in the sense that they are not "domain-specific", they do not rely specifically on any domain knowledge of the game of Mario. So yes, if they can be used to successfully learn how to play Mario, it is likely that they can also be applied with similar success to other Platformers (or even ...


5

There is Google Research Football, which is an open-source platform to develop reinforcement learning algorithms to play a game similar to FIFA or PES, although the football simulation is not as realistic as the current versions of FIFA or PES. You can play this game against different RL agents (e.g. DQN or IMPALA) and, of course, you can even develop your ...


5

Overlap between AI and "Game AI" Nowadays, if you search for AI online, you will find a lot of material about machine learning, natural language processing, intelligent agents and neural networks. These are not the whole of AI by any means, expecially in a historical context, but they have recently been very successful, there is lots of published ...


4

I think you should get familiar with reinforcement learning. In this field of machine learning the agent interacts whit its environment and after that the agent gets some reward. Now, the agent is the neural network the environment is the game and the agent can get a reward +1 if it wins or -1 if loses. You can use this state, action, reward experienc tuple ...


4

In SC2, players have more control over every minuet mechanic (constructing buildings, resource mining and management, controlling minions...) in the game, thus putting more tactical responsibility on the burden of the player. In DOTA2, the player is only in control of the super-powered hero itself, and not much of the other aspects of the gameplay. It is ...


4

Those AI-learning programs may have very similar scheme. We are changing only inputs and possible actions (like "use skill" or "move here"). Starcraft AI must do a lot of actions and control many units. Dota is MOBA so bot should be good in positioning on map for example. Different opponents to destroy and target for win. AI needs to play many games for ...


Only top voted, non community-wiki answers of a minimum length are eligible