Notes about solving for castability
Closed this issue · 2 comments
Line 113 in 813cb4a
Hey, not sure if you're still making updates on this source code but I can provide some information on how to solve for castability on basic tap to produce one color of mana from some set.
First, as I read the algorithm outlined in the link I believe you can find counter examples like the one below.
Goal: {W}{U}{U}{B}{R}{G}
Sorted Lands: (I believe this is a valid ordering)
{W}{U}
{U}{B}
{U}{B}
{W}{G}
{R}{G}
{R}{G}
The first land {W}{U} needs to tap for {U}, however I believe your algorithm will attempt to tap for {W} instead. I think the situation is going to get even more complicated with the upcomming tri-lands.
In general, tapping lands can be characterized by the Bipartite Matching problem. In this case the "lands" are on one side of the graph and each pip of mana required in the cost is on the other side of the graph. Then there is an edge between a land and a cost pip if the land is compatible with the color of the pip.
However, even this won't help with some of the more esoteric lands like Lotus Field or Interplanar Beacon. To solve those I think some amount of backtracking is probably required.
Thank you for taking the time to read the source and write-up an excellent issue!
First, as I read the algorithm outlined in the link I believe you can find counter examples like the one below.
You are correct. I added this counterexample as a test case and confirmed that it indeed causes my heuristic to return an incorrect result.
In general, tapping lands can be characterized by the Bipartite Matching problem. In this case the "lands" are on one side of the graph and each pip of mana required in the cost is on the other side of the graph. Then there is an edge between a land and a cost pip if the land is compatible with the color of the pip.
This is a great insight. #17 replaces my incorrect heuristic with an implementation of the Ford-Fulkerson method for computing maximum flow and all 165 test cases now pass, including your provided counterexample. I would like to spend some more time with the problem space and code before merging though; this is a great opportunity to refresh my graph theory knowledge.
However, even this won't help with some of the more esoteric lands like Lotus Field or Interplanar Beacon. To solve those I think some amount of backtracking is probably required.
Unfortunately, these more esoteric lands are out of scope for the amount of effort I'm currently willing to devote to this project.
Thanks again for your contribution!