I built a card game prototype, wondering about performance

[kasbah]

Hello all, happy New Year!

I built a card game prototype using the new library interface:

• It's a Top Trumps style game using planets and exo-planets
• The rules are defined in Prolog and very inspired by the Game Description Language. The relevant source file is logic.pl
  • The cards are the only defined facts
  • There's an init rule that gives us the initial game state
  • There's a random_options rule that gives us things to randomize based on the game state
  • There's a next rule to advance the game state
  • There's a sees rule that tells us what each player can see
  • There's a player_options rule that gives a player the possible moves based on the game state
• This is all pulled together in Rust, in the main game loop: game_logic.rs. It queries these rules in order in a loop and modifies the game state. The idea being you could change the logic of the game in Prolog and it would continue to work without modifying the Rust code.
• It has a rudimentary inefficient AI that does a Monte-Carlo-esque thing (but backwards in time instead of forwards? 🤔), again, the idea being to develop an AI that would continue to work if the game rules are changed
• I did wrap Scryer in an Actix actor so the AI, for instance, can query 6 Scryer machines running on separate threads.

You can clone the repo and run the game. It will print some game state and then the AI will start thinking about which category to pick. Once it figures it out you will be shown which cards were drawn. If the AI ever loses it's your turn to pick the category.

git clone https://github.com/kasbah/cardgame-scryer/
cd cardgame-scryer
cargo run --release 

example output

   Compiling cardgame v0.1.0 (/home/kaspar/projects/blank-planet/scryer/cardgame)
    Finished `release` profile [optimized] target(s) in 5.12s
     Running `target/release/cardgame`
Game phase: dealing
Player turn: none
Your cards: 0
Opponent cards: 1
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 1
Opponent cards: 1
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 1
Opponent cards: 2
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 2
Opponent cards: 2
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 2
Opponent cards: 3
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 3
Opponent cards: 3
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 3
Opponent cards: 4
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 4
Opponent cards: 4
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 4
Opponent cards: 5
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 5
Opponent cards: 5
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 5
Opponent cards: 6
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 6
Opponent cards: 6
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 6
Opponent cards: 7
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 7
Opponent cards: 7
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 7
Opponent cards: 8
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 8
Opponent cards: 8
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 8
Opponent cards: 9
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 9
Opponent cards: 9
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 9
Opponent cards: 10
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 10
Opponent cards: 10
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 10
Opponent cards: 11
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 11
Opponent cards: 11
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 11
Opponent cards: 12
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 12
Opponent cards: 12
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 12
Opponent cards: 13
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 13
Opponent cards: 13
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 13
Opponent cards: 14
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 14
Opponent cards: 14
------------------------------------
Game phase: dealing
Player turn: none
Your cards: 14
Opponent cards: 15
------------------------------------
Game phase: playing
Player turn: player1
Your cards: 15
Opponent cards: 15
------------------------------------
Game phase: scoring
Player turn: player1
Your cards: 14
Opponent cards: 14
Opponent picked: Compound("category", [Integer(0), Atom("distance")])
------------------------------------
Your card:
Name:             c_hat_p_7_b
Distance:         1000 light-years
Temperature:      2457 °C
Orbit time:       22 days
Radius:           1639.999 × Earth
Mass:             57450 × Earth
Earth similarity: 0.03
--------------
Opponent card:
Name:             c_kepler_10_c
Distance:         605 light-years
Temperature:      311 °C
Orbit time:       453 days
Radius:           235.5 × Earth
Mass:             1140 × Earth
Earth similarity: 0.47
--------------
option 0: {}
Enter option: 
Game phase: evaluating
Player turn: player2
Your cards: 16
Opponent cards: 14
------------------------------------
Game phase: playing
Player turn: player2
Your cards: 16
Opponent cards: 14
------------------------------------
Your card:
Name:             c_mercury
Distance:         0.0000097 light-years
Temperature:      350 °C
Orbit time:       880 days
Radius:           38.3 × Earth
Mass:             5.5 × Earth
Earth similarity: 0.43
--------------
option 0: {"selected_category": Compound("category", [Integer(0), Atom("distance")])}
option 1: {"selected_category": Compound("category", [Integer(1), Atom("temp")])}
option 2: {"selected_category": Compound("category", [Integer(2), Atom("orbit_time")])}
option 3: {"selected_category": Compound("category", [Integer(3), Atom("radius")])}
option 4: {"selected_category": Compound("category", [Integer(4), Atom("mass")])}
option 5: {"selected_category": Compound("category", [Integer(5), Atom("earth_similarity")])}
Enter option: 

This has all been a lot of fun but there is one problem: it seems very slow. Ideally I would like to let the AI play against the AI and tell me things about the game, is it balanced, etc. Then maybe change the Prolog and try again. Right now AI vs AI it never finishes (it actually runs out of memory on my laptop after an hour or so).

Any ideas for making this system more efficient? Given I am pretty new to Prolog and Rust I am sure there are lots of targets for optimization but I am wondering about big targets and systemic inefficiency, maybe something more fundamental.

I did install and run cargo flamegraph, here's the output, but it hasn't helped me figure out how to best make this faster.

Anyway, all thoughts and suggestions are appreciated.

[hurufu]

Nice project, I also have used GDL to describe rules of a turn-based game in the past, but even state-of-the-art solvers couldn't deal with it in a timely manner. I haven't read your code yet, but the general suggestion is to reduce the search space by finding and eliminating symmetries.

[hurufu]

Also if I remember correctly, a GDL-1 way of introducing randomness is to add a third player (aka environment) with random AI.

[kasbah]

Thanks, the way I implemented randomness is also inspired by this GDL approach actually.

Do you have any more info on finding and eliminating symmetries? I can sort of imagine it but I am struggling to think how to implement it, especially in a general way (i.e. the rules of the game are allowed to change). Is there a name for it that I could try and find in a book or something?

It's possible that my inefficient AI really is the main problem, since, I forgot to mention, in addition to being a Rust and Prolog noob I am also inexperienced in implementing anything to do with machine learning. I assumed the overhead of querying Scryer is why the AI is slow but that may be a wrong assumption.

[bakaq]

I think Scryer (and/or your Prolog code) is indeed the problem here from the flamegraph. An absurd amount of time is spent in Term::from_heapcell, which is my fault since I implemented it in the dumbest way possible and didn't focus on performance at all (a lot of time is spent on cloning, and therefore allocating and deallocating, things for example). If this is indeed the problem, for now I guess you could try to minimize the number of calls to Scryer, make it so that your queries succeed fewer times, and make the terms that are generated by the query are smaller. It could be other things, I haven't looked at your code yet, but this is my first intuition from the flamegraph.

[kasbah]

This was my first intuition as well though I couldn't understand it from the flamegraph. There is something fundamental in the design, where I am inputting and outputting an assoc as the entire game state all the time, and even converting it to and from a BTree in Rust, which I may need to rethink. But there should be some opportunities for reducing the number of calls to Scryer as well, so thanks!

[jjtolton]

As a good Prolog developer, you are just supposed to write good code and trust that the implementation will get better. However, as a game developer... profiling is import and appropriate. You can do some basic but useful profiling with the time library. Sometimes you find things that are surprising. For instance, I found that charsio:char_type is very fast when working with instantiated variables but very slow when the modality of the ?char variable is in output mode.

:- use_module(library(time)).
:- use_module(library(lists)).
:- use_module(library(charsio)).

?- time(findall(D, member(D, "0123456789"), Ds)).
%@    % CPU time: 0.000s, 12 inferences
%@    Ds = "0123456789".

?- time(findall(D, char_type(D, decimal_digit), Ds)).
%@    % CPU time: 0.629s, 7_784_568 inferences
%@    Ds = "0123456789".

So I would start there to make sure that your predicates are meeting your expectations in terms of the number of inferences and time it takes.

If you want to get more sophisticated with it, you can use term_expansion/2 and goal_expansion/2 to build a profiling kit, possibly using managed predicates. I go into detail on how to use them here. (there's a lot of other stuff in there too about how it will be used in the game I'm working on, but it's not directly related to your question).

I intend to use Prolog heavily in a Unity game I'm working on and I'm sure that sort of profiling will be very prominent, and I will most likely end up building out a profiling kit as well!

[jjtolton]

FWIW -- at this point I would probably not use raw Scryer Prolog in the core game loop -- it would be rough, anyway. I plan to use it asyncronously for handling planning, but at 16ms per frame, even a few milliseconds of Prolog execution is more than I can afford. But it's great for executing complex planning tasks in the background.

[jjtolton]

Oh, by the way, I meant I would not use raw Scryer Prolog as the execution engine in the core game loop. I do intend on writing core game loop logic in Prolog. However, I intend to generate C# code using that specification.

[kasbah]

Thanks, I will take a look at profiling some of these rules.

That's interesting regarding not putting Scryer in the game loop. Before I was looking at Scryer I was actually taking a look at Differential Datalog which compiles a Datalog dialect to Rust that uses the differential_dataflow crate. Unfortunately it is not well maintained and I got a bit stuck with trying to use it.

What would be your strategy for code generation from the Prolog spec?

[jjtolton]

First of all, let me start off by saying I have not yet put this into practice, but here is my plan:

There are many ways to do it, but the code itself is by design trivially traversible via metainterpeters as long as you use valid Prolog syntax. Skipping to the end, C# has well defined source generation semantics.

Step 1: write a Prolog metainterpreter that can run the "Prolog pseudocode", even if it isn't particularly performant -- (although it can be amazingly performant, as a lot of @triska 's work has shown). (this applies even if you are using executable prolog rather than just prolog syntax).

(Note: I would probably use term expansion and goal expansion here so that I can switch out the behavior of the metainterpreter without changing the source code.)

Step 2: From here you will want to create an implementation of the interpreter that emits an intermediate representation as it traverses the source code. using the diag module is pretty good for inspiration.

Step 3: Decide if you want your target language to interpret those instructions directly, or if you want to compile them. If you go the compilation route, you can use DCGs very effectively to turn the IR into an AST, especially if the IR emitted is Prolog terms (but it can work well on strings too, you've just made some extra work for yourself). Optionally, you can make yet another Prolog interpreter to consume the IR for testing purposes.

There are some sections of the code, at least for me, that need to actually be executed in Scryer Prolog, particularly things that rely on clpz such as planning algos -- that's why we've been working hard on the embedded branch. This requires a lot of modular design, though, because you can't freely mix game logic with things that MUST BE Scryer (aka clpz). You would need a clean interface.

The way I see it -- the core strength of Prolog is not running a tight game loop, it's extensible source-to-source transformations. Nothing in the world even comes close to Prolog in expressive power there.

That being said, subsets of Prolog can be compiled to run on the GPU, so hopefully at some point more muscle-bound work can be given to Prolog.

[triska]

Happy New Year!

Thank you a lot for sharing your work, very interesting!

I noticed a few small things which I hope may help to improve the code, and eventually also its efficiency.

I start with a very small aspect, which is in itself not—or at most only very slightly—relevant for performance. However, it helps to reduce the amount of code and therefore may help indirectly to better grasp and implement more important issues that are otherwise overshadowed and less visible. This point is about making more, and more direct, use of unification. For instance, instead of:

get_assoc(game_phase, GameStateIn, GamePhase),
GamePhase = playing,

We can write:

get_assoc(game_phase, GameStateIn, playing),

We know that this usage mode is admissible from the signature of get_assoc/3, whereas its docstring is wrong (too specific).

Likewise, instead of:

\+ length(WinPile2, 0),

we can write:

WinPile2 = [_|_]

It's shorter and also more general, and on top likely also more efficient (which is not the main reason why we are doing this).

The same goes for:

length(WinPile2, WinPile2Length),
WinPile2Length #> 0,

which can also be directly expressed by reasoning about the shape of the term itself.

Another, more complex thing I noticed is:

\+ member(Card, Deck1),

This can be written more generally as:

maplist(dif(Card), Deck1)

We now have more freedom to move the goal around, and it also makes clear that we are reasoning here about a disequality. Seeing this, it may make sense to think about representing the problem in such a way that we can instead use CLP(ℤ) constraints, since domain information about integer variables can be very efficiently propagated. This would require representing the entities we want to reason about as integers, and a deck (maybe!) as the domain of an integer variable, expressing which cards can still be, or are, present in the deck.

Another thing that stands out are long sequences of goals that have a common shape, like:

maplist(any_card, VisibleDeck1),
maplist(any_card, VisibleDeck2),
maplist(any_card, VisibleWinPile1),
maplist(any_card, VisibleWinPile2),

It seems this can be expressed with a single goal such as (please verify!):

maplist(maplist(any_card), [VisibleDeck1,VisibleDeck2,VisibleWinPile1,VisibleWinPile2])

Another such occurrence of goals that have a lot in common is:

get_assoc(game_phase, GameStateIn, GamePhase),
get_assoc(deck1, GameStateIn, Deck1),
get_assoc(deck2, GameStateIn, Deck2),
get_assoc(win_pile1, GameStateIn, WinPile1),
get_assoc(win_pile2, GameStateIn, WinPile2),
get_assoc(cards_on_table, GameStateIn, CardsOnTable),
get_assoc(selected_category, GameStateIn, SelectedCategory),
get_assoc(player_turn, GameStateIn, PlayerTurn),

It seems such a sequence can be readily expressed with a lambda expression:

maplist(GameStateIn+\Key^Value^get_assoc(Key,GameStateIn,Value), [game_phase,deck1,deck2,...], [GamePhase,Deck1,Deck2,...]).

As mentioned, these changes are not expected to make a significant difference in performance by themselves. However, I hope they help to reduce the amount of code and make it easier to recognize more common patterns as candidates for further code reductions, and make it easier to change the remaining parts in order to improve performance. As soon as something seems tedious to write, we better stop and think about what we are doing: It may be a sign of redundancy in the code, and I suggest to look for ways to write it more compactly.

Avoiding deconstructing terms may actually improve performance by itself. For instance, the following stands out as unusual:

Player1Card =.. Player1CardDeconstructed,
Player2Card =.. Player2CardDeconstructed,

(=..)/2 may be useful in cases where we are reasoning about terms without knowing their functors and arities. But in the context of this application, it seems rather that we are supposed to know which terms we are reasoning about, and so such conversions can likely be avoided. If it is a matter of reasoning about a specific argument of a term, we can use the standard predicate arg/3 to efficiently access the argument. If the arity is meant to be flexible, then maybe using lists right away may be a better representation. Deconstructing a term like this takes time and space linear in the size of the term, and that additional space will only be reliably reclaimed by Scryer Prolog when the system provides garbage collection in the future.

I hope this helps, and if possible, please keep us posted!

[kasbah]

Thanks so much, I will try and improve these. As you said, I suspect this won't solve my performance problems but tips on my Prolog are always welcome.