U.S. Pat. No. 11,478,715

In one or more implementations, not all of the depicted components in each figure may be required, and one or more implementations may include additional components not shown in a figure. Variations in the arrangement and type of the components may be made without departing from the scope of the subject disclosure. Additional components, different components, or fewer components may be utilized within the scope of the subject disclosure.

DETAILED DESCRIPTION

In the following detailed description, numerous specific details are set forth to provide a full understanding of the present disclosure. It will be apparent, however, to one ordinarily skilled in the art that the embodiments of the present disclosure may be practiced without some of these specific details. In other instances, well-known structures and techniques have not been shown in detail so as not to obscure the disclosure.

Matching is a critical challenge in social networks, job marketing websites, shared-ride services, recommendation systems, and video games. High quality, efficiently implemented matches are imperative for ensuring a good user experience, perceived latency of the service, and cost-effective allocation of service resources. As matching applications rapidly grow, the number of candidates to be matched grows dramatically, increasing both the available candidate data and the dimensions of preference. This growth in size complicates maintaining high quality. Furthermore, finding a good match with reasonably short waiting times for each candidate within online applications introduces a new degree of complexity. All of these factors make the matching problem very challenging.

Many matching systems in production use a rule-based process to determine the quality of each match and then find matches with high qualities. When the number of candidates and the dimension of the data increase, a rule-based matching process becomes convoluted and impractical. Furthermore, defining a quality function to assess the quality of a given match can become very complicated in this situation. Researchers have used machine learning techniques to tackle the problem as a supervised learning problem and construct intricate match quality prediction models to consider various factors. However, given the outputs of nontrivial match quality function from machine learning, it could be even more challenging to construct a rule-based matching policy to optimize the outputs.

Video games, such as sports video games, first person shooter games, or other online games, often include a multiplayer mode allowing multiple players to connect online to interact with one another in the video game. Players may select a game mode they would like to play, and the video game may find other players looking to play the same game mode. The game will attempt to match players accordingly. However, the matches are not always ideal based on user preferences.

Conventionally, real-time matchmaking optimization is challenging for several reasons. For example, online user matchmaking typically involves high dimensional and complex condition satisfaction. The quality desired of matches are also often non-trivial (e.g., based on skill, country, etc.). There is also a dynamic pool of users to match and a speed requirement because users prefer quick matches. This all results in a very large-scale combinatorial problem. Additionally, users typically desire control of preferences to be able to further customize the matchmaking. For example, users may select a game mode to play (e.g., casual or competitive), and a preferred role (e.g., teammates, characters, etc.). Privacy is also a concern of users, so user data is limited for privacy and security reasons and unavailable to be utilized for matchmaking purposes.

Aspects of the present disclosure address these issues by providing for systems and methods for user-controllable model-driven online matchmaking. In an aspect, a predictive model is trained to estimate potential matchmaking quality under all controllable scenarios utilizing historical data. A locality embedding model may be trained to project matchmaking requests into an embedded space. Users may then be embedded to a lower dimension space and matched together based on the closest Euclidean distance. Both the trained predictive and locality embedding models may then be utilized together to perform user matchmaking.

The disclosed system addresses a problem in traditional video game player matchmaking tied to computer technology, namely, the technical problem of matching players online. The disclosed system solves this technical problem by providing a solution also rooted in computer technology, namely, by providing for user-controllable model-driven online matchmaking. The disclosed system also improves the functioning of the computer itself because it allows for efficiently generated fast matches of high quality based on user preferences.

In a 1-1 online matching scenario, when each user arrives, a matching request is initiated. The system searches for the possible and proper candidates. When a pair of users are matched, they are both removed from the system. In many applications, the matching requests arrive in sequence, and the system often manages a dynamic pool of candidates for future requests.

FIG. 1illustrates an exemplary system100for 1-1 user matchmaking, according to certain aspects of the present disclosure. The system100may include matchmaking requests102from multiple users to be matched with users in a waiting pool110. For example, the users in the waiting pool110may include users that have submitted a matchmaking request. As illustrated, candidates may be matched instantly104. If matches are not instant, the users may be added to the waiting pool until a match106is found. For example, the match106may be of users that were waiting in the waiting pool110.

According to aspects, the system100may receive a request102from a new user to find a match. The system100may then search candidates in the existing waiting pool110and find potential matches104,106. If the match is meets a distance threshold (e.g., a match threshold) the matched users are removed from the waiting pool110and returned as a matched pair104,106. If the match does not meet the distance threshold, then the request102from the new user is added to the waiting pool110for future matches. The waiting pool110may also be frequently scanned to match users based on relaxed criteria (e.g., a relaxed distance threshold) so that the users do not wait too long (e.g., over a minute).

Although the process inFIG. 1may appear straightforward, there are two main hidden challenges. The first challenge is how to search for a potentially good match from the waiting pool, especially when the match quality definition is complicated. A brute force method would visit every candidate pair in the waiting pool. However, it is neither practical nor scalable for online matching systems. Another solution is to build a search index system. Nevertheless, it still encounters challenges such as a high number of features, non-linearity in the search criteria, and the highly dynamic index insertions and deletions. The second challenge is to determine whether the system is supposed to match two candidates together immediately or keep both of them waiting for a better future match. Such a decision process needs a trade-off between a long waiting time with good future opportunities against fast matching with current openings. Note that solving the first challenge is the prerequisite of approaching the second challenge. To overcome these two challenges, a novel method is proposed to leverage recent advances in artificial neural networks to facilitate the online matching problem.

As will be described in more detail below, this method is comprised of 1) a neural network training process that learns an embedding for the quick nearest neighbor search in low dimensional space, and 2) a statistical matching process that determines whether to match with or wait for the best existing candidate. For example, the novel method may be applied to the 1-1 matching problem in an online video game. Because the novel method optimizes the matching strategy for any given match quality models, it can be extended to any 1-1 matching system in different applications, in addition to video game matchmaking.

FIG. 2illustrates an exemplary matchmaking system200, according to certain aspects of the present disclosure. The system200may include historical data202that is utilized for model training204. For example, the historical data202may include past user matches and user preferences used for those matches. The historical data202may be utilized to train an embedding model210and a matchmaking quality model218. For example, the embedding model210may be trained to embed users into embedded locations in an embedded space based on historical user data (e.g., from the historical data202). The matchmaking quality model218may train the embedding model210.

Once trained, the embedding model210may receive user control options206and new matchmaking requests208. For example, the user control options206may include a variety of user preferences, including, but not limited to, game modes, game roles, geography, ranking, skill, etc. The new matchmaking requests208may be requests from users that are not included in the historical data202. It is understood that as the new matchmaking requests208are received, the requests208are also saved in the historical data202to improve robustness of the historical data202.

According to aspects, the trained embedding model210may embed the users into embedded locations212based on the received user control options206and new matchmaking requests208. As a result, each user becomes represented as an embedded location (e.g., a point) in an embedded space (e.g., a three-dimensional space). Based on the embedded locations212, a nearest neighbor search may be performed based on a decision tree214. For example, the decision tree214may be configured to locate users closest to each other in the embedded space by continuously halving the embedded space until ideally only two users remain. These two users may then be matched together via a nearest neighbor search and cluster detection. The trained matchmaking quality model218may be utilized to train the embedding model210. The matchmaking results220may then be output.

According to aspects, a queue216may keep track of how long users have been waiting. For example, the longer a user has been waiting, the more relaxed the nearest neighbor search may be. This seeks to prevent users from waiting too long (e.g., over a minute).

FIG. 3illustrates an exemplary model training system300, according to certain aspects of the present disclosure. For example, the model training system300may be configured to train the embedding model210and the matchmaking quality model218ofFIG. 2.

According to aspects, the model training system300may include historical data302, a matchmaking data simulator304, a user control simulator306, random users308, neural networks320, and a matchmaking quality model314. For example, the matchmaking data simulator304and the user control simulator306may simulate user data and user preferences based on the historical data302to generate pairs of random users (e.g., first random users308a, second random users308b) for matching. The neural networks (e.g., a first neural network320a, a second neural network320b) may embed the random users308a,308binto respective embedded locations310a,310bbased on the simulated user data and user preferences. A distance312between the embedded locations310a,310bmay be calculated.

According to aspects, the matchmaking quality model314may simultaneously receive the simulated user data and user preferences to calculate a quality estimation316based on regression model training from the historical data302. The quality estimation316may be compared with the distance312to determine whether the match satisfies a match threshold. A network training signal318may then be generated based on whether the match satisfied the match threshold and utilized to further train the neural networks320.

FIGS. 4A and 4Billustrate additional exemplary model training systems400,450, according to certain aspects of the present disclosure. Referring toFIG. 4A, a model training system400may include training samples402, neural networks404a,404b, and a matchmaking quality function406.

According to aspects, for each training sample402, two candidates may be randomly selected from a historical dataset (e.g., historical data202,302ofFIGS. 1 and 2). For example, both the states of the candidates and preference vectors of the candidates may be embedded by a multi-layer perception neural network (e.g., neural networks404) to a low-dimensional space.

In an implementation high-quality matches may correlate with small Euclidean distances410. Therefore, compatibility of the candidate pairs may then be evaluated by a predefined match quality function406, where the training loss412measures the discrepancy between the Euclidean distance410of the two embedded positions and one minus the match quality score408. In mathematical form, this may be represented as:
∥f(xi,w)−f(xj,w)∥2≈1−q(xi,xj),  (1)

where f: Ru×1Rv×1denotes the embedding network mapping dimension u to v where v<<u. In the training process, the L2 distance may be minimized between the left and right-hand sides of Eqn. (1), where the training loss function is:

dist-embd(w)=∑i,j(f⁡(xi,w)-f⁡(xj,w)2-(1-q⁡(xi,xj)))2(2)

The loss function includes a square root operation that is not numerically stable for obtaining the gradient. Thus, the loss function └dist-embd (w) may be modified as:

∑i,j(f⁡(xi,w)-f⁡(xj,w)22-(1-q⁡(xi,xj)2))2❘"\[LeftBracketingBar]"1-q⁡(xi,xj)❘"\[RightBracketingBar]"+δ(3)

where δ is a small positive constant preventing division by zero.

Because the loss function only considers the relative difference between two outputs of the embedding network f, it is shift-invariant to the outputs. In other words, adding a constant value to the embedding network output does not affect the loss412. The match quality function406may thus be defined with an output range from zero to one, and a similar bounding box may be applied to the output of the embedding network400to increase numerical stability. Additionally, the tan h function may be utilized as the activation function of the last layer of multi-layer perception.

Referring toFIG. 4B, a model training system450may include training samples402a,402b, neural networks404a,404b,404c,404d, and a matchmaking quality functions406a,406b. Similar to the above inFIG. 4A, the Euclidean distances410a,410b, may be compared with quality scores408a,408bto determine a training loss412.

According to aspects, the distance being exactly equal to 1−q (e.g., the match quality value408) is not necessary. Because the best possible match candidates are discovered by the nearest neighbor search in the embedded space, the required condition is merely for the shorter distance to represent a better match (a higher value of q). This type of embedding may be referred to as an order embedding, where the loss function is computed as follows:

order-embd(w)=∑i,j,i′⁢j′,(q⁡(xi,xj)-q⁡(xi′,xj′))⨯Sign(f⁡(xi,w)-f⁡(xj,w)22-f⁡(xi′,w)-f⁡(xj′,w)22)(4)

The pairs (i, j) and (i′, j′) may be two arbitrary candidate pairs. The difference between the match qualities (xi, xj) and (xi′, xj′) serves as the weights of the order so that if the match quality difference between two pairs is large, it is more likely to generate a correct order of the distances. Therefore, the loss function is minimized if a positive difference between the match qualities is connected with a negative difference between the distances and vice versa. The modified final loss function to make the loss function more friendly to the gradient descent process is:

order-embd-m(w)=∑i,j,i′⁢j′,(q⁡(xi,xj)-q⁡(xi′,xj′))⨯(SoftSign⁡(f⁡(xi,w)-f⁡(xj,w)22-f⁡(xi′,w)-f⁡(xj′,w)22)+η⁢∑i,jf⁡(xi,w)-f⁡(xj,w)22(5)

where the SoftSign function is defined as:

SoftSign⁡(x)=x1+❘"\[LeftBracketingBar]"x❘"\[RightBracketingBar]"(6)

The last regularization term in Eqn. (5) is to ensure the numeric stability, and the hyper-parameter17determines how much the embedding positions should be close to each other.

According to aspects, data may be randomly generated with similar distribution to historical data, but with a wide probability span of input data. To preserve some of the inter-feature relationships, a Chow-Liu tree may be constructed between the features to extract the greatest mutual information while having a simple graph representation. For example, the data generation may include a traversal of the Chow-Liu tree with a Markov process. The generated data may then be combined with the real data (e.g., historical data) to be utilized in the training process.

According to aspects, it may be assumed that all candidates have the same distribution of good and bad matches among the total population. As a result, a Poisson random process may be utilized to model online request arrival scenarios. Therefore, the probability of having k matches with the quality less than c within waiting time t may be expressed as:i′

Pr⁡(∑i′⁢1⁢{xi′❘q⁡(xi,xi′)≤c,ti′≤ti+t}=k)=e-kk!′,(7)

where λ is the arrival rate with inputs c and t′, which is computed as:

(c,t)=t·∑j⁢1⁢{xi′❘q(xi,xi′}≤c}∑i′⁢1⁢{xi′}·∑i′1⁢{xi′❘0rwaitxi+rwaitxj(14)

The expected waiting reward can be further reduced if the waiting time penalty function has a closed-form. For example, the linear waiting time penalty function may be defined as:

p⁡(t)=1-tTmax⁢∀t∈[0,Tmax](15)

where Tmaxis the parameter that controls the decay speed, also known as the maximum waiting time. Then, the expected reward of waiting becomes a function that only depends on the request distribution and waiting time as follows:

r⁢waitui≈∫01c·dg(c)dc·(12⁢g⁡(c)-16⁢Tmax⁢g2(c))⁢dc(16)r⁢waitui≈∫01c·dg(c)dc·(1-ti-tjTmax2⁢g⁡(c)-16⁢Tmax⁢g2(c))⁢dc

It may be assumed that the function (c) is differentiable, otherwise, a discrete version can be derived. Note that rwaitxj≤p(t+(ti−tj))rwaitximeans the expected reward of waiting decreases faster than the expected reward of matching. Thus, two candidates who were previously decided not to be matched can become a match in Eqn. (11) after both of them wait for a certain amount of time, which is the desired behavior.

FIG. 5illustrates an exemplary system500for user matchmaking, in accordance with one or more implementations. For example the system500may include matchmaking requests502, a trained neural network504, a decision tree506, a queue508(e.g., a first in, first out (FIFO) queue), an expected rewards comparison510, and matches512,514. According to aspects, the system500may conduct matchmaking as described above in relation to Eqns. (7) through (16).

According to aspects, the system500may match users according to an algorithm based on a greedy strategy. For example, the algorithm may be defined as follows:

Initialize v-dimension R-tree

Initialize FIFO Queue

For all user request i=1, 2, 3, . . . doUse train embedding network yi←f (xi)if Find nearest neighbor j in R-tree with yithenCompute matching quality q(xi, xj)Compute expected rewards for waiting in Eqn. (10)and (11)if Eqn. (14) is true thenReturn matched pair xiand xjelseAdd i to Queue and yito the R-treeendelseAdd i to Queue and yito the R-treeendFor all First l candidates i′ in Queue doFind the best match j′if Waiting time is over maximum thenReturn matched pair xi′and xj′endCompute match quality q(xi, xj)Compute expected rewards in Eqn. (11)if Eqn. (14) is true thenReturn matched pair xi′and xj′endend

end

Specifically, the first half of the algorithm conducts neural network based location embedding and searches for the nearest neighbors with the help of an R-tree (e.g., the decision tree506). To manage the waiting pool, a FIFO queue508is used to prioritize some candidates502that have been waiting and not revisited by the algorithm for the longest time. In each iteration, the first1candidates in the waiting pool are retried to match with others in the pool. Empirically, a small number such as 3 for l is sufficient for most cases. If the system has a higher computing capacity, the value of l can be increased.

FIG. 6illustrates an exemplary system600for user matchmaking, in accordance with one or more implementations. In some implementations, system600may include one or more computing platforms602. Computing platform(s)602may be configured to communicate with one or more remote platforms604according to a client/server architecture, a peer-to-peer architecture, and/or other architectures. Remote platform(s)604may be configured to communicate with other remote platforms via computing platform(s)602and/or according to a client/server architecture, a peer-to-peer architecture, and/or other architectures. Users may access system600via remote platform(s)604.

Computing platform(s)602may be configured by machine-readable instructions606. Machine-readable instructions606may include one or more instruction modules. The instruction modules may include computer program modules. The instruction modules may include one or more of quality model training module608, embedding model training module610, user control option receiving module612, matchmaking request receiving module614, embedding module616, distance determining module618, user matching module620, and/or other instruction modules.

Quality model training module608may be configured to train a quality model. By way of non-limiting example, the quality model may be trained based on historical data.

Embedding model training module610may be configured to train an embedding model. By way of non-limiting example, the embedding model may be trained based on historical data.

User control option receiving module612may be configured to receive user control options from users.

Matchmaking request receiving module614may be configured to receive matchmaking requests from users.

Embedding module616may be configured to embed user data regarding the users into embedded locations.

Distance determining module618may be configured to determine a distance between two users. By way of non-limiting example, the distance may be a Euclidean distance.

User matching module620may be configured to match users based on a distance threshold.

In some implementations, computing platform(s)602, remote platform(s)604, and/or external resources624may be operatively linked via one or more electronic communication links. For example, such electronic communication links may be established, at least in part, via a network such as the Internet and/or other networks. It will be appreciated that this is not intended to be limiting, and that the scope of this disclosure includes implementations in which computing platform(s)602, remote platform(s)604, and/or external resources624may be operatively linked via some other communication media.

A given remote platform604may include one or more processors configured to execute computer program modules. The computer program modules may be configured to enable an expert or user associated with the given remote platform604to interface with system600and/or external resources624, and/or provide other functionality attributed herein to remote platform(s)604. By way of non-limiting example, a given remote platform604and/or a given computing platform602may include one or more of a server, a desktop computer, a laptop computer, a handheld computer, a tablet computing platform, a NetBook, a Smartphone, a gaming console, and/or other computing platforms.

External resources624may include sources of information outside of system600, external entities participating with system600, and/or other resources. In some implementations, some or all of the functionality attributed herein to external resources624may be provided by resources included in system600.

Computing platform(s)602may include electronic storage626, one or more processors628, and/or other components. Computing platform(s)602may include communication lines, or ports to enable the exchange of information with a network and/or other computing platforms. Illustration of computing platform(s)602inFIG. 6is not intended to be limiting. Computing platform(s)602may include a plurality of hardware, software, and/or firmware components operating together to provide the functionality attributed herein to computing platform(s)602. For example, computing platform(s)602may be implemented by a cloud of computing platforms operating together as computing platform(s)602.

Electronic storage626may comprise non-transitory storage media that electronically stores information. The electronic storage media of electronic storage626may include one or both of system storage that is provided integrally (i.e., substantially non-removable) with computing platform(s)602and/or removable storage that is removably connectable to computing platform(s)602via, for example, a port (e.g., a USB port, a firewire port, etc.) or a drive (e.g., a disk drive, etc.). Electronic storage626may include one or more of optically readable storage media (e.g., optical disks, etc.), magnetically readable storage media (e.g., magnetic tape, magnetic hard drive, floppy drive, etc.), electrical charge-based storage media (e.g., EEPROM, RAM, etc.), solid-state storage media (e.g., flash drive, etc.), and/or other electronically readable storage media. Electronic storage626may include one or more virtual storage resources (e.g., cloud storage, a virtual private network, and/or other virtual storage resources). Electronic storage626may store software algorithms, information determined by processor(s)628, information received from computing platform(s)602, information received from remote platform(s)604, and/or other information that enables computing platform(s)602to function as described herein.

Processor(s)628may be configured to provide information processing capabilities in computing platform(s)602. As such, processor(s)628may include one or more of a digital processor, an analog processor, a digital circuit designed to process information, an analog circuit designed to process information, a state machine, and/or other mechanisms for electronically processing information. Although processor(s)628is shown inFIG. 6as a single entity, this is for illustrative purposes only. In some implementations, processor(s)628may include a plurality of processing units. These processing units may be physically located within the same device, or processor(s)628may represent processing functionality of a plurality of devices operating in coordination. Processor(s)628may be configured to execute modules608,610,612,614,616,618, and/or620, and/or other modules. Processor(s)628may be configured to execute modules608,610,612,614,616,618, and/or620, and/or other modules by software, hardware, firmware, some combination of software, hardware, and/or firmware, and/or other mechanisms for configuring processing capabilities on processor(s)628. As used herein, the term “module” may refer to any component or set of components that perform the functionality attributed to the module. This may include one or more physical processors during execution of processor readable instructions, the processor readable instructions, circuitry, hardware, storage media, or any other components.

It should be appreciated that although modules608,610,612,614,616,618, and/or620are illustrated inFIG. 6as being implemented within a single processing unit, in implementations in which processor(s)628includes multiple processing units, one or more of modules608,610,612,614,616,618, and/or620may be implemented remotely from the other modules. The description of the functionality provided by the different modules608,610,612,614,616,618, and/or620described below is for illustrative purposes, and is not intended to be limiting, as any of modules608,610,612,614,616,618, and/or620may provide more or less functionality than is described. For example, one or more of modules608,610,612,614,616,618, and/or620may be eliminated, and some or all of its functionality may be provided by other ones of modules608,610,612,614,616,618, and/or620. As another example, processor(s)628may be configured to execute one or more additional modules that may perform some or all of the functionality attributed below to one of modules608,610,612,614,616,618, and/or620.

The techniques described herein may be implemented as method(s) that are performed by physical computing device(s), as one or more non-transitory computer-readable storage media storing instructions which, when executed by computing device(s), cause performance of the method(s), or, as physical computing device(s) that are specially configured with a combination of hardware and software that causes performance of the method(s).

FIG. 7illustrates an example flow diagram (e.g., process700) for user matchmaking, according to certain aspects of the disclosure. For explanatory purposes, the example process700is described herein with reference toFIGS. 1-6. Further, for explanatory purposes, the steps of the example process700are described herein as occurring in serial or linearly. However, multiple instances of the example process700may occur in parallel. For purposes of explanation of the subject technology, the process700will be discussed in reference toFIGS. 1-6.

At step702, a quality model and an embedding model are trained based on historical data and user control options. At step704user control options and matchmaking requests are received from users. At step706, user data regarding the users are embedded through the embedding model into embedded locations based on the received user control options and the matchmaking requests. At step708, a distance between two users that satisfies a distance threshold is determined based on the embedded user data. At step710, the two users are matched when the determined distance satisfies the distance threshold. According to aspects, multiple users may be matched when at least one of user preference stratification and matching quality satisfies a threshold.

For example, as described above in relation toFIGS. 1-6, at step702, a quality model (e.g., quality model218,314,406,510) and an embedding model (e.g., embedding model210,310,404,504) are trained based on historical data (e.g., historical data202,302). For example, the training may be performed through the quality model training module608and the embedding model training module610. At step704user control options (e.g., user options206) and matchmaking requests (e.g., requests102,208,502) are received from users. At step706, user data (e.g., control options206, requests208, historical data202) regarding the users are embedded through the embedding model into embedded locations (e.g., embedded location212) based on the received user control options and the matchmaking requests. At step708, a distance (e.g., distance312) between two users that satisfies a distance threshold is determined based on the embedded user data (e.g., embedded locations310). At step710, the two users are matched (e.g., results220) when the determined distance satisfies the distance threshold.

According to an aspect, training the quality model may further include receiving historical data, receiving a simulated match, outputting a quality estimation, and comparing the quality estimation with the simulated match.

According to an aspect, training the embedding model may further include receiving a simulated match between a first user and a second user based on historical data, embedding, through a first neural network, data of the first user into a first embedded location, embedding, through a second neural network, data of the second user into a second embedded location, calculating a distance between the first embedded location and the second embedded location, comparing a quality of the simulated match based on the calculated distance, and outputting a training signal to the first neural network and the second neural network based on the compared quality of the simulated match.

According to an aspect, the distance comprises a Euclidean distance. According to an aspect, the distance between the two users is determined based on a decision tree.

According to an aspect, the process700may further include outputting a matchmaking result comprising the two users.

According to an aspect, the process700may further include matching users when a waiting time has exceeded a waiting threshold for each of the users.

FIG. 8is a block diagram illustrating an exemplary computer system800with which aspects of the subject technology can be implemented. In certain aspects, the computer system800may be implemented using hardware or a combination of software and hardware, either in a dedicated server, integrated into another entity, or distributed across multiple entities.

Computer system800(e.g., server and/or client) includes a bus808or other communication mechanism for communicating information, and a processor802coupled with bus808for processing information. By way of example, the computer system800may be implemented with one or more processors802. Processor802may be a general-purpose microprocessor, a microcontroller, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), a Programmable Logic Device (PLD), a controller, a state machine, gated logic, discrete hardware components, or any other suitable entity that can perform calculations or other manipulations of information.

Computer system800can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them stored in an included memory804, such as a Random Access Memory (RAM), a flash memory, a Read Only Memory (ROM), a Programmable Read-Only Memory (PROM), an Erasable PROM (EPROM), registers, a hard disk, a removable disk, a CD-ROM, a DVD, or any other suitable storage device, coupled to bus808for storing information and instructions to be executed by processor802. The processor802and the memory804can be supplemented by, or incorporated in, special purpose logic circuitry.

The instructions may be stored in the memory804and implemented in one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, the computer system800, and according to any method well-known to those of skill in the art, including, but not limited to, computer languages such as data-oriented languages (e.g., SQL, dBase), system languages (e.g., C, Objective-C, C++, Assembly), architectural languages (e.g., Java, .NET), and application languages (e.g., PHP, Ruby, Perl, Python). Instructions may also be implemented in computer languages such as array languages, aspect-oriented languages, assembly languages, authoring languages, command line interface languages, compiled languages, concurrent languages, curly-bracket languages, dataflow languages, data-structured languages, declarative languages, esoteric languages, extension languages, fourth-generation languages, functional languages, interactive mode languages, interpreted languages, iterative languages, list-based languages, little languages, logic-based languages, machine languages, macro languages, metaprogramming languages, multiparadigm languages, numerical analysis, non-English-based languages, object-oriented class-based languages, object-oriented prototype-based languages, off-side rule languages, procedural languages, reflective languages, rule-based languages, scripting languages, stack-based languages, synchronous languages, syntax handling languages, visual languages, wirth languages, and xml-based languages. Memory804may also be used for storing temporary variable or other intermediate information during execution of instructions to be executed by processor802.

A computer program as discussed herein does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, subprograms, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output.

Computer system800further includes a data storage device806such as a magnetic disk or optical disk, coupled to bus808for storing information and instructions. Computer system800may be coupled via input/output module810to various devices. The input/output module810can be any input/output module. Exemplary input/output modules810include data ports such as USB ports. The input/output module810is configured to connect to a communications module812. Exemplary communications modules812include networking interface cards, such as Ethernet cards and modems. In certain aspects, the input/output module810is configured to connect to a plurality of devices, such as an input device814and/or an output device816. Exemplary input devices814include a keyboard and a pointing device, e.g., a mouse or a trackball, by which a user can provide input to the computer system800. Other kinds of input devices814can be used to provide for interaction with a user as well, such as a tactile input device, visual input device, audio input device, or brain-computer interface device. For example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback, and input from the user can be received in any form, including acoustic, speech, tactile, or brain wave input. Exemplary output devices816include display devices, such as an LCD (liquid crystal display) monitor, for displaying information to the user.

According to one aspect of the present disclosure, the above-described gaming systems can be implemented using a computer system800in response to processor802executing one or more sequences of one or more instructions contained in memory804. Such instructions may be read into memory804from another machine-readable medium, such as data storage device806. Execution of the sequences of instructions contained in the main memory804causes processor802to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in memory804. In alternative aspects, hard-wired circuitry may be used in place of or in combination with software instructions to implement various aspects of the present disclosure. Thus, aspects of the present disclosure are not limited to any specific combination of hardware circuitry and software.

Various aspects of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., such as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. The communication network can include, for example, any one or more of a LAN, a WAN, the Internet, and the like. Further, the communication network can include, but is not limited to, for example, any one or more of the following network topologies, including a bus network, a star network, a ring network, a mesh network, a star-bus network, tree or hierarchical network, or the like. The communications modules can be, for example, modems or Ethernet cards.

Computer system800can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other. Computer system800can be, for example, and without limitation, a desktop computer, laptop computer, or tablet computer. Computer system800can also be embedded in another device, for example, and without limitation, a mobile telephone, a PDA, a mobile audio player, a Global Positioning System (GPS) receiver, a video game console, and/or a television set top box.

The term “machine-readable storage medium” or “computer readable medium” as used herein refers to any medium or media that participates in providing instructions to processor802for execution. Such a medium may take many forms, including, but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as data storage device806. Volatile media include dynamic memory, such as memory804. Transmission media include coaxial cables, copper wire, and fiber optics, including the wires that comprise bus808. Common forms of machine-readable media include, for example, floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, DVD, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, an EPROM, a FLASH EPROM, any other memory chip or cartridge, or any other medium from which a computer can read. The machine-readable storage medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more of them.

As the user computing system800reads game data and provides a game, information may be read from the game data and stored in a memory device, such as the memory804. Additionally, data from the memory804servers accessed via a network the bus808, or the data storage806may be read and loaded into the memory804. Although data is described as being found in the memory804, it will be understood that data does not have to be stored in the memory804and may be stored in other memory accessible to the processor802or distributed among several media, such as the data storage806.

As used herein, the phrase “at least one of” preceding a series of items, with the terms “and” or “or” to separate any of the items, modifies the list as a whole, rather than each member of the list (i.e., each item). The phrase “at least one of” does not require selection of at least one item; rather, the phrase allows a meaning that includes at least one of any one of the items, and/or at least one of any combination of the items, and/or at least one of each of the items. By way of example, the phrases “at least one of A, B, and C” or “at least one of A, B, or C” each refer to only A, only B, or only C; any combination of A, B, and C; and/or at least one of each of A, B, and C.

To the extent that the terms “include”, “have”, or the like is used in the description or the claims, such term is intended to be inclusive in a manner similar to the term “comprise” as “comprise” is interpreted when employed as a transitional word in a claim. The word “exemplary” is used herein to mean “serving as an example, instance, or illustration”. Any embodiment described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments.

A reference to an element in the singular is not intended to mean “one and only one” unless specifically stated, but rather “one or more”. All structural and functional equivalents to the elements of the various configurations described throughout this disclosure that are known or later come to be known to those of ordinary skill in the art are expressly incorporated herein by reference and intended to be encompassed by the subject technology. Moreover, nothing disclosed herein is intended to be dedicated to the public regardless of whether such disclosure is explicitly recited in the above description.

While this specification contains many specifics, these should not be construed as limitations on the scope of what may be claimed, but rather as descriptions of particular implementations of the subject matter. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

The subject matter of this specification has been described in terms of particular aspects, but other aspects can be implemented and are within the scope of the following claims. For example, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed to achieve desirable results. The actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the aspects described above should not be understood as requiring such separation in all aspects, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products. Other variations are within the scope of the following claims.