Saturday, May 13, 2017

Expression evaluation on object based models


Let's look at how to mix object based models with logical expression evaluation.
Other articles in the AI Knowledge Based Reasoning series on this site:
Knowledge based reasoning in .net c#
Reasoning in Open or Closed models
Logic Expression evaluation with open-world assumption
Expression evaluation on object based models

Many systems work on an object model of some kind, to be able to integrate logical expression evaluation to an existing system you need some way to translate from that object model to a knowledge model. This is one way to do it, there are probably better ways out there. But this works for me : )

To be able to evaluate logical expressions on an object model, you first have to translate the object model into a Knowledge model. The idea here is to scope the amount of knowledge to a certain object (or objects), lets call that scope a Context, in the case of objects lets call it an ObjectContext.
public class Context
{
 public Guid Id { get; }
 public string Name { get; }
   
 public KnowledgeStore KnowledgeStore { get; }

 public Context(string name)
 {
  Id = Guid.NewGuid();
  Name = name;
  KnowledgeStore = new KnowledgeStore(this);
 }

 public EvaluationResult Evaluate(AExpression expression)
 {
  var facts = new Dictionary<ExpressionLeaf, EvaluationResult>();
  var leafNodes = expression.GetLeafNodes();
  foreach (var node in leafNodes)
  {
   var leaf = node.Leaf;
   if(leaf is KnowledgeNon)
    continue;
   var attr = leaf as KnowledgeAttribute;
   if (attr != null)
   {
    facts.Add(node, KnowledgeStore.Evaluate(attr));
   }
   var rel = leaf as KnowledgeRelation;
   if (rel != null)
   {
    facts.Add(node, KnowledgeStore.Evaluate(rel));
   }
  }
  if (facts.Values.Any(x => x == EvaluationResult.NotSure))
   return EvaluationResult.NotSure;
  return expression.TransformEvaluation(facts);
 }
}
So, the base Context object lets us Evaluate an Expression, as we assume an open world we also allow for the response NotSure.

And for the ObjectContext, we will use reflection to create the Knowledge from the objects that we throw at it.In my case, my model inherits from a BaseObject class, but it could be any object.
public class ObjectContext : Context
{
 public BaseObject Root { get; set; }
 public ObjectContext(BaseObject root) : base(root.ToString())
 {
  Root = root;
  KnowledgeStore.AddAttribute(new KnowledgeAttribute
  {
   Attribute = root.GetType().Name,
   Subject = Name
  }, Name);
  var fields = GetAllProperties(root);
  foreach (var field in fields)
  {
   KnowledgeStore.AddRelation(new KnowledgeRelation
   {
    Subject = field.Value,
    Relation = $"{field.Key}Of",
    Target = Name
   }, Name);
  }
 }

 private Dictionary<string, string> GetAllProperties(object obj)
 {
  var d = new Dictionary<string, string>();
  var properties = obj.GetType().GetProperties();
  foreach (var prop in properties)
  {
   var val = prop.GetValue(obj);
   if (val == null)
    val = string.Empty;
   d.Add(prop.Name, val.ToString());
  }
  return d;
 }
}

So basically we will take a snapshot of the model and allow for expression evaluation on that snapshot. If the underlying model changes, the context object would need to be recreated.
As you can see we add a suffix to each attribute name, so if the object has a field called Name, the knowledge attribute would be NameOf.

Lets look at some unit tests to see how this works.
[TestClass]
public class ObjectContextTest
{
 [TestMethod]
 public void ContextTest_Evaluate_Not_False()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionNot(new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() });
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.False, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_Not_True()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionNot(new KnowledgeRelation { Relation = "NameOf", Subject = "T", Target = obj.ToString() });
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.True, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_And_BothTrue()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionAnd(
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() },
   new KnowledgeRelation { Relation = "NameOf", Subject = "Charlize", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.True, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_And_RightFalse()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionAnd(
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() },
   new KnowledgeRelation { Relation = "NameOf", Subject = "T", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.False, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_And_LeftFalse()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionAnd(
   new KnowledgeRelation { Relation = "NameOf", Subject = "T", Target = obj.ToString() },
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.False, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_And_BothFalse()
 {
  var obj = new Person("Charlize") { Gender = Person.GenderType.Female };
  var target = new ObjectContext(obj);
  var expr = new ExpressionAnd(
   new KnowledgeRelation { Relation = "NameOf", Subject = "T", Target = obj.ToString() },
   new KnowledgeRelation { Relation = "GenderOf", Subject = "male", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.False, actual);
 }
 [TestMethod]
 public void ContextTest_Evaluate_Or_BothTrue()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionOr(
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() },
   new KnowledgeRelation { Relation = "NameOf", Subject = "Kate", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.True, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_Or_RightFalse()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionOr(
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() },
   new KnowledgeRelation { Relation = "NameOf", Subject = "Kate", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.True, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_Or_LeftFalse()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionOr(
   new KnowledgeRelation { Relation = "NameOf", Subject = "Kate", Target = obj.ToString() },
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.True, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_Or_BothFalse()
 {
  var obj = new Person("Charlize") { Gender = Person.GenderType.Female };
  var target = new ObjectContext(obj);
  var expr = new ExpressionOr(
   new KnowledgeRelation { Relation = "NameOf", Subject = "Kate", Target = obj.ToString() },
   new KnowledgeRelation { Relation = "GenderOf", Subject = "Male", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.False, actual);
 }


 [TestMethod]
 public void ContextTest_Evaluate_Xor_BothTrue()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionXor(
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() },
   new KnowledgeRelation { Relation = "NameOf", Subject = "Charlize", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.False, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_Xor_RightFalse()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionXor(
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() },
   new KnowledgeRelation { Relation = "NameOf", Subject = "Kate", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.True, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_Xor_LeftFalse()
 {
  var obj = new Person("Charlize");
  var target = new ObjectContext(obj);
  var expr = new ExpressionXor(
   new KnowledgeRelation { Relation = "NameOf", Subject = "Kate", Target = obj.ToString() },
   new KnowledgeAttribute { Attribute = "Person", Subject = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.True, actual);
 }

 [TestMethod]
 public void ContextTest_Evaluate_Xor_BothFalse()
 {
  var obj = new Person("Charlize") { Gender = Person.GenderType.Female };
  var target = new ObjectContext(obj);
  var expr = new ExpressionXor(
   new KnowledgeRelation { Relation = "NameOf", Subject = "T", Target = obj.ToString() },
   new KnowledgeRelation { Relation = "GenderOf", Subject = "female", Target = obj.ToString() }
   );
  var actual = target.Evaluate(expr);
  Assert.AreEqual(EvaluationResult.False, actual);
 }
}

So, just some thoughts on how to do this. This is far from completed and is still a work in progress used by one of my home projects. Any comments are appreciated.
If you wonder why this is not on my github repository, I feel that it doesn't really have that kind of quality yet. But with time it will get there.

All code provided as-is. This is copied from my own code-base, May need some additional programming to work.


Sunday, April 9, 2017

DIY Game Financial System Part 2: Trade Algorithm


This is part of my series on DIY Game Financial System
For other posts in this series check out the following links:
DIY Game Financial System Part 1: Intro and Accounts
DIY Game Financial System Part 2: Trade Algorithm

For the full source code for the financial system discussed in this series, look in the repository.
This post we will look at the actual trade algorithm used. It is a quite naive implementation but works for me. Feel free to extend it for your own needs.

In the Marketplace class, we have an Update method that iterates through all the buy and sell orders available and tries to match them with each other. This simple implementation tries to find an exact match but there is potential to extend it to match multiple sell to one buy, or one sell to multiple sell.
In the demo application this is triggered by a timer.

public void Update()
{
 bool updated = false;
 lock(_sellOrders)
 {
  lock (_buyOrders)
  {
   foreach (var buyName in _buyOrders)
   {
    List<SellOrder> sellOrders;
    if (!_sellOrders.TryGetValue(buyName.Key, out sellOrders))
     continue;
    // naive
    foreach (var buyOrder in buyName.Value)
    {
     foreach (var sellOrder in sellOrders)
     {
      if (buyOrder.Quantity == sellOrder.Quantity
       && buyOrder.PricePerItem == sellOrder.PricePerItem)
      {
       updated = true;
       buyOrder.Execute(sellOrder);
      }
     }
    }
   }
   foreach (var order in _sellOrdersToBeRemoved)
   {
    _sellOrders[order.SecurityName].Remove(order);
   }
   foreach (var order in _buyOrdersToBeRemoved)
   {
    _buyOrders[order.SecurityName].Remove(order);
   }

  }
 }
 if (updated)
 {
  Updated?.Invoke(this, this);
 }
}

The key lines above are the
if (buyOrder.Quantity == sellOrder.Quantity
 && buyOrder.PricePerItem == sellOrder.PricePerItem)
{
 updated = true;
 buyOrder.Execute(sellOrder);
}
This tries to exactly match each buy with a sell and then trigger the Execute method:
public void Execute(SellOrder sellOrder)
{
    OrderAccount.DepositInto(sellOrder.OrderAccount, sellOrder.Quantity * sellOrder.PricePerItem);
    Security = sellOrder.ForSale;
    foreach (var action in _executeActions)
    {
        action(this);
    }
    sellOrder.Execute();
}
This is where the money is transferred between the two orders, all actions connected to this BuyOrder are triggered and then finally the sellOrder is executed as well.

When the buy order was added to the Marketplace, it associated a Cancel and Execute action with it to be triggered when the order was successful or canceled.
public void Buy(BuyOrder order)
{
 lock (_buyOrders)
 {
  if (_buyOrders.ContainsKey(order.SecurityName))
   _buyOrders[order.SecurityName].Add(order);
  else
   _buyOrders.Add(order.SecurityName, new List<BuyOrder> { order });
  order.AddCancelAction(RemoveBuy);
  order.AddExecuteAction(RemoveBuy);
 }
}
For both cases, we are just interested in removing the order from the list of available orders. The same goes for the Sell method.
private void RemoveBuy(BuyOrder order)
{
 _buyOrdersToBeRemoved.Add(order);
}
As this is triggered from an iteration of the _buyOrders collection, we need to deffer the removal to after the iteration has completed, hence the addition to a secondary removal list.
Just writing this I spotted a bug in the code where the order needs to be flagged as executed so that the same order isn't executed multiple times. I will not fix this in the demo application for now. 


Last in the Update method, a call to the Updated event handlers associated with this marketplace object.
if (updated)
{
 Updated?.Invoke(this, this);
}
This way a GUI can update itself if there was an update. The Updated event is also fired each time an order is added to the marketplace.

So there, thank you for reading. Hope this helps someone out there : )

Until next time: Work to Live, Don’t Live to Work

Friday, March 10, 2017

DIY Game Financial System Part 1: Intro and Accounts

picture of commerce on river banks in the evening

I'm quite interested in finance as can be seen on my other blog dreamstateliving, and thus I decided to start working on a small but powerful in game financial system that can be used in my future games.
The goal for this system is to allow for
  • trading at a marketplace, much like the stock market
  • buying and selling stuff from vendors
Note that the code provided with this post is intended to be used in games, a lot of shortcuts have been taken. This is not a fool-proof system, more like a base to start building your own in game financial system on.

In this part we will introduce the scenario and go through the Account and TradeAccount classes.

This is part of my series on DIY Game Financial System
For other posts in this series check out the following links:
DIY Game Financial System Part 1: Intro and Accounts
DIY Game Financial System Part 2: Trade Algorithm

Introduction, a textual description

Every player, vendor etc. has their private TradeAccount consisting of a BalanceAccount and a list of Securities (items, shares whatever) owned at his current state.
Each TradeAccount is able to generate a BuyOrder based on a name of the Security to buy, the Quantity of Securities we are shopping for and the PricePerItem we are willing to pay. The BuyOrder  also contains a BalanceAccount with the amount of money needed to make the purchase. It is not possible to generate a BuyOrder if the TradeAccounts' BalanceAccount does not hold the amount of money needed to close the transaction.
In a similar fashion, each TradeAccount is able to generate a SellOrder for Securities currently held by that TradeAccount. The SellOrder also consists of the PricePerItem, Quantity and the Security for sale.

Both the SellOrder and the BuyOrder are sent to the Marketplace where the trade should be made. The Marketplace should be possible to instance as many times as needed. For example each vendor would have their own with things for sale, but the global Marketplace would allow for players to trade.

If there is an exact match on Security, Quantity and PricePerItem we will Execute the BuyOrder and transfer the money to the sellers TradeAccount and the securities to the buyers TradeAccount.
This will be our first naive algorithm to match orders.

Lets look at some code.


BalanceAccount

This is just a holder of money. Lets look at the interface.
public interface IAccount
{
    Guid Id { get; }
    ulong Balance { get; }
    bool CanAfford(ulong x);
    bool DepositInto(IAccount dest, ulong amount);
    void AddBalance(ulong amount);
}
So first we have an identifier, Id, just so that we can identify this account uniquely. Then we will store the actual current Balance of the account. I chose an unsigned long to store because of three reasons:

  • I don't really want to handle negative numbers, i.e. if you cannot afford it you can't buy it.
  • to be able to handle very large sums, I don't really know the applications for this yet, but don't want to limit someone for buying something for a ridiculous amount of money (18,446,744,073,709,551,615 to be exact)
  • I don't want to handle decimal numbers. Keep it simple, its a game :)
After that we have some functions, CanAfford checks if the account could afford to buy something costing x. 
public bool CanAfford(ulong x)
{
    return Balance >= x;
}
DepositInto withdraws money from this account and inserts it into the destination account.
public bool DepositInto(IAccount dest, ulong amount)
{
    lock (this)
    {
        if (!CanAfford(amount))
            return false;
        SubtractBalance(amount);
    }
    lock (dest)
    {
        dest.AddBalance(amount);
    }
    return true;
}
And lastly AddBalance creates money out of the blue (or you handle it somewhere else) and inserts into this account.
public void AddBalance(ulong amount)
{
    lock (this)
    {
        Balance += amount;
    }
}
private void SubtractBalance(ulong amount)
{
    Balance -= amount;
}
As you can see we add an extra lock in the AddBalance function as it is a public one and could be called from outside the DepositInto lock. For the private SubtractBalance method, we have full control and don't need the additional lock overhead.
There is a number of unit tests to verify this implementation in the source code in the repository. It gets quite long and thus not included in the post.

TradeAccount

public interface ITradeAccount
{
    event EventHandler<TradeAccount> Updated;
    IAccount BalanceAccount { get; }
    ulong ValueOfActiveBuyOrders { get; }
    Dictionary<string, Security> Securities { get; }
    List<BuyOrder> BuyOrders { get; }
    List<SellOrder> SellOrders { get; }

    SellOrder CreateSellOrder(string name, ulong quantity, ulong pricePerItem);
    BuyOrder CreateBuyOrder(string name, ulong quantity, ulong pricePerItem);
}

First off, we will expose an event, Updated, that will be triggered whenever the contents of this Trade Account change. This to be able to create event based updates of GUI elements at a later stage.
After that we have the BalanceAccount associated with this TradeAccount, for storage of money that can be used to buy stuff.
ValueOfActiveBuyOrders will return the amount of money bound in buy orders created by this TradeAccount.
public ulong ValueOfActiveBuyOrders
{
    get
    {
        ulong sum = 0;
        foreach (var item in BuyOrders)
        {
            sum += item.OrderAccount.Balance;
        }
        return sum;
    }
}
Securities is a dictionary of securities held by this account followed bu the currently active BuyOrders and SellOrders.

Lastly we expose functions to create both Sell and Buy orders.

CreateSellOrder

public SellOrder CreateSellOrder(string name, ulong quantity, ulong pricePerItem)
{
    Security security; 
    if (!Securities.TryGetValue(name, out security))
        return null;
    var split = security.Split(quantity);
    if (split == null)
        return null;
    var order = new SellOrder(split, pricePerItem);
    order.AddCancelAction(CancelSellOrder);
    order.AddExecuteAction(ExecuteSellOrder);
    lock (SellOrders)
    {
        SellOrders.Add(order);
    }
    Updated?.Invoke(this, this);
    return order;
}
To createa a SellOrder we first need to check if we actually own any securities with the name provided, if we don't we will stop directly. After that we split our owned security into a new one with the quantity we want to sell. We expect the Split method to return null if the split is invalid (tries to sell more then owned) and we stop there as well. If all is well, we setup the SellOrder, connect both Cancel and Execute handlers to this TradeAccount so that it will know its way home when the mission is accomplished or canceled. Lastly, we add it to the list of active SellOrders and invoke the Updated event.
private void ExecuteSellOrder(SellOrder order)
{
    order.OrderAccount.DepositInto(BalanceAccount, order.OrderAccount.Balance);
    lock (SellOrders)
    {
        SellOrders.Remove(order);
    }
    Updated?.Invoke(this, this);
}
The ExecuteSellOrder is responsible to transfer money to the selling TradeAccount when a trade is completing. As seen, the SellOrder has already received the money from the buying account so this is just a final put the money where it belongs and cleanup things handler.
private void CancelSellOrder(SellOrder order)
{
    Security security;
    if (!Securities.TryGetValue(order.SecurityName, out security))
    {
        Securities.Add(order.SecurityName, order.ForSale);
    }
    else
    {
        Securities[order.SecurityName].Merge(order.ForSale);
    }
    lock (SellOrders)
    {
        SellOrders.Remove(order);
    }
    Updated?.Invoke(this, this);
}
The CancelSellOrder is a little more complicated. We are not receiving any money here but we need to put the Securities back where they belong. So find the security we were trying to sell and either merge with the existing one or create a new entry (if it has been cleaned up for any reason). After that some cleanup and update event invoking.

CreateBuyOrder

The CreateBuyOrder basically follows the same pattern as the sell order creator but here we check that we have enough money to make the purchase that we want to.
We do this by creating a new account and trying to deposit the needed amount of money into it. If it fails, we stop there. If all is good, we create the BuyOrder and supply it the just created account and what to look for in the marketplace. Just as for the SellOrder, we connect handlers for both the Execute and Cancel outcomes and add it to the list of active buy orders.
public BuyOrder CreateBuyOrder(string name, ulong quantity, ulong pricePerItem)
{
    var orderAccount = new Account(0);
    if (!BalanceAccount.DepositInto(orderAccount, quantity*pricePerItem))
        return null;
    var order = new BuyOrder(name, pricePerItem, quantity, orderAccount);
    order.AddCancelAction(CancelBuyOrder);
    order.AddExecuteAction(ExecuteBuyOrder);
    lock (BuyOrders)
    {
        BuyOrders.Add(order);
    }
    Updated?.Invoke(this, this);
    return order;
}
The ExecuteBuyOrder looks very similar to the CancelSellOrder above, instead of putting back a canceled sell order, we will put in a newly purchased Security. It needs to find the already owned security and merge with it if it exists or create a new entry in the owned Securites dictionary. After that a cleanup is done.
private void ExecuteBuyOrder(BuyOrder order)
{
    Security security;
    if (!Securities.TryGetValue(order.SecurityName, out security))
    {
        Securities.Add(order.SecurityName, order.Security);
    }
    else
    {
        Securities[order.SecurityName].Merge(order.Security);
    }
    lock (BuyOrders)
    {
        BuyOrders.Remove(order);
    }
    Updated?.Invoke(this, this);
}
And surprise, surprise the CancelBuyOrder is similar to the ExecuteSellOrder. Here we put back the pocket-money we received when going to the market and then cleaning up.
private void CancelBuyOrder(BuyOrder order)
{
    order.OrderAccount.DepositInto(BalanceAccount, order.OrderAccount.Balance);
    lock (BuyOrders)
    {
        BuyOrders.Remove(order);
    }
    Updated?.Invoke(this, this);
}

So just like with the Account, there are a number of unit tests in the repository  that I will not cover here. Actually the repository contains the code for the first working version with a test GUI. We will cover the rest of the code in future posts in this series, but if you are interested you can look at the code already now :)

So there, thank you for reading. Hope this helps someone out there : )

Until next time: Work to Live, Don’t Live to Work