4
$\begingroup$

To provide a bit of context, I'm a software engineer & game enthusiast (card games specially). The thing is I've always been interested in AI oriented to games. In college, I programmed my own Gomoku AI so i'm a bit familiar with the basic concepts of AI game oriented and have read books & articles about Game Theory as well.

My issue comes when I try to analyze AI's for Imperfect Information games like (Poker, Magic the gathering, Hearthstone, etc). In most cases when I found an AI for Hearthstone, it was either some sort of Monte Carlo or MinMax strategy. I honestly think although it might even provide some decent results it will still be always quite flat and linear since it doesn't take into account what deck the opponent is playing and almost always tries to follow the same game-plan, since it will not change based on tells your opponent might give away via cards played (hint that a human would catch).

I would like to know if using Neural Networks would be more better than just using a raw evaluation of board state + hands + Hp each turn without taking into account learning about possible threads the opponent might have, how to deny the opponent the best plays he could make, etc.

My intuition tells me that this is way harder and far more complex. Is that the only reason the NN method is not used?Has there been any research to prove how much efficiency edge would be between those 2 approaches?

$\endgroup$
  • 2
    $\begingroup$ Welcome to AI! Interesting question. I find it interesting that machine learning is performing so well with perfect information games, where indeterminacy is purely a function of complexity (intractability). Uncertainty arising from imperfect or incomplete information is distinct, and minimax is the hedge. CGT initially was focused only on perfect information games, until Fergusson (UCLA) and other started analyzing poker, so it may just be a matter of time before we see strong, narrow reinforcement learning producing the same results in this broader class of games... $\endgroup$ – DukeZhou Apr 4 '18 at 17:58
4
$\begingroup$

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 in concept. Replace the hand-coded heuristic with a learning engine, e.g. DQN or AC3. Train the learning engine from human expert play examples and/or from self play.

It is harder though, because there are many things that can go wrong with an NN-based estimator in a RL context. You will need to make many experiments with different hyper-parameters of the learning engine. For complex games, you may have to invest many 100s of hours of training, which you might want to compare against the end result of a similar amount of time spent refining expert heuristic systems.

For imperfect information games, you may also want to use something that can learn an internal state representation. That could be some kind of explicit belief state that you maintain like an expert system, or something that attempts to learn a good representation, such as an RNN (e.g. LSTM). This may not be necessary for a first try at an agent though, since the MCTS search will make up for some inadequacies of low accuracy heuristics.

Is that the only reason the NN method is not used?

Up until quite recently, approaches using RL and NN were far harder to find examples of outside of academic machine learning research, and there were not any pre-written frameworks for LSTM or e.g. AC3. In the last few years, RL and NN frameworks have started to appear making an AI self-learning approach far more approachable.

I would expect that many hobby-level coders considering game-playing AI nowadays would seriously take a look at RL and NNs in order to learn robust heuristics for their game projects. However, the "traditional" search-based methods still work in conjunction with these for a completed agent.

Has there been any research to prove how much efficiency edge would be between those 2 approaches?

For card games, I am not aware of any specific research, although I am just a hobbyist, yet to write any specific game engine more complex than tic-tac-toe.

For perfect information board games, the chess playing variant of AlphaZero demonstrates applicability of RL+NN self-play approach versus "traditional" heuristics plus search (represented by Stockfish). However, the framing of the tournament has been criticised as unfair to Stockfish, so it is not necessarily an open-and-shut case that RL is strictly better.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.