Partitioned artificial intelligence for networked games

• US 8,137,199 B2
• Filed: 02/11/2008
• Issued: 03/20/2012
• Est. Priority Date: 02/11/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Calligaro, Michael P., Lorch, Jacob R., Wood, Randall C
• Primary Examiner(s): D'AGOSTINO, PAUL ANTHONY
• Application Number:
  US12/029,286
• Publication Number:
  US 20090203449A1
• Time in Patent Office: 1,499 Days
• Field of Search: 463/42
• US Class Current: 463/42
• CPC Class Codes: A63F 13/10 Control of the course of the game, e.g. start, progess, end
• CPC Class Codes: A63F 13/12 involving interaction between a plurality of game devices, e.g. transmisison or distribution systems protocols for networked virtual reality, networked games H04L29/06034
• CPC Class Codes: A63F 13/30 Interconnection arrangements between game servers and game devices; Interconnection arrangements between game devices; Interconnection arrangements between game servers
• CPC Class Codes: A63F 13/34 using peer-to-peer connections
• CPC Class Codes: A63F 13/355 Performing operations on behalf of clients with restricted processing capabilities, e.g. servers transform changing game scene into an encoded video stream for transmitting to a mobile phone or a thin client
• CPC Class Codes: A63F 13/358 Adapting the game course according to the network or server load, e.g. for reducing latency due to different connection speeds between clients
• CPC Class Codes: A63F 13/45 Controlling the progress of the video game
• CPC Class Codes: A63F 13/60 Generating or modifying game content before or while executing the game program, e.g. authoring tools specially adapted for game development or game-integrated level editor
• CPC Class Codes: A63F 2300/534 for network load management, e.g. bandwidth optimization, latency reduction
• CPC Class Codes: A63F 2300/538 for performing operations on behalf of the game client, e.g. rendering
• CPC Class Codes: A63F 2300/6009 for importing or creating game content, e.g. authoring tools during game development, adapting content to different platforms, use of a scripting language to create content
• CPC Class Codes: A63F 2300/63 for controlling the execution of the game in time

Abstract

Partitioned artificial intelligence (AI) for networked gaming. An exemplary system splits the AI into a computationally lightweight server-side component and a computationally intensive client-side component to harness the aggregate computational power of numerous gaming clients. Aggregating resources of many, even thousands of client machines enhances game realism in a manner that would be prohibitively expensive on the central server. The system is tolerant of latency between server and clients. Deterministic and stateless client-side components enable rapid handoff, preemptive migration, and replication of the client-side AI to address problems of client failure and game exploitation. The partitioned AI can support tactical gaming navigation, a challenging task to offload because of sensitivity to latency. The tactical navigation AI calculates influence fields partitioned into server-side and client-side components by means of a Taylor-series approximation.

Claims

1. A method implemented on a gaming server device that hosts an online game, the method comprising:

partitioning an artificial intelligence (AI) process for the online game into a tunable server-side AI component and a client-side AI component that provides tuning parameters for the server-side AI component, the server-side AI component being computationally simpler than the client-side AI component;

running the server-side AI component on the gaming server device;

offloading the client-side AI component to a gaming client device of a game player of the online game; and

receiving tuning parameters from the client-side AI component to tune the server-side AI component, wherein

the tuning parameters are usable by the server-side AI component over multiple game frames;

the server-side AI component is capable of tolerating stale tuning parameters;

the server-side AI component is capable of tolerating no reception of any tuning parameters for an extended interval of time; and

the server-side AI component includes a fallback mode in which the server-side AI component operates without input of any tuning parameters from the client-side AI component.

2. The method as recited in claim 1, wherein the server-side AI component and the client-side AI component are configured to tolerate remote computation latency.

3. The method as recited in claim 1, further comprising structuring the client-side AI component to be deterministic to produce identical tuning parameters when the gaming server device sends identical glimpses of a game state to the client-side AI component.

4. The method as recited in claim 1, wherein the client-side AI component comprises a stateless component, in which each glimpse of a game state provided by the gaming server device and each corresponding return of the tunable parameters from the gaming client device is independent of prior computations and does not depend on a carry-forward of a client-side state;

and

wherein when the gaming client device fails or becomes disconnected, the gaming server device offloads a same computation to another gaming client device.

5. The method as recited in claim 1, wherein the artificial intelligence process is related to tactical navigation of the online game, and the tactical navigation employs an aggregate vector field to determine movements of gaming characters;

and

wherein the server-side AI component selects which direction to move a gaming character of the gaming characters via the aggregate vector field calculated as a sum of influence fields radiating from the gaming characters in the game.

6. The method as recited in claim 1, wherein the client-side AI component performs AI computations for a gaming character that is in a different area of a game world than a gaming character of the gaming client'"'"'s local player.

7. The method as recited in claim 1, further comprising temporally limiting an effect of the gaming client device on the server-side AI component by preemptively migrating the client-side AI component via assigning successive computations for a gaming character to another gaming client device.

8. The method as recited in claim 1, further comprising replicating the client-side AI component to be offloaded to a subset of another one or more gaming client devices of another one or more game players of the online game.

9. The method as recited in claim 8, further comprising:

redundantly sending a same glimpse of a game state to the gaming client device and another one or more gaming client devices; and

accepting tuning parameters that are first received from among the gaming client device and another one or more gaming client devices to overcome a client failure.

10. The method as recited in claim 8, further comprising:

redundantly sending a same glimpse of a game state to the gaming client device and another one or more gaming client devices; and

applying a plurality voting scheme to tuning parameters received from the gaming client device and another one or more gaming client devices to overcome a tampered state of one of the gaming client device and another one or more gaming client devices.

11. The method as recited in claim 5, wherein a calculation of the aggregate vector field is partitioned between the server-side AI component and the client-side AI component via Taylor-series approximations;

wherein the server-side AI component sums the Taylor-series approximations of the influence fields radiating from the gaming characters, the Taylor-series approximations running at substantially a same rate as the gaming server device'"'"'s game loop; and

wherein the client-side AI component computes coefficients for the Taylor-series approximations based on influence fields emanating from a local subset of the gaming characters, the coefficients comprising the tuning parameters for the server-side AI component.

12. The method as recited in claim 5, wherein the client-side AI component uses an array of descriptors for each gaming character to calculate scalar coefficients for Taylor-series approximations of the aggregate vector field, including a position of each gaming character, a strength weighting of each influence field, and an exponential decay rate of each influence field;

and

wherein the scalar coefficients are computed based on a glimpse of a game state provided by the gaming server device when the gaming character of the game characters is at a given position in a virtual space.

13. A system implemented on a gaming server device, the system comprising:

a tunable server-side artificial intelligence (AI) component associated with the gaming server device to determine gaming character behaviors from an aggregate vector field representing gaming character positions and influences;

a complementary client-side AI component to intensively compute complex behavior possibilities of a local subset of gaming characters, the complementary client-side AI component being configured to be offloaded to a gaming client device;

wherein the server-side AI component non-intensively computes Taylor-series approximations and sums of influence fields to obtain the aggregate vector field;

wherein the client-side AI component intensively computes tuning parameters for tuning the Taylor-series approximations at the server-side AI component, the tuning parameters comprising coefficients representing the complex behavior possibilities; and

wherein the server-side AI component solicits the coefficients as advice from the client-side AI component by sending a glimpse of part of a game state to the gaming client device that runs the client-side AI component.

14. The system as recited in claim 13, wherein the client-side AI component provides a stateless and deterministic segment of a gaming AI, each glimpse-advice exchange between the gaming server device and the gaming client device comprising a standalone module of the gaming AI that can be executed interchangeably by the gaming client device, the standalone module running independently of prior computations and without dependence on a client-side state that has been carried forward.

15. The system as recited in claim 13, wherein the gaming server device uses the tuning parameters from the client-side AI component as the advice for improving behavior of a gaming character of the gaming characters;

and

wherein the gaming server device does not depend on the advice from the client-side AI component to satisfactorily run a game associated with the gaming character.

16. The system as recited in claim 13, further comprising running multiple different AI modules corresponding to different gaming characters;

and

wherein each AI module includes the server-side AI component and the client-side AI component, the client-side AI component being replicated to run on different gaming client devices.

17. The system as recited in claim 14, wherein the gaming server device redundantly offloads a same client-side AI computation to multiple gaming client devices to insure against failure of one of the gaming client devices or to detect a tampering or exploitation of one or more of the gaming client devices.

18. A system comprising:

means for partitioning artificial intelligence (AI) for gaming into a computationally lightweight AI process for a gaming server and a computationally intensive AI process for a gaming client, the computationally lightweight AI process determining gaming character movement using a Taylor-series approximation of an aggregate influence field representing summed influences of the gaming characters, and the computationally intensive AI process computing tuning parameters for the Taylor-series approximation; and

means for providing a glimpse of a current game state to the gaming client to solicit intensive computation to support the computationally lightweight AI process at the gaming server.