3
$\begingroup$

In lots of games there are multiple phases or decision points that are not similar yet seem to have a dependency on one another when taking the perspective of the overall strategy of the player. A couple examples I thought up:

  1. In a simple draw poker, you can have a strategy for discarding cards and a strategy for betting. They may not be mutually exclusive if you know your opponents betting will change with the number of cards you draw.

  2. In Cribbage there are two phases, Discard to crib and the Play. The Play phase is definitely dependent on which cards are discarded in the discard phase. So it seems knowledge of Play strategy would be needed to make the Discard decision.

The intent is to learn how to set up an unsupervised learning algorithm to play a game with multiple types of decision making. Doesn't matter the game. I'm at a loss at the highest level in what ML models to learn to use for this scenario. I don't think a single NN would work because of the different decision types.

My question is how are these dependencies handled in ML? What are some known algorithms/models that can handle this?

I'm at a loss on what to even search for so feel free to dump some terminology and keywords on me. =)

$\endgroup$
  • $\begingroup$ In your last sentence you are asking about handling different action phsaes in ML - i.e. machines learning to play games. Is that your intent? I'd like to check, because you could equally ask about how to deal with this issue in other approaches to game-playing AI, e.g. in game tree searches. $\endgroup$ – Neil Slater Sep 7 at 19:56
  • $\begingroup$ I'm not quite sure what you're saying, but I think 'machines learning to play games' is correct. The intent is to learn how to set up an unsupervised learning algorithm to play a game with multiple types of decision making. Doesn't matter the game. I'm at a loss at the highest level in what ML models to learn to use for this scenario. I don't think a single NN would work because of the different decision types. I'll have to read a bit more on game tree searches though. Added to question, I hope it helps. $\endgroup$ – paul_roland Sep 7 at 20:28
  • $\begingroup$ That's fine. I am asking because you originally only mentioned learning at the end, and the majority of AI game playing literature is not about learning algorithms. For instance the famous Deep Blue system that beat Kasperov is not a learning system. Learning systems based on self-play have become very fashionable recently (e.g. Alpha Zero) but AI applied to games has a varied history with many types of algorithm that can be made to work $\endgroup$ – Neil Slater Sep 7 at 20:36
  • $\begingroup$ Ah now I see! I'm definitely more interested in the ML solutions. This is a problem I thought of in trying learn more about ML. But I see now that there might be other types of algorithms outside of ML to tackle the problem. And if someone has a good idea outside of ML, I welcome that answer too. Thank you! $\endgroup$ – paul_roland Sep 7 at 21:02
1
$\begingroup$

Your intuition is correct, neural networks are a no go (except see bottom).

It seems like you'd want to look into the ML sub-field called Reinforcement Learning. In a nutshell, RL offers a set of methods to learn what is the best action to take in a given situation.

More formally, in RL settings the algorithm learns from experience by observing a reward ($R$) associated to an action ($a$).

RL problems can be conceptualized as Markov Decision Processes (MDPs). From Sutton & Barto:

MDPs are a classical formalization of sequential decision making, where actions influence not just immediate rewards, but also subsequent situations, or states, and through those future rewards.

MDP can be faced with several methods, mainly Monte Carlo Methods and Temporal-Difference Learning.

In short, both use the Bellman equation in different ways. A key component of the eq. is the discounting term ( $\gamma$ ). Values for rewards associated with future states are discounted (multiplied) by $\gamma<1$ in order to modulate the importance of future rewards.

Since you're concerned with strategy, another way to influence the agent's learning wrt. the environmental rewards is the adoption of an epsilon value $\epsilon<1$. When defining an $\epsilon$-greedy policy, the agent will choose the action with highest value $Q$ only with a probability equal to $1-\epsilon$. This enables the agent to balance exploitation of previous experience with the exploration of the environment. Very useful in cases where an immediate low reward compromises the achievement of a much higher reward later during the episode.

There's many other ways to influence the behaviour of your learner of choice to respond differently to its environment. For a complete view, I recommend Sutton and Burton who offer their book in pdf format for free at the given link.

Edit: almost forgot. Neural networks can be useful when combined with more classical RL methods, say Q-learning (a type of Temporal-difference learning), taking on the name of deep Q-learning. Alpha go also uses a combination of Monte Carlo methods combined with 2 NNs for Value evaluation and policy evaluation Wikipedia. I wouldn't necessarily venture in this domain without first having a clear overview of classical RL methods.

Hope this helps.

$\endgroup$
  • $\begingroup$ This absolutely did help! I'm not 100% there yet, but I believe you've sent me down the right path. For different states (what I called phases) there could be a completely different set of actions that may be mutually exclusive to the previous state's available actions. However, when I feed back the rewards it will capture the dependencies. Is this correct? And I will definitely take your advice master simpler problems first. $\endgroup$ – paul_roland Sep 8 at 14:35
  • $\begingroup$ States are different from timesteps. A scenario such as a card game is naturally structured by successive turns (timesteps). In each of them you would then observe the occurrence of one state between many possible ones. $\endgroup$ – nvergontbij Sep 11 at 9:27

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.