Hot answers tagged

18

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

Just ignore the invalid moves. For exploration it is likely that you won't just execute the move with the highest probability, but instead choose moves randomly based on the outputted probability. If you only punish illegal moves they will still retain some probability (however small) and therefore will be executed from time to time (however seldom). So you ...


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 ...


11

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 ...


10

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 ...


10

Usually softmax methods in policy gradient methods using linear function approximation use the following formula to calculate the probability of choosing action $a$. Here, weights are $\theta$, and the features $\phi$ is a function of the current state $s$ and an action from the set of actions $A$. $$ \pi(\theta, a) = \frac{e^{\theta \phi(s, a)}}{\sum_{b \...


10

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

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

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

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

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 neutral 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 ...


7

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, ...


7

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....


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 faced a similar issue recently with Minesweeper. The way I solved it was by ignoring the illegal/invalid moves entirely. Use the Q-network to predict the Q-values for all of your actions (valid and invalid) Pre-process the Q-values by setting all of the invalid moves to a Q-value of zero/negative number (depends on your scenario) Use a policy of your ...


6

IMHO the idea of invalid moves is itself invalid. Imagine placing an "X" at coordinates (9, 9). You could consider it to be an invalid move and give it a negative reward. Absurd? Sure! But in fact your invalid moves are just a relic of the representation (which itself is straightforward and fine). The best treatment of them is to exclude them completely ...


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 &...


6

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. ...


6

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 ...


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

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 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 ...


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 ...


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

Blackjack is usually modelled using Monte Carlo (MC) Methods. There is a lot of literature on MC methods which is interesting on its own right but here is a paper describing how MC is applied to Blackjack. There is also a good description on page 110 of the Introduction to Reinforcement Learning. Good luck!


4

To build on Neil's answer a bit, you're right that the better your evaluation function gets, the less work your optimization function will need to perform. If your evaluation function gets good enough, you won't need to search at all. This is not just an academic idea though! It's actually fairly widely used, and has been key to solving several games. The ...


4

I understand your question to be: If some moves are compulsory, and my agent has no choice about which move to make next, do I need to perform a search, or can I just return the compulsory move? The answer depends on what your goal is. If your goal is to make an interactive agent that will play the game against you, then you are correct: there's no need ...


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