# Computerized Interactive Gaming via Supporting  Vector Machines

Authors: Y. Jiang; J. Jiang; I. J. Palmer
Journal: International Journal of Computer Games Technology
 (2008)

---

## Abstract

Computerized interactive gaming requires automatic processing of large volume of random data produced by players on spot, such as shooting, football kicking, and boxing. This paper describes a supporting vector machine-based artificial intelligence algorithm as one of the possible solutions to the problem of random data processing and the provision of interactive indication for further actions. In comparison with existing techniques, such as rule-based and neural networks, and so forth, our SVM-based interactive gaming algorithm has the features of (i) high-speed processing, providing instant response to the players, (ii) winner selection and control by one parameter, which can be predesigned and adjusted according to the needs of interaction and game design or specific level of difficulties, and (iii) detection of interaction points is adaptive to the input changes, and no labelled training data is required. Experiments on numerical simulation support that the proposed algorithm is robust to random noise, accurate in picking up winning data, and convenient for all interactive gaming designs.


---

## Body

## 1. Introduction

Over the past  decades, artificial intelligence in
computer gaming development  has
become an increasingly important research area,
and many researchers attempted and reported algorithms across a number of
disciplines including interactive gaming, character behaviour control, events
and activity simulation. Theoretical and practical advancements
have been made in building human-level AI systems, which enable data from other
entertainment sources such as “star trek” and “star wars”, to
seamlessly integrate with all level human capabilities. As a result,
interactive gaming assisted with AI techniques has evolved as one of the most
important research topics within the gaming industry as well as the research
community [1–3]. In a stream
of reports, papers, and  research seminars,  Laird and van Lent
[1] addressed this topic on
the basis of reviewing existing research on AI and gaming to describe different
game genres and to specify the roles that human-level AI could play within
these genres. In [4], neural network-based approaches are reported to
provide intelligence for characters in fighting action games. The described
approaches include three phases of designs, which are basic game rule learning and matches against
randomly acting opponents, evaluation of decision fitness by using the relative
score change caused by the decision, and training of neural network by using
the score difference and the previous input and output values which induced the
decision. The opponents' past actions are also utilized to find out the optimal
counteractions for the patterns, and experiments show that significant
understanding of the game rules is achieved by the proposed AI algorithm. AI
techniques are also playing leading roles for character-based design and
development [5, 6], which is essentially organized around the topic of
artificial characters. The work reported in [6] introduces an intermediate
architecture that fits between games and AI elements, and assesses the
feasibility of improving quality of game AI.Essentially, the AI system looks over the shoulder of players while they are
taking part and learns how they deal with issues incurred in fighting games,
interactive games, and all other games which require significant speed in
responding and reactions. As all games are required to target a range of
different players, however, capability to adapt to such changes of players and
thus their reactions is essential for any AI system design. For interactive games, one of the
major issues is to determine the interaction points out of the achievement data
produced by players, which can be modelled by a set ofN-dimensional random
points. The randomness comes from the fact that performances delivered by
players are generally subject to certain levels of statistics and probabilities. Therefore,
such interaction design problem can be modelled as an outlier detection, where
some dataset is drawn from an underlying probability distribution, and we want
to estimate a simple subset S of the input space as such that a test point
being outside S can be characterized by a priori.As one of the
most popular machine learning approaches, SVM has received tremendous attention
in a number of areas to deal with learning, training, and optimizing problems.
General SVM uses a kernel-mapping technique to separate linearly
nonseparable cases in high-dimensional space [7]. SVM not only
separates data
from different classes, but also separates data to its maximum margin. In other
words, SVM not only divides
mixed datasets into classes, but also optimizes such a classification. However, the
weakness of general SVM lies in the fact that it requires labeled datasets to
get it trained, yet interactive game design requires close-to-real randomness
and thus responses made by players or computer-simulated opponents could be
very diversified. To this end, the data produced by such random responses could
be difficult to label, or manual labeling could require significant resources
and time consumption.
To this end, we introduce a one-class-SVM and design an AI mechanism, which can
automatically process the random response datasets without any labeling
process, yet capable of detecting those characteristics out of the response
data randomly generated by either players or computer-simulated opponents.One-class-SVM is essentially an extension of support vector machines [8] used
for detecting the outliers [7, 9]. The idea is that it first maps the data into
high-dimensional space, and then maximizes the margin between the mapped data
and the origin. The main difference from general SVMs is the fact that a
constraint parameter ν is introduced to control the maximum
percentage of  outliers in the dataset, which can also be used to indicate the
priori. As a result, the one-class-SVM is capable of being adaptive to input
changes or different  players when used to design the interactive gaming. This
is because the priori specifies the maximum likelihood that outlier detections
can make, and hence such
detection is less sensitive to changes of inputs generated by different
players. In comparison with neural network-based approaches, SVM presents a
range of advantages, which can be summarized as: (i) while artificial neural
networks (ANNs) can suffer from multiple local minima, the solution to
an SVM is often global and unique; (ii) while ANNs use empirical risk
minimization, SVMs use structural risk minimization. As a result, the
computational complexity of SVM is not dependent on the dimensionality of the
input space, and SVMs can also have a simple geometric interpretation and can generate
a sparse solution; (iii) from wide range of reports on evaluation of both SVMs
and ANNs [10, 11], it is generally concluded that SVMs often outperform ANNs in
many classification-relevant applications due to the fact that they are less
prone to overfittings.The rest of the
paper is organised into three further sections, where Section2 is to describe
the proposed AI design for interactive gaming based on one-class-SVM. Section 3
reports the experimental results, and finally, Section 4 makes concluding
remarks.


## 2. Basic Concept Review of Support Vector Machine (SVM)

Supporting vector machine is a powerful classification tool widely used
in many areas of research and applications, especially for pattern recognition
and classifications [7, 9, 12]. Its basic concept can be best illustrated in a
linear classification with only two classes: ω1 and ω2.
Given N training  vectors, {x1,x2,…,xN}, being fed into an SVM, each vector will
have an output indicator yi={y1,y2,…,yN},
and a hyperplane g(x)=wTx+w0 needs to be determined, which can achieve the
following classifications: (1)forxi∈ω1:g(xi)=wTxi+w0≥1(yi=1),forxi∈ω2:g(xi)=wTxi+w0≤−1(yi=−1),where w=(w1,w2,…,wN) is referred to as supporting vectors as they
comprise the basic elements of the hyperplane for such binary classification. To
optimize the classification, w and w0 need to be determined as such that the cost
function J(w)≡(1/2)∥w∥2 is
minimized, subject to the condition: yi(wTxi+w0)≥1.To solve the above problem, the technique of Lagrange multipliers
is generally used, where a Lagrange function is introduced via combination of
the cost function with its constraint condition. This is defined as(2)L(w,w0,λ)=12wTw−∑i=1Nλi[yi(wTxi+w0)−1]. Therefore,
minimizing the cost function is equivalent to maximizing the Lagrange function,
and its corresponding solutions satisfy the following conditions [7, 9]: (3)∂L(w,w0,λ)∂w=0,(4)∂L(w,w0,λ)∂w0=0,(5)λi[yi(wTxi+w0)−1]=0,(6)λi≥0. From the above
conditions, the supporting vectors can be worked out as (7)w=∑i=1Nλiyixi. The Lagrange
multipliers λi can be determined from (8)∑i=1Nλiyi=0. To illustrate
the essential concept of SVM, we use a simple linear example, in which a
training set consists of four points with two classes given below (9)ω1={x1=[1,1]T,x2=[1,−1]T},ω2={x3=[−1,1]T,x4=[−1,−1]T}.  With the
Lagrange multiplier approach as explained above, the following equations can be
established from (7) and (8) since in this case we have y1=y2=1 and y3=y4=−1   as follows: (10)w1=λ1+λ2+λ3+λ4,w2=λ1+λ4−λ2−λ3λ1+λ2−λ3−λ4=0. According to
(5), however, we have (11)λ1(w1+w2+w0−1)=0,λ2(w1−w2+w0−1)=0,λ3(w1−w2−w0−1)=0,λ4(w1+w2−w0−1)=0. As (11) gives
us w1+w2=1 and w1−w2=1,
solutions to these two simultaneous equations give us w1=1 and w2=0.
By putting these solutions back to (11), it can be derived that w0=0.
As a result, the optimized hyperplane for dividing these two classes can be
determined as g(x)=wTx+w0=w1x1+w2x2+w0=x1=0.
Indeed, observations can easily reveal that all the four points become the
supporting vectors, and the margin of the separating hyperplane (line) from
both classes is equal to 1.For nonlinear
SVM-based classification, the concept is to map the input vectorsx∈Rl into another k-dimensional feature space: y∈Rk (normally k > l).
Consequently, the SVM classification becomes  (12)Assignxinω1ifg(x)=∑i=0NsλiyiK(xi,x)+w0>0,Assignxinω2ifg(x)=∑i=0NsλiyiK(xi,x)+w0<0,  where Ns is the total number of supporting vectors, K(xi,x) is known as a kernel function. When the input x∈Rl is mapped into another feature space via  ϕ:x→ϕ(x)∈ψ,
the inner product operation has an equivalent representation ∑rϕr(x)ϕr(z)=K(x,z),
where ϕr(x) is the r-component of the mapping ϕ(x) of x.
Typical examples of the kernel functions used in SVM include (i) polynomials: K(x,z)=(xTz+1)q,q>0;
(ii) radial basis functions (RBF): K(x,z)=exp(−∥x−z∥2/σ2),
which is also referred to as Gaussian kernel; and (iii) hyperbolic tangent: K(x,z)=tanh(βxTz+γ).
Formulation of SVM does not include
criteria to select a kernel function that gives good generalization, detection,
and classification. Its selection is dependent on the dataset to be classified
and applications involved. The general principle is to use Gaussian as the RBF
and its variance becomes essential in SVM design, which can often be estimated
and assessed via training data. On the other hand, the polynomial kernel
function is directional, that is, the output depends on the direction of the
two vectors in low-dimensional space. Extensive work has been carried out and
reported regarding the kernel selection, which can be generally classified as
(i) entropy-based approach [13] and (ii) empirical approach [11], where part of
training data is used to assess the effectiveness of the kernel candidates. In
our proposed algorithm, we used Gaussian as the RBF kernel for our SVM design.As seen, the
principle for linear SVM and nonlinear SVM remains the same, and the only
difference is that a feature space mappingx→ϕ(x) is applied to transform the nonlinear case
into a linear one, and thus the hyperplane can be determined through the inner
product of these mapping functions, that is, the kernels, since the kernels are
readily selected as one of the above three.


## 3. The Proposed SVM Interaction Design

The
scenario for interactive gaming is that among all the responses generated by
players or the simulated computer opponents, only a small proportion represents
high level hits, which need to be detected and picked up for the design of reactions.
This is a basic mechanism to make the game playing more challenging, which can
attract players to learn and improve their skills. Such a scenario can be
described by a dataset withT={x1,x2,…,xl},x∈RN,
as shown in Figure 1 for a two-dimensional case (N=2).
The task is to find a function f that generates the value “+1” for most of the
vectors in the dataset (marked as stars in Figure 1(a)), and “−1” for the other
very small part (marked as circles in Figure 1(a)). The strategy for such a
classification and detection is to use a one-class-SVM [8] and to map the input
data into a Hilbert space H according
to a mapping function X=ϕ(x),
as shown in Figure 1(b), and to separate the data from the origin to its
maximum margin.Data mapping by (a) one-class-SVM from input space  to (b) output space.
(a)(b)As a result, to separate the mapped
data from the origin to its maximum margin is equivalent to solving the
following quadratic optimization problem:(13)minw∈F:12||w||2+1νl∑iξi−ρ. Subject to (14)f(x)=wϕ(xi)−ρ≥−ξi,ξi>0,i=1,…,l, where ν∈(0,1) is a constraint parameter to limit the maximum
proportion of the high performance responses among all the ordinary responses
such that a maximum of ν×100% is expected to return negative values according to f(x)=w⋅ϕ(x)−ρ.  ξi are slack variables acting as penalties in the
objective function. Therefore, based on its dual representations, the
one-class-SVM is to solve the following problems.(1)
Select a kernel functionK(x,x′) in Hilbert space H,
and the sensitivity parameter ν to solve the following optimization problem
and find the solution of α*=(α1*,…,αl*) as follows: (15)minα:12∑i=1l∑j=1lαiαjK(xi,xj). Subject to (16)0≤αi≤1(ν⋅l),i=1,…,l, where  K(xi,xj)=ϕ(xi)⋅ϕ(xj) is the kernel function, and ∑i=1lαi=1.(2)
Select anyα* which satisfies 0<α*<1/(ν⋅l),
and calculate the bias ρ=∑ilαi*K(xi,xj).
The vectors that satisfy 0<α*<1/(ν⋅l) are called support vectors.(3)
Integrate the decision functionf(x)=∑i=1Nsvαi*K(xi,x)−ρ,
and if f(x)≥0,
it returns +1. Otherwise,
return the real negative value, where Nsv is the number of support  vectors.It is proved in [8] that ν×100 is the upper bound percentage of the data that
are expected to be outliers in the training data, and a vector xi is detected to be outlier in  the training set,
if and only if αi=1/(ν⋅l). αi is the parameter that directly determines the sensitivity of
outlier detection using one-class-SVM. Its selection is dependent on the
specific interactive game design and specific setting for the level of
difficulties, which is often dependent on individual players. In our simulated
experiments given in the next section, we constrained the maximum number of
interactive points to be detected at 20%.Figure2 illustrates the structure
of our proposed AI interactive game design, where the one-class-SVM is taken as
the core of the response data processing. Depending on the response data
capture mechanisms, further data preprocessing can be designed to improve the
SVM-based response data selection and classification. In our simulated
experiments, we designed the input response vector to contain the location of
the response, and the strength of the response. As a result, the input data is
a vector of three elements. Following the SVM-based data detection, a basic
clustering [14] is designed as a postprocessing to cluster the detected
response data into three categories, outstanding, excellent, and good, to
enable the game designers to allocate appropriate awards to the players’
performances. Essentially, all the three categories also represent the
interactive points, upon which further interactive actions can be designed
accordingly.Figure 2
Structural illustration of the SVM-based AI interaction design.


## 4. Simulated Experiments and Evaluation of the Proposed AI Design

In this section, numerical
experiments are carried out to demonstrate the effectiveness of the SVM-based
response data processing and the interactive gaming design. To evaluate the
proposed AI interactive algorithm, we designed a simple interactive game to
collect the training and testing data, where response is simulated by a
pseudorandom generation on a computer screen. While its hit-on-screen location
is represented by two coordinates (x, y),
its hitting strength can be represented by the intensity value of its display
on a grey level scales (0~255). To
simulate the different contexts and the varying nature of the input data
content, we randomly added bias data into the input data capture and asked
different players to generate the random input vectors. Following that,
performance evaluation and interaction are simulated by the proposed SVM-based system as
illustrated in Figure 2.Figure3 illustrates the simulated
experimental results, where the pink colour highlighted points are the high-performing
responses automatically detected by our proposed algorithm as the interactive
points that need to be further classified to determine the level of rewards for
the corresponding players, and those blue colour highlighted points are
ordinary responses that do not receive any rewards. As a matter of fact, those
high-performing responses represent the set of interactive points for general
game design, where interactive actions can be further designed according to the
specific needs of the game. The experimental results illustrated in Figure 3
prove that the proposed algorithm is capable of detecting those interactive
points or high performance responses automatically without any regards to who
the players are. As seen, not only those high-performing responses are
effectively detected by the SVM-based AI algorithm, but also their context
is adapted to automatically
by the proposed system.Summary illustration of experimental results.
(a)
player-1(b)
player-2(c)
player-3(d)
player-4Specifically, part (a) in Figure3
represents a less skilled player, whose high performance responses are detected
by the proposed AI algorithm with an equivalent threshold at around 38. The
player who generated the experimental results in part (b) of Figure 3 is better
skilled, where his high performance responses are detected with an equivalent
threshold at around 70. Further observation reveals that the part (c) and part
(d) of Figure 3 represent even better skilled players, where their high
performances are detected with equivalent thresholds at around 81 and 85,
respectively. With the proposed algorithm, no labelled data is required for
both training and testing. The proposed algorithm is capable of automatically
adapting to the different players and detecting their high performance
responses. In contrast, existing rule-based approaches [12] would have to set
up different thresholds for all the four players. With general SVM or neural
network approaches [4, 13], separate training with labelled data for each of
the four players will also be required in order to make them adaptive to other
unseen players with different skills. As interaction is desired to be tailored
for individual players, the advantage that the proposed AI algorithm is not
only capable of detecting high performance responses (outliers) but also
adapting to their context changes would prove very useful for practical
interactive game designs and developments.In addition, the proposed algorithm
is fully automatic and computerized, in which only a few initial sample testing
is needed depending on specific gaming design, and such initial sample testing
is often helpful for the designed interactive system to collect training data
and thus to get the
SVM element trained to allow the system to learn from the players, especially
when the player is first time encountered.


## 5. Conclusions

While existing
AI techniques developed for interactive gaming are mostly focused on neural
networks and rule-based approaches, we propose an SVM-based approach in this
paper to illustrate the effectiveness and efficiency in processing responses
and to generate reactions. Compared with other AI techniques, the proposed has
the features of: (i) self-adaptive to the response data content by controlling
one trade off parameter; (ii) detection of high-performing responses according
to the context the responses are generated; (iii) training does not require any
labeled data, which can be very useful for circumstances where manual labeling
is labour intensive and time consuming. Following the proposed AI design, a
number of options can be further designed for specific reactions to the
detected responses, such as awards, penalties, or any other actions that can
further stimulate responses. Therefore, the proposed AI design can
have many useful applications in practical computer game design when
interaction is required.



---

*Source: 186941-2009-01-25.xml*