Predicting actions is a great way to give players a challenge by going from random selection to selection based on past actions. One way to implement learning is by using probabilities in order to predict what the player will do next, and that's what an N-Gram predictor does.
To predict the next choice, N-Gram predictors hold a record of the probabilities of making a decision (which is usually a move), given all combinations of choices for the previous n moves.
This recipe makes use of general types. It is recommended that we have at least a basic understanding of how they work because it's critical that we use them well.
The first thing to do is implement a data type for holding the actions and their probabilities; we'll call it KeyDataRecord.
The KeyDataReconrd.cs file should look like this:
using System.Collections;
using System.Collections.Generic;
public class KeyDataRecord<T>
{
public Dictionary<T, int> counts;
public int total;
public KeyDataRecord()
{
counts = new Dictionary<T, int>();
}
}Building N-Gram predictor is divided into five big steps. They are as follows:
- Create the general class within a file named exactly the same:
using System.Collections; using System.Collections.Generic; using System.Text; public class NGramPredictor<T> { private int nValue; private Dictionary<string, KeyDataRecord<T>> data; } - Implement the constructor for initializing the member variables:
public NGramPredictor(int windowSize) { nValue = windowSize + 1; data = new Dictionary<string, KeyDataRecord<T>>(); } - Implement a static function for converting a set of actions into a string key:
public static string ArrToStrKey(ref T[] actions) { StringBuilder builder = new StringBuilder(); foreach (T a in actions) { builder.Append(a.ToString()); } return builder.ToString(); } - Define the function for registering a set of sequences:
public void RegisterSequence(T[] actions) { string key = ArrToStrKey(ref actions); T val = actions[nValue - 1]; if (!data.ContainsKey(key)) data[key] = new KeyDataRecord<T>(); KeyDataRecord<T> kdr = data[key]; if (kdr.counts.ContainsKey(val)) kdr.counts[val] = 0; kdr.counts[val]++; kdr.total++; } - Finally, implement the function for computing the prediction of the best action to take:
public T GetMostLikely(T[] actions) { string key = ArrToStrKey(ref actions); KeyDataRecord<T> kdr = data[key]; int highestVal = 0; T bestAction = default(T); foreach (KeyValuePair<T,int> kvp in kdr.counts) { if (kvp.Value > highestVal) { bestAction = kvp.Key; highestVal = kvp.Value; } } return bestAction; }
The predictor registers a set of actions according to the size of the window (the number of actions to register in order to make predictions) and assigns them a resulting value. For example, having a window size of 3, the first three are saved as a key to predict that it's possible that the fourth one may follow.
The prediction function computes how likely it is for an action to be the one that follows, given a set of previous actions. The more registered actions, the more accurate the predictor will be (with some limitations).