Hot answers tagged

14

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


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

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


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


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


8

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


8

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


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

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


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


5

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


5

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


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

N.B The reason why I only chose these three algorithms was due to time I have available in understanding them. From a little research, I found that these algorithms are basically interweaved into the minimax algorithm. So if I can understand one then the other two will just fall into place. Given this context, I would recommend starting out with Minimax. 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

Welcome to AI.SE @Kate_Catelena! I teach AI courses at the undergraduate level, and so have seen a lot of semester projects over the years. Here are some templates that often lead to exciting outcomes: Pick a new board or card game, and write a program to play it. Your course has probably covered Adversarial Search, and may also have covered Monte Carlo ...


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

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


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

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


4

I don't think your network, trained using PPO to play a card game, already contains sufficient information to also use for drafting. I'm not saying this with 100% certainty, maybe there's something I'm overlooking, but I can't think of anything right now. A small adaptation to the network might be sufficient (though it would also involve re-training again). ...


4

What aspects of AI would be most applicable to creating a self learning game AI for a racing game (Q-Learning, NEAT etc) In general, you are looking at a problem that involves sequential decision making, in a machine learning context. If you are wanting to build an agent that can learn by receiving screen images, then NEAT cannot scale to that complexity ...


3

The second equation is correct. In TD($\lambda$), the $\lambda$ parameter can be tuned to smoothly vary between single-step updates (essentially what Sarsa does) in the case of $\lambda = 0$, and Monte-Carlo returns (using the full episode's returns) in the case of $\lambda = 1$. In the first equation, $\sum_{j = i}^{N - 1} \lambda^{j - i} d_i$ could be ...


3

As you mentioned in the question, you cannot solve all problems with decision trees. Decision trees usually works well in a turn-based game with a good heuristic function, but in RTS games takes a different approach. In the case of a very complex RTS game, one could implemented a rule-based AI. For example given it is the early game use all units to scout ...


3

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


3

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