Research Notes

Creativity - Flow and the Psychology of Discovery and Invention by Mihaly Csikszentmihalyi. (pg. 27-28)

1. The creative domain (table-top card games)
2. The field/gatekeepers that decide if the idea is creative/acceptabel (players or companies that fund/sell games)
3. The person who sees the new idea, and when it is selected for inclusion in the domain by the field (self-testing and creation by AI)

Computer Models of Creativity by Margaret A. Boden

• Psychological Creativity – novel to the one who created it, regardless of previous existence
• Historical Creativity – novel to the creator and having never been created previously
• Combinational Creativity – producing unfamiliar combinations of familiar ideas
• Exploratory Creativity – moving through the “conceptual space” of the domain to find what’s there, especially the unexplored parts, to find the potential and limits of the space
• Transformational Creativity – the space/style is transformed by altering/dropping one or more of its defining demensions

Under instruction on Dr. Ventura, further investigation into the meaning of creativity with computers has been suspended due to having little purpose concerning the project at hand.

Meeting (1/18/17):

• AAAI game description language for testing and playing. Agents out there that already know how to learn to play those games. Can use language to generate rules
• Possible genetic algorithm to generate the game. Fitness function that gives score based on testing to decide what phenotypes are better and are allowed to breed.

Beyond Computational Intelligence to Computational Creativity in Games Dan Ventura

• “Or consider card-based games such as Hearthstone and Lords of War. Because these games lack mechanics, it is perhaps even simpler to imagine abstracting the genre and building a system that creates new complete games. The challenge is the invention of diverse card packs and their coherent incorporation into a set of gameplay and ludic rules.”
• Game Development Language (GDL) for use in describing game rules/moves for use in AI player learning
• GDL-II for incomplete information: not every possible move is stated, but general rules of what is legal and what is not are given (more research needed)

Computational Game Creativity Antonios Liapis, Georgios N. Yannakakis and Julian Togelius

• Good games are non-trivial, but learnable (pg 4)

General Game Playing

• General Game Playing (GDP) is a field of AI research where AI systems are built to learn a game and then compete against other AI to see who wins.
• AAAI holds competitions where these AI are given a game to learn, then compete against each other to see who leaned the game better.
• The language format used for AI instruction is called Game Descriptive Language (GDL).
• To focus solely on the card game creating system, there is a possibility that the testing side of the system could incorporate the GDL learning AI.

General Game Playing: Game Description Language Specification Nathaniel Love et al.

• For use with games of “complete information”
• The Game Description Language is a variant of Datalog¬ that allows function constants, negation, and recursion.
• KIF is the official written language of GDL, datalog expressions written in KIF format
• In KIF, variables begin with a ?. All operators are written in prefix notation. Every term and every sentence is a Lisp S-expression. The arity and type (relation, function, object) of constants are determined by context.

Producing well formed games in GDL (from above specification document)

1. (Termination) A game description in GDL terminates if all infinite sequences of legal moves from the initial state of the game reach a terminal state after a finite number of steps.
2. (Playability) A game description in GDL is playable if and only if every role has at least one legal move in every non-terminal state reachable from the initial state.
3. (Monotonicity) A game description in GDL is monotonic if and only if every role has exactly one goal value in every state reachable from the initial state, and goal values never decrease.
4. (Winnability) A game description in GDL is strongly winnable if and only if, for some role, there is a sequence of individual moves of that role that leads to a terminal state of the game where that role’s goal value is maximal. A game description in GDL is weakly winnable if and only if, for every role, there is a sequence of joint moves of all roles that leads to a terminal state where that role’s goal value is maximal.
5. (Well-formed Games) A game description in GDL is well-formed if it terminates, is monotonic, and is both playable and weakly winnable.

There are definite limits to the GDL in that card games are not complete information games. At least, the majority of them are not. Research led to a version of GDL for incomplete/imperpect information as well as randomization elements, called GDL-II.

GDL-II and A General Game Description Language for Incomplete Information Games Michael Thielscher

• Only adds 2 new keywords: “random” and “sees”
• random is an additional role that performs tasks without the input of players, such as roll dice or draw cards.
• (sees r p) is a function that allows the role r to perceive action p.
• Combining these two additions, different players can only view/know what the game allows and are able perform randomized actions.

Found a GGP host and a GGP player called Sancho (GDL, not GDL-II), need to find a GDL-II player for testing…

Archive of games in GDL and GDL-II: http://ggpserver.general-game-playing.de/ggpserver/public/show_games.jsp?page=6

Explanation of GDL-II, including card game potential: http://logic.stanford.edu/ggp/chapters/chapter_17.html

Eclipse extension for use as a GDL IDE: http://palamedes-ide.sourceforge.net/index.html

GDL-II game controller with easy-to-use GUI: https://sourceforge.net/projects/ggpserver/files/

• The source was stated to be in this link, but only the executable JAR files are there. I have emailed the creator requesting the source code.
• I received a reply and now have the source code for the game controller!!

I am going to need a Unix environment in order to automate testing. The Game checker, the first line of fitness assessment that makes sure the program is syntactically correct and guarantees that the game is playable, only runs on Unix systems.

Created page for GDL-II syntax and examples: DESCRIPTION OF THE GDL-II LANGUAGE

Stanford Lecture explaining GGP and GDL: https://www.youtube.com/watch?v=WgdnjI4Tz-k

Syntax and Logic rules of GDL: https://www.youtube.com/watch?v=_f4b9ajYav8

In-depth explanation of Tic-Tac-Toe in GDL: https://www.youtube.com/watch?v=wxttnBPvH64

Found a plugin for eclipse that creats a KIF IDE for writing GDL programs. I was able to install it but was unable to figure out how to activate the plugin, get the syntax highlighting, and work with the syntax checker. After 2 hours of attempting, I am now using Atom to write the programs.

Began writing the War card game in GDL-II to get used to the syntax and learn how the individual pieces of a card game work in GDL-II. Notes and findings can be found on the DESCRIPTION OF THE GDL-II LANGUAGE page.

Major revelations are that individual rules come in chunks that can easily be generated given a pre-defined string with variable that can be filled in. Setting up the basic structure of the game is also as simple as determining how many players/decks/cards are needed and setting up the initial states for those.

If I wrote the genetic algorithm for creating the card game based on these pieces, than it would be more structured and easy to swap/modify genes to create new iterations.

I have been working on how these peices relate to each other, and using Lucidcharts, I have begun diagramming these relations. The natural tree structure creates the possibility of recursive rule creation that I will investigate on a later date.

Dr. Ventura advised that I look into a method of adding a “fun” factor to my fitness function. While “fun” is hard to categorize through the GDL game testing, there is a possibility. When generating the games, the rules and form of the game can be categorized. Given these features, it would not be impossible to train a machine learning AI that could determining the relative “fun factor” of the game. Building the data set would take a little work. I would need to randomly generate arrangements of the features and have people rate how fun they think a game would be if it had these features. The AI would then train on this data to be able to generalize how fun the games created by my genetic algorithm potentially are.

Using a machine learning algorithm is not too feasible because of the difficulty of obtaining data. For it to work, a LOT of data would need to be gathered from people. This is further complicated by the fact that it is hard for people to decide how fun a game is by its description alone.

Working on getting a lab computer set up. 2 possibilities, but are trying to contact former users to see if it is safe to wipe one of them.

Created Rule Descriptions page with formatted examples of how card rules could be represented in GDL-II for specific use in this system.

Added Players Section to Rule Descriptions:

• Number if Players
• Player Teams
• Team Membership Logic Checking
• Unique Player Classes
• Class Checking Logic

Added Decks Section to Rule Descriptions:

• Decks
• Max Size of Decks
• Current Deck Size
• Deck Checking Logic

Added Hands Section to Rule Descriptions:

• Hand Ownership
• Max Hand Size
• Current Hand Size
• Hand Check Logic

Continues creating arbitrarilly small games to test rule concepts.

Due to the inability of KIF to have mathematical expression, functions must be implemented to increment/decrement numbers, compare numeric values, and add.

Added Universal Inclusions Section to Rule Descriptions:

• Inrementors and Decrementors
• Greater than or Less than
• Adding

Created new testing games:

• move_state - to check the “Next”, “Terminate”, and “Goal” functions in GDL
• incrememntor - a little more complicated, testing persistent states and the incrementor function mentioned above
• greaterthan_lessthan - the most complicated game so far to test the functionality of the greater than or less than function mentioned above, also tests hands and picking a card from a hand.

Added to Hands Section in Rule Descriptions:

• Hand Persistence

Created new testing game:

• Teams - tests the team functionality and specific ability cards, most complex game so far

Spent time working on finding ways to generalize the creation of the Next functions for state change/persistence and still can't figure out a good way to do it. Next states very specific in what they need to check for and how they need to set. If there are multiple different rules that effect the same state, all combinations of each rule need to be considered in separate Next functions.

For example:

If you have a stat, and 2 different card abilities alter that stat:

• For simultaneous play there needs a different next for the first ability, second ability, and the two at the same time.
• For turn-based play, you need one for each ability.

All the below next functions are for a single stat

(<= (next (status ?player ?stat)) ;no actions against stat, required or else the stat disappears!
(true (status ?player ?stat))
(not (true (choice ?actor defend ?player)))
(not (true (choice ?actor attack ?player)))
(not (true (choice ?actor heal ?player)))
(true (control between)))

(<= (next (status ?player ?status)) ;during decision round, keep statuses
(true (status ?player ?status))
(true (control players)))

(<= (next (status ?player alive)) ;healed
(true (choice ?actor heal ?player))
(true (control between)))

(<= (next (status ?player dead)) ;attacked and not defended
(true (choice ?attacker attack ?player))
(not (true (choice ?defender defend ?player)))
(true (control between)))

(<= (next (status ?player alive)) ;defended
(true (choice ?defender defend ?player))
(true (control between)))

Continued working on next and state persistence. No major headway. Have a migraine, so little work could be done.

Continued working on state persistence with the next function. Focused solely on movement of cards from decks to player hands to discard piles. The major issue was keeping the modification of variables persistent so that cards do not disappear or duplicate. This also includes the changing of variables for deck and hand size to make sure that they do not duplicate or disappear.

Each move an actor can make modifies one of the variables in the game. Sometimes actions on these variable cross. For example:

Deal - Actors: random, player - Altered Values: deck, decksize, hand, handsize Discard - Actors: player - Altered Values: deck, decksize, hand, handsize

The altered values here are duplicates, but some can be ignored. The deck in the “Deal” case is the draw deck whereas the “Discard” case's deck is the discard pile, so there is no cross involved there. However, the cards in the player's hand and the hand size are directly affected by both dealing and discarding. Dealing adds cards to the hand and increases the hand size. Discarding does the exact opposite.

From my former look into this, every combination of these moves would have to be considered for each. For example:

• no deal or discard
• deal, no discard
• no deal, discard
• deal and discard

The relation is a n^2 relation with n being the number of factors that affect the variable. If there were 3 total moves that affected cards in hand, then there would be 9 combinations. With four, 16! This is HIGHLY infeasible

The goal is to find some way to make these separate, to isolate one affect on the hand from another. Through experimentation, I have created an arbitrarily simple game that accomplishes this!

__The Game__ The base game is simply draw-then-discard. The first iteration of the game had 5 cards in the deck. The random player would draw 1 for the player, and the player would discard a card if he had one in his hand.

I started writing it with the restriction that any modification to a variable can only have one actor modifying it, a.k.a. a single next changing the hand size could only have a check for drawing OR for discarding. There would need to be separate next statements for each check. There would This would make the relation n instead of n^2, and much easier to generate.

Problems: When the computer drew a card and a player discarded, the value for hand size would duplicate. The card discarded would still be in hand because the next for cards in hand that has a check for added card drawn creates a state where all cards that were in the hand are still in the hand + the new card. This could easily be fixed by adding a check to see if the card was discarded in the next for draw, but that goes against the restrictions I set.

Changes: Prevent simultaneous actions. I made it so that instead of simultaneous drawing and discarding, the random would draw one turn, then the player would discard the next. This fixed the duplication of cards.

Problems: The new changes made the hand size variable disappear between turns instead of duplicate. I attempted an asymmetric fix, where draw's next would do all general check for drawing or no action modified the variable, and discard's next would just check for if a discard happened. This made it so that it would not disappear on draw turns, but it would still disappear on discard turns. I then added the check for no action in discard as well. This returned to the problems from simultaneous play with duplication of the value.

Changes: Place turn checks in on each next. Because draw and discard are both turn specific, this fixed again the duplication of values. Drawing and discarding are now completely separate! The question no becomes, how extendable is it?

Problems: Due to the turn check being specifically for when it is the random's turn for drawing or the player's turn for discarding, when another player with their own turn is added, values disappear because there is no check for when it's the other player's turn.

Changes: Separate from any modifier for a variable, include a next that states the value stays the same when it is not the player's or random's turn. But how versatile is this? I added a new move called “take” where a player can take a card from another.

Problems: The “take” move is able to be separated from all other moves except in one instance: the case where neither a card has been taken nor discarded from a hand. The cards themselves are not affected by this, but the handsize is. This cannot be separated into two next functions, one checking if no card has been discarded and the other checking to make sure no card has been taken by another player. If they are separated, at least one will be true, so the other will preserve the handsize while the other will decrease it by one creating duplicate handsize variables, one with the correct value and the other with the old.

Unlike the other issues, there is no fix for this one that I can see. Doing logical proofs, the only way to make the correct handsize carry on is to have the function that carries both checks. This breaks my original assumption that all functions can be completely separated. This does not mean that generation of functions is going to be n^2 complexity.

Notes on this can be found in Persistence of Sates