How Could I Apply Graph Theory to TCG?


#1

Okay, I’m nowhere near an expert in math or computer science. I am just curious.
The Graph Theory I’m talking about is more relevant to Computer Science.

Take a 60 card deck as 60 vertices (or nodes). Some cards, such as ultra ball, can retrieve other specific cards, like shaymin EX. Some draw any random card. Some dicard cards, and others take cards from the dicard pile.

Those connections between cards are edges, and groups of edges form paths. Edges can be represented in matrices, which can be taken to the nth power to find paths of length n.

Basically, using this logic of paths, you can find how well your deck flows together, the overall consistency of your deck. I’ve read articles on the first turn hand probability, but in this VS seeker, Battle Compressor, Shaymin EX, Trainers Mail and Delinquent format, that is not as important as the consistency of your hand.

Does anyone know a way to apply this? Again, I’m no expert on the subject, I’m just asking.


#2

Considering that your deck is completely randomized, I’d say you can’t, but I’m no expert.


#3

Hmmm it’s possible to write a computer program that could find the possibility of you drawing certain cards via ultra ball/shaymin/trainers mail etc, python would probably be the best language to program that in, but I mostly study javascript so I wouldn’t know.


#4

I wasn’t going to say it initially, but, yes, that’s what I’m hoping to achieve with this question.
I’m already somewhat proficient in java. I don’t really care which language to use, I just need to do it.

I have already been able to take TheMathTCG’s formulas and implement them in java. However, those are not enough.

Also,they only work for the start of the game. They do not apply after you set out your prizes. Midgame, you have to factor in the possibility that a card is prized, and that is also affected by the amount of basics in your deck.

By using Graph Theory and probability, I’ll be able to come up with an algorithm to program to calculate consistency.

The problem is that I cannot make matrices of ones and zeros to represent connections between cards,and call it correct. Take acro bike. It draws any two random cards. Roller skates draws even more cards, 3. That does not mean roller skates makes your deck more consistent than acro bike. So I would have to factor in probability somewhere, but I do not know where, nor how.

Another possibility to do this is to generate a hundred random matches and see what probability that gives, but that is inefficient and seems like even more work.


#5

Your best bet is to create an adt for your object (card) and build your graph theory storing that adt instead of a Boolean.


#6

If you have the time, you could draw this all out on a graph on multiple pieces of paper, and then it might be easier to program in that form.


#7

To clarify, I am treating a deck as a Directed Acylic Graph (for now), meaning you cannot use the same exact card twice (duhh). I actually don’t know how to calculate paths on that though.

So does anyone know how to calculate the amount of paths of a certain length on a Directed Acylic Graph? That would help.

I’m not factoring in comboing from the hand or discard (VS seeker + Battle compressor, for example) because I just would not know how to go about doing this. This would basically be an algorithm for going from card-to-card in a deck.

Update
I actually figured out the algorithm myself. As stated earlier by CelloJake, I need to use an ADT to represent an edge. It contains the probability of the edge’s existence, and the name of the two nodes that make the edge (so there’s no professor sycamore -> prof Sycamore - > get more cards possibility) That probability I can calculate with equations which were made before. I drew a diagram to illustrate these relationships and such, and I get how it works now. Thanks!


#8

I would love to see the program when your done! If you need more help let me know. Your project is much different than mine. I am working on a program to run 1000 (or some number ) of opening hands /prizes / first draw of any given deck and give a statistical report on it. It’s limited to opening hand consistency though.


#9

I’m also working on a program to determine opening hand statistics, prize odds, etc. but it’s still in the very early stages, mostly because I’m just starting to learn programming.


#10

I’ve always wanted to try something like this, but I’m not the best at coding. I’d love to see how this project progresses!


#11

Um…
There are already articles that detail opening hand probability :stuck_out_tongue:


It seems that MNchino just wanted to take it a lot further, by calculating the overall consistency of a deck


#12

I mean specific hand probability over a course of a few thousand games. Not individual calcs but with a full 60 card list. I do not need to know the chance at starting with a supporter but how opening hands interact and develop when changing 1-2 cards in a list. My goal is very similar to mn’s except it is a lot simpler to do an opening hand scenario compared to his complex, but awesome, scenario.


#13

Actually, it’s not a “duhh” at all as to whether or not you can reuse a card, as there are already several mechanics that allow for such a thing. You could use VS Seeker to retrieve supporters, Dowsing Machine to retrieve trainers, sacred ash to recycle pokemon, super rod for pokemon + energy, Milotic for anything, Puzzle of Time for anything, etc.


#14

Great topic, the cordination between the members proves these forums are quite useful.


#15

Yeah. That makes it much more complicated. However, right now I’m going with a simple algorithm, not factoring that in…for now. If I don’t use a DAG, that would mean I could use shaymin EX to get the exact same shaymin EX to get the exact same Shaymin EX, and so on…


#16

You could have used/discarded cards in a priority linked list and cards like puzzle of time or super rod would follow the priority order (while loving past nodes that do not function with that card type eg super rod wouldn’t grab items.) but I would worry about things like that after a simpler program is working


#17

But doesn’t that not account for what your opponent is playing, or what they do?


#18

This is mostly for “How often do I achieve such and such a board state t1”, answering such questions as “How often would LatiDonk have worked w/ LTC?”, “What’s the best NM deck for t1 180”, etc.


#19

Exactly. Another example would be frequency of t1 Bridgette with octillary gallade


#20

the frequency of drawing into brigette in your first turn (including your t1 topdeck) assuming you go first or your hand doesn’t get altered is
if you play 1: 11.8%
if you play 2: 22.5%
if you play 3: 32%
if you play 4: 40.5%