Monday, July 3, 2017

Expression evaluation over time

We have looked at different aspects of knowledge representation during this series and this time its time to look at time itself. How to model logic expressions that incorporate time? I.e. how to store knowledge and query it with time based queries?

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
Expression evaluation over time

Introduction

To be able to model logic expressions that incorporate time we first have to ask ourselves, what do we mean by time? Is it abstract ideas like before, after, now and then? Or is it exact number of ticks since we began to measure? Or is it a combination of both?

This part will be quite heavy on ideas rather then code..

Discrete Time

Lets first look at some definitions of discrete time.
Discrete time views values of variables as occurring at distinct, separate "points in time", or equivalently as being unchanged throughout each non-zero region of time ("time period")—that is, time is viewed as a discrete variable -wikipedia
So basically what we say is that even though time is continuous, we will look at it in a discrete way just to simplify our models.

Events

Lets say that we receive knowledge in the form of events, all data recorded in the event will be added to our Context as one frame. For example:
Time Frame Name Occupation Eye-color Hair-color
1 Kate Student Blue Brown
2 Kate Pearlescent
3 Kate Pink
4 Kate Student Blue
5 Kate Intern Blonde
6 Kate
Pearlescent
7 Kate Lawyer Brown
Time frame can be incremental number if we don't care about actual time passed or a time stamp of when the even occurred.
So lets store all our data in this form.

Full frame from incomplete frames

How to query something like the above example?
One idea is to see each event as its own frame of context. I.e. all expressions written in previous posts would now be transferred to refer only to one frame at a time. But that would be kind of incomplete as all events do not record data on all possible parameters. One way to work around this would be to always start from the latest frame and search backwards in the frame-stack until that parameter gets hit. For example in the example above, a full 'latest' frame of information would be the blue highlighted information as seen in the following table:
Time Frame Name Occupation Eye-color Hair-color
4 Kate Student Blue
5 Kate Intern Blonde
6 Kate
Pearlescent
7 Kate Lawyer Brown

Occupation(Lawyer) AND Eye-color(Blue) AND Hair-color(Brown)
Would return True

Occupation(Intern) AND Eye-color(Blue) AND Hair-color(Brown)
Would evaluate to False, as it is not the last full aggregate frame. See Occupation column has newer entries then Intern.

Occupation(Lawyer) AND Eye-color(Blue) AND Drives(Volvo XC90)
Would evaluate to Not Sure as there is no event recording any knowledge about what car Kate drives.

Lets look at some C# code to do just that. Lets convert our Evaluate method in the Context class to the following instead:
public EvaluationResult Evaluate(AExpression expression, int frameStart = -1)
{
    if (frameStart == -1)
        frameStart = _frames.Count - 1;
    var facts = new Dictionary<ExpressionLeaf, EvaluationResult>();
    var leafNodes = expression.GetLeafNodes();
    foreach (var node in leafNodes)
    {
        var leaf = node.Leaf;
        var attr = leaf as KnowledgeAttribute;
        var rel = leaf as KnowledgeRelation;
        if (!(attr != null | rel != null))
            continue;
        for (int i = frameStart; i >= 0; i--)
        {
            var frame = _frames[i];
            var result = attr != null ? frame.Evaluate(attr) : frame.Evaluate(rel);

            if (result == EvaluationResult.NotSure)
                continue;
            facts.Add(node, result);
            break;
        }
    }
    if (!facts.Any())
        return EvaluationResult.NotSure;
    if (facts.Values.Any(x => x == EvaluationResult.NotSure))
        return EvaluationResult.NotSure;
    return expression.TransformEvaluation(facts);
}
And the frame/event store looks something like this (still in the Context class):
private readonly List<KnowledgeStore> _frames;
public IReadOnlyCollection<KnowledgeStore> Frames => new ReadOnlyCollection<KnowledgeStore>(_frames);
public KnowledgeStore CurrentFrame => _frames.Last();
public void AddFrame(KnowledgeStore frame)
{
    _frames.Add(frame);
}

Relative queries

So now we have covered how to determine the current state from this event based knowledge store. Next step is to start determining how knowledge relates to each other based on relative time queries.

For this we will need to add an Evaluate method in the Context class for just relative queries:
public EvaluationResult Evaluate(IRelative expression)
{
    return expression.Evaluate(this);
}

All keyword

Time Frame Name Occupation Eye-color Hair-color
1 Kate Student Blue Brown
2 Kate Pearlescent
3 Kate Pink
4 Kate Student Blue
5 Kate Intern Blonde
6 Kate
Pearlescent
7 Kate Lawyer Brown
This one is pretty simple, it just states that All knowledge frames in the store should evaluate the expression to true.
I.e. ALL Name(Kate) AND Eye-color(Blue)
would be True.
But ALL Occupation(Lawyer) would evaluate to False as there exists frames where this statement is false.
And as before, including a fact from a column that has no recorded data in the query would result in Not Sure.

public class RelativeAll : IRelative
{
    private readonly AExpression _expression;

    public RelativeAll(AExpression expression)
    {
        _expression = expression;
    }

    public EvaluationResult Evaluate(Context context)
    {
        var result = EvaluationResult.NotSure;
        for (int frameIndex = context.Frames.Count - 1; frameIndex >= 0; frameIndex--)
        {
            result = context.Evaluate(_expression, frameIndex);
            if(result == EvaluationResult.False)
                return EvaluationResult.False;
        }
        return result;
    }
}

Some unit tests to see how it behaves:
[TestMethod]
public void RelativeAllTest_AddFrame_CurrentUpdated()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var actual = target.Evaluate(expr);
    Assert.AreEqual(EvaluationResult.True, actual);
}

[TestMethod]
public void RelativeAllTest_All_True()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation
    {
        Subject = "Alice",
        Relation = "Name of",
        Target = obj.ToString()
    });
    var rel = new RelativeAll(expr);
    var actual = target.Evaluate(rel);
    Assert.AreEqual(EvaluationResult.True, actual);
}

[TestMethod]
public void RelativeAllTest_All_False()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation
    {
        Subject = "Lawyer",
        Relation = "Occupation of",
        Target = obj.ToString()
    });
    var rel = new RelativeAll(expr);
    var actual = target.Evaluate(rel);
    Assert.AreEqual(EvaluationResult.False, actual);
}

[TestMethod]
public void RelativeAllTest_All_NotSure()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr = new ExpressionIs(new KnowledgeRelation
    {
        Subject = "Undercut",
        Relation = "Hair style of",
        Target = obj.ToString()
    });
    var rel = new RelativeAll(expr);
    var actual = target.Evaluate(rel);
    Assert.AreEqual(EvaluationResult.NotSure, actual);
}

private static Person CreateTarget(out Context target)
{
    var obj = new Person("Alice");
    obj.Occupation = "Student";
    target = new Context(obj.ToString());
    target.AddFrame(FrameFactory.Create(obj));
    obj.Occupation = "Lawyer";
    target.AddFrame(FrameFactory.Create(obj));
    return obj;
}

Before keyword

Time Frame Name Occupation Eye-color Hair-color
4 Kate Student Blue
5 Kate Intern Blonde
6 Kate
Pearlescent
7 Kate Lawyer Brown

Syntax: Expression1 Before Expression2
A little harder, trying to determine if Expression1 evaluates true in a full frame before Expression2 evaluates true.
For example:
(Name(Kate) AND Occupation(Intern) AND Hair-color(Blonde)) Before (Name(Kate) AND Occupation(Intern) AND Hair-color(Pearlescent))
Would evaluate to True.

(Name(Kate) AND Occupation(Intern) AND Hair-color(Pearlescent)) Before (Name(Kate) AND Occupation(Intern) AND Hair-color(Blonde))
Would evaluate to False.

And as before, including a fact from a column that has no recorded data in the query would result in Not Sure.

Tricky one is if only one of the expressions evaluate but the other comes back Not Sure, I think for sake of consistency we should evaluate that as Not Sure also.
public class RelativeBefore : IRelative
{
    private readonly AExpression _left;
    private readonly AExpression _right;

    public RelativeBefore(AExpression left, AExpression right)
    {
        _left = left;
        _right = right;
    }

    public EvaluationResult Evaluate(Context context)
    {
        int rightFrameIndex;
        var rightResult = EvaluateExpression(context, _right, out rightFrameIndex);
        int leftFrameIndex;
        var leftResult = EvaluateExpression(context, _left, out leftFrameIndex);

        if (leftResult == EvaluationResult.NotSure || rightResult == EvaluationResult.NotSure)
            return EvaluationResult.NotSure;

        if (leftResult == EvaluationResult.True && rightResult == EvaluationResult.True)
        {
            return leftFrameIndex < rightFrameIndex ? EvaluationResult.True : EvaluationResult.False;
        }
        return EvaluationResult.False;
    }

    private EvaluationResult EvaluateExpression(Context context, AExpression expression, out int frameIndex)
    {
        var result = EvaluationResult.NotSure;
        for (frameIndex = context.Frames.Count - 1; frameIndex >= 0; frameIndex--)
        {
            result = context.Evaluate(expression, frameIndex);
            if (result == EvaluationResult.True)
            {
                return EvaluationResult.True;
            }
        }
        return result;
    }
}

Some tests to clarify things:
[TestMethod]
public void RelativeBeforeTest_True()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Student", Relation = "Occupation of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr1, expr2);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.True, actual);
}
[TestMethod]
public void RelativeBeforeTest_False()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Student", Relation = "Occupation of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr2, expr1);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.False, actual);
}
[TestMethod]
public void RelativeBeforeTest_LeftNotSure_NotSure()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Undercut", Relation = "Hair style of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr1, expr2);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.NotSure, actual);
}
[TestMethod]
public void RelativeBeforeTest_RightNotSure_NotSure()
{
    Context target;
    var obj = CreateTarget(out target);

    var expr1 = new ExpressionIs(new KnowledgeRelation { Subject = "Undercut", Relation = "Hair style of", Target = obj.ToString() });
    var expr2 = new ExpressionIs(new KnowledgeRelation { Subject = "Lawyer", Relation = "Occupation of", Target = obj.ToString() });
    var relative = new RelativeBefore(expr2, expr1);
    var actual = target.Evaluate(relative);
    Assert.AreEqual(EvaluationResult.NotSure, actual);
}
private static Person CreateTarget(out Context target)
{
    var obj = new Person("Alice");
    obj.Occupation = "Student";
    target = new Context(obj.ToString());
    target.AddFrame(FrameFactory.Create(obj));
    obj.Occupation = "Lawyer";
    target.AddFrame(FrameFactory.Create(obj));
    return obj;
}


Conclusions and future work

The method to determine a 'full' frame by aggregating each column backwards gives room for uncertainty as we don't really consider the time between two events that are aggregated together into one frame, if we only have a few records of knowledge and the time between those events is years, then maybe we should be a little bit more uncertain.. a little bit more fuzzy in our determination. Or perhaps return a probability value together with the result. I.e.
True: 0.95
False: 0.1
NotSure: 0.4
And that way be able to build a little more smooth evaluations. But for now this suites my needs.
Another improvement could be to add variance per knowledge column. I.e. if the name is always Kate, then variance should be 0, but for the hair color in the example above it should be way higher as it changes for each event..
Addition of more types of relative expressions could be useful. Exists, Followed by, X years ago etc. But here I think the requirements for each type of project needs to guide the way.

For example source code, head over to my github repository and play around for yourself:


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

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
Expression evaluation over time

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