Another discussion about optimizing breeding

[Warpten]

Greetings,

Having returned fairly recently and having played through Sinnoh, I decided to try to take one an idea I got back when Unova was released: producing a program able to optimize pokemon breeding for breeders like me that hoard pokemons in boxes.

 

A quick forum/google search yielded nothing of particular interest. Some people (see here) seem to have started on the idea but quickly given up for obvious mathematical concerns, but I attempt here to explain the algorithms here I use and the problems they each have.

 

For the purpose of simplicity, I am excluding natured breeding here. If you want to nature a pokemon, you should know the only solution is to breed each intermediate pokemon with one that has one less set IV, and an everstone attached. Or get lucky and get a random natured offspring that matches what you want.

 

Let's get into it. The code here will be C# because it allows for quick design. I think C++ is a must here but I'll explain why later on in this post.

 

The basics

 

The first question we should ask ourselves is this: for a Nx31, what are the parent pairs of (N-1)x31 that can breed together?

From this simple question, two rules arise:

1. Parents need to share (N-2) IVs.
2. Parents need to each have 1 IV they do not share.

 

They obviously need to be able to breed together, so gender is also an issue, but we won't discuss that here, for the sake of simplicity.

 

This can easily be written up as a bitmask, where each IV is a bit. 1 means that we have a 31, 0 means any other value.

 

    public enum Statistic : uint
    {
        Health         = 0x01,
        Attack         = 0x02,
        Defense        = 0x04,
        SpecialAttack  = 0x08,
        SpecialDefense = 0x10,
        Speed          = 0x20
    }

This is, inherently, pretty much all we need to represent a pokemon, barring gender and nature considerations.

We are going to be abusing popcnt to know if pokemons can breed:

 

public class Pokemon
{
	public readonly Statistic Statistics;
	public readonly ulong UUID;

	private static ulong _generator = 1;

	public Pokemon(Statistic statistic)
	{
		Statistics = statistic;
		UUID = _generator++;
	}

	public bool CanBreedWith(Pokemon other)
	{
		if (other.UUID == UUID)
			return false;

		// Can only breed if
		// 1. Two IVs not shared at most.
		// 2. All IVs but one shared exactly.
		var ourMask = (uint) Statistics;
		var otherMask = (uint) other.Statistics;

		var sharedStatCount = (ourMask & otherMask).CountBits();
		var expectedSharedStatCount = ourMask.CountBits() - 1;
		var nonSharedStatCount = (ourMask ^ otherMask).CountBits();
		if (nonSharedStatCount != 2 || sharedStatCount != expectedSharedStatCount)
			return false;

		return true;
	}
}

This is failry cheap to do, since we can abuse bitwise operators to perform the checks.

 

With our abstraction in place for a Pokemon, let's look at the algorithms we can use.

 

Algorithm A.

 

Algorithm A tries to find a breeding path by breeding pokemons until they can no longer breed.

Given a set of M varying pokemons, we just breed everyone with everyone, but we add one rule: a pokemon can't breed with another pokemon that shares a parent with them. Why is that?

Because we are essentially generating a new pokemon pool from an existing pool, we are reusing parents across multiple breeds. That means that a pokemon can have more than one child in the next pool, and these children are banned from breeding with each other, because we lose parents when we breed in the game. This also very conveniently gives us the end condition: we keep breeding until we are unable to produce any child.

 

public class TreeNode<T>
{
	public readonly T Data;
	public readonly TreeNode<T> Left;
	public readonly TreeNode<T> Right;

	public TreeNode(T data, TreeNode<T> left, TreeNode<T> right)
	{
		Data = data;
		Left = left;
		Right = right;
	}

	public TreeNode(T data) : this(data, default, default) { }
}

public class BreedingPool
{
	public Func<TreeNode<Pokemon>, TreeNode<Pokemon>, bool> BreedingRule { get; set; } = (l, r) =>
	{
		if (!l.Data.CanBreedWith(r.Data))
			return false;

		// Can't breed if we share parents
		foreach (var leftParent in new[] { l.Left, l.Right })
			if (leftParent != null)
				foreach (var rightParent in new[] { r.Left, r.Right })
					if (rightParent != null && rightParent.Data.UUID == leftParent.Data.UUID)
						return false;

		return true;
	};

	public List<TreeNode<Pokemon>> DataSource { get; set; } = new List<TreeNode<Pokemon>>();

	public IEnumerable<TreeNode<Pokemon>> BestBreeds
	{
		get
		{
			var children = DataSource;

			while (true)
			{
				var nextGeneration = new List<TreeNode<Pokemon>>();

				for (var i = 0; i < children.Count; ++i)
				{
					var leftParent = children[i];

					for (var j = i + 1; j < children.Count; ++j)
					{
						var rightParent = children[j];

						if (!BreedingRule(leftParent, rightParent))
							continue;

						var newChild = new TreeNode<Pokemon>(
							new Pokemon(leftParent.Data.Statistics | rightParent.Data.Statistics),
							leftParent, rightParent
						);
						nextGeneration.Add(newChild);
					}
				}

				if (nextGeneration.Count == 0)
					return children;

				children = nextGeneration;
			}
		}
	}
}

Quote

Note that the code above is incomplete: if we were breeding two 1x31 but we had an extra 2x31 in the pool, it would be discarded, despite being usable in the next step. We would thus be calculating that the best breed is a 2x31, while it should be a 3x31.

This algorithm has a couple of drawbacks, and the biggest one is space (both memory and search). Because we are generating countless "useless" pokemons, we exceed system memory very fast. The solution to this is to not mix children with shared parents in the first place, but I haven't been able to write an efficient algorithm for it, because it is basically a very specific variant of a permutation problem, where the amount of groups and the size of each group is the result of a combination problem of its own. In my testing, this algorithm bottlenecks at 4x31 breeds.

The second drawback is that this algorithm is not lazy: for each step, we need to calculate all children, meaning we can't provide one solution without having calculated all solutions.

 

Algorithm B

 

Algorithm B takes the inverse approach of that of algorithm A. Given a target IV spread, what parent pairs work? We then recursively search down until we find pokemons in our initial pool we can use.

 

    public class BreedingTree
    {
        public TreeNode<Pokemon> Tree { get; private set; }
        public List<Pokemon> ConsumedInputs { get; } = new List<Pokemon>();

        public static IEnumerable<BreedingTree> Solve(List<Pokemon> source, Pokemon target)
        {
            var candidatePokemon = source.Where(s => s.Equals(target)).Distinct().ToList();
            if (candidatePokemon.Count == 0)
            {
                // Matching pokemon not found in candidates, generate left and right nodes
                foreach (var (leftTarget, rightTarget) in target.Parents)
                {
                    var leftSubTrees = Solve(source, leftTarget);
                    foreach (var leftSubTree in leftSubTrees)
                    {
                        var rightSource = new List<Pokemon>(source);
                        rightSource.RemoveRange(leftSubTree.ConsumedInputs);

                        var rightSubTrees = Solve(rightSource, rightTarget);

                        // We know immediately all pairs work here
                        foreach (var rightSubTree in rightSubTrees)
                        {
                            // Make sure both can breed
                            if (!rightSubTree.Tree.Data.CanBreedWith(leftSubTree.Tree.Data))
                                continue;

                            var tree = new BreedingTree() {
                                Tree = new TreeNode<Pokemon>(target, leftSubTree.Tree, rightSubTree.Tree)
                            };
                            tree.ConsumedInputs.AddRange(leftSubTree.ConsumedInputs);
                            tree.ConsumedInputs.AddRange(rightSubTree.ConsumedInputs);
                            // Console.WriteLine("Found breeding mon ({0} inputs, [{1}] + [{2}]).", tree.ConsumedInputs.Count, tree.Tree.Left.Data.Statistics, tree.Tree.Right.Data.Statistics);
                            yield return tree;
                        }
                    }
                }
            }
            else
            {
                foreach (var candidate in candidatePokemon)
                {
                    var tree = new BreedingTree()
                    {
                        Tree = new TreeNode<Pokemon>(candidate)
                    };
                    tree.ConsumedInputs.Add(candidate);
                    yield return tree;
                }
            }
        }

        public static IEnumerable<BreedingTree> Solve(List<Pokemon> source, Statistic target)
            => Solve(source, new Pokemon(target, default));
    }

This is the first algorithm I wrote and it is decently fast at finding one path to the desired IV spread. It is however not necessarily the best path.

 

Finally, some benchmarks:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.1139 (1909/November2018Update/19H2)
Intel Core i7-7700HQ CPU 2.80GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores
  [Host]     : .NET Framework 4.8 (4.8.4250.0), X86 LegacyJIT
  DefaultJob : .NET Framework 4.8 (4.8.4250.0), X86 LegacyJIT


|                 Method |          Mean |       Error |      StdDev |    Gen 0 | Gen 1 | Gen 2 | Allocated |
|----------------------- |--------------:|------------:|------------:|---------:|------:|------:|----------:|
| '3x31 (Genderless, B)' |      9.563 us |   0.1889 us |   0.2585 us |   2.5940 |     - |     - |   7.98 KB |
| '3x31 (Genderless, A)' |      1.802 us |   0.0356 us |   0.0437 us |   0.5608 |     - |     - |   1.73 KB |
| '4x31 (Genderless, B)' |    407.218 us |   8.1353 us |  12.9034 us | 109.8633 |     - |     - | 337.97 KB |
| '4x31 (Genderless, A)' | 27,989.286 us | 535.8662 us | 733.4997 us |  93.7500 |     - |     - | 342.01 KB |

As you can see, we start seeing the effect of space constraints for algorithm A on a 4x31 solve. 5x31 just exceeds my 16GBs of RAM.

 

I'm willing to share the entire code (includes a GUI, a benchmark project, and a test project) with people that fully intend to help with this. Please no leechers. I fully expect some people to have solved this but not share their solution because "muh economy" and I think it is a fascinating optimization problem that fully deserves to be solved for everyone.

 

Cheers

A guy that hoards Ferroseed.

[Quinn010]

yes 

[Poufilou]

It's very interesting nerd-wise. But spending 10 minutes reading a guide about breeding and do a couple experiences in game is much faster. People also enjoy breeding and finding their own way to optimize it. 

 

Don't want to ruin your fun and I think it's interesting project but just saying that the probability of it being in anyway useful to players is low.