How to model the probability of this gift exchange? There is a gift exchange with $N$ people using the following rules:


*

*Everyone starts with a randomly selected wrapped gift.

*The people take turns rolling a 6-sided die to determine what action to take. Rolling a 1 or a 2 means that person gets to open the gift in front of them - and that person is taken out of the rotation. Rolling a 3, 4, 5, or 6 causes other events that shift around the wrapped gifts (i.e. that person cannot open their gift yet).

*The game ends once every gift has been opened.


I wanted to know how many turns this gift exchange should go on until completion but I couldn't figure out how to model that. I try restructuring it as "What is the probability it will end in $X$ turns?" but still didn't get far. Any ideas?
I know the probability of opening a gift on any given turn is $\frac{2}{6} = \frac{1}{3}$. So I could calculate the probability of the gift exchange ending as fast as possible ($N$ turns for $N$ people), which would be $\left(\frac{1}{3}\right)^N$. How can I expand on this to compute the probability of the exchange ending in $X$ turns, where each turn has a $\frac{2}{3}$ chance of "no gifts opened"?
 A: 
I wanted to know how many turns this gift exchange should go on until completion... 

You are inquiring about the expected number of times the dice is to be thrown. At a glance this count seems to be a sum of geometric random variables.
$$C=\sum_{i=1}^n G_i$$
where $G_i$ is the geometric random variable counting the number of times the dice has to be thrown, for the $i$-th person to be eliminated (open the gift)
$$G_i\sim G(\frac{1}{3}).$$
You are interested in the expected number of tries needed.
$$E(C)=E(\sum_{i=1}^n G_i)=\sum_{i=1}^n E(G_i)=nE(G)=n\cdot\frac{1}{p}$$
where $p$ is the probability of success on each try, $\frac{1}{3}$ in your case. For completion, the expected number of trials/turns for a geometric random variable is $\frac{1}{p}$.
So, for a group of a $100$ people, it would take
$$100\cdot\frac{1}{\frac{1}{3}}=300$$
turns for all of them to be eliminated (open their gifts).
Modeling the gift exchange - Negative binomial distribution
You could have asked

What is the probability that the $n$-th elimination (gift opening) is preceded by exactly $N$ failures (and $n-1$ eliminations)?

and model the same procedure. Than, the probability for a game involving $n$ people to end on the $N$ turn is
$$P(N,n)=\binom{N+n-1}{N}(1-p)^Np^n$$
which is the negative binomial distribution. 
A note on the expectation of the negative binomial
Please note that the expected value that is cited on the wiki
$$\tilde{E}(C)=n\frac{1-p}{p}$$
counts the expected numbers of failures. The number you inquired about, and we caluclated above counts all trials. To get it from the cited formula for the number of failures, we add the number of successes to it
$$\tilde{E}(C)+n=n\frac{1-p}{p}+n=n\frac{1}{p}=E(C)$$
Simulation
Lets test the solution with a simulation of the game in numpy.
import numpy as np
def foo(n):
  k=n
  count=0
  while k>0:
   count+=k
   throws=np.random.randint(1,7,k)
   k-=np.sum((throws==1)|(throws==2))
  return count
np.mean([foo(100) for _ in range(10000)])


299.997

Simulation matches the result.
I hope I understood your procedure correctly. To me, one throw of the die was considered to be one try/turn.
A: Note that in theory, there's no limit to how long the game can last: if you're sufficiently unlucky, then in theory there's no limit to how many rounds in a row you can get a "no-gifts" result on the die. That being said, the expected number of rounds before all N gifts are open is 3N (as shown below), and there's a nice formula for computing the probability that the game has ended after $k$ rounds, for any $k$. Even though this probability is never exactly 100%, this probability approaches 100% as $k$ becomes large.
Expected number of rounds is 3N
We can relate the outcomes of this game to the outcomes of a related game where we flip a coin that has a probability $\frac{1}{3}$ of HEADS and a probability $\frac{2}{3}$ of TAILS.  In particular, HEADS means "open a gift" and TAILS means "don't open a gift".
There are $N$ gifts in total and the game ends when they're all open. So, the expected number of rounds before the game is over is the expected number of coin tosses before $N$ successes. The expected number of coin tosses before $N$ successes is $N/p$, where $p$ is the probability of success. Here, "success" means "opening a gift", so:

Expectation = $\frac{N}{p} = \frac{N}{1/3} = 3N$ rounds to open all N gifts.

That is, the game is expected to end after $3N$ rounds, where $N$ is the number of gifts to be opened. (This makes sense: imagine if the probability of opening a gift were 100%, or if it were 1/2, and so on.)

A formula for probability of ending after k rounds
Similarly, the probability that the game has ended after $M$ turns is the probability of flipping $M$ coins and getting at least $N$ heads. (The reason it's alright to get more than $N$ heads is because we can imagine that the game ended after $N$ heads and we just kept flipping coins anyways even though it had no more effect.)
The probability of flipping $M$ coins and getting at least $N$ heads is:
$$P(M,N) \equiv \sum_{h=N}^M {M \choose h} \left(\frac{1}{3}\right)^h \left(\frac{2}{3}\right)^{M-h} = \left(\frac{2}{3}\right)^M\sum_{h=N}^M {M \choose h} 2^{-h}$$
This is equivalent to the probability of the game ending after $M$ rounds or less. Unfortunately, it's a pretty messy formula with many terms—in the next section, I'll show how we can use matrix math to get a more compact way to calculate these and other probabilities.

An improved formula using matrix math
Suppose we keep track of the number $g$ of gifts we've opened so far. Initially, $g=0$, and we know the game ends when $g=N$. In each round, either $g$ becomes incremented (probability 1/3) or stays the same (probability 2/3).
Because we can model this problem as various "states of the world" with a probability of transitioning between them, we can use a branch of matrix math (specifically Markov processes) to efficiently compute probabilities of different outcomes. 
To do so, we make an $(N+1)\times (N+1)$ transition matrix $T$. The entry $T_{i,j}$ is the probability of starting in state $g=i$ and going to state $g=j$ after one round. In our case, we have:
$$T_{i,j} = \begin{cases}\frac{1}{3}&\text{if }i=j-1\\\frac{2}{3} &\text{if }i=j<N\\1&\text{if }i=j=N\\0&\text{otherwise}\end{cases}$$
(Also we've included the rule that whenever $g=N$, it remains at $g=N$ because the number of opened gifts can't increase anymore.)
So, for example, if there are $N=4$ gifts, the transition matrix is 5×5 and looks like:
$$T = \begin{bmatrix}\frac{2}{3}&&&&\\\frac{1}{3}&\frac{2}{3}&&&\\&\frac{1}{3}&\frac{2}{3}&&\\&&\frac{1}{3}&\frac{2}{3}&\\&&&\frac{1}{3}&1\end{bmatrix}$$
Now, it turns out that powers $T, T^2, T^3, \ldots, T^k$ of the transition matrix $T$ compute important probabilities. Specifically:

The first column of $T^k$ lists the probabilities that various numbers of gifts are open after exactly $k$ rounds. In particular, the bottom-left entry of $T^k$ is the probability that all $N$ gifts are open—so the game has ended—by the $k$th round.

This gives a compact way to compute the probability that the game has ended by the $k$th round, for any $k$.
A: To end in exactly $X$ turns you need to select $X-N$ times out of the first $X-1$ to have no gift opened, then open one on turn $X$.  The chance is then ${X-1 \choose X-N}(\frac 23)^{X-N}(\frac 13)^N$
