Rating system incorporating experience
One option is to use something like the beta-binomial model.
The general idea is that players' true success rates (or winning frequency) come from an underlying distribution (e.g. a beta distribution). As a player plays more games and you get actual information on wins and losses, the prior information from the beta distribution is combined with the wins/losses information which is expected to follow a binomial distribution (based on the true success rate $p$), and a posterior estimate of the success rate made as $$\hat{p}=\frac{n_{\text{wins}}+\nu\rho}{n_{\text{games}}+\nu}$$ where the beta distribution essentially has the effect of a prior information equivalent to $\nu$ games with $\rho$ success rate.
The advantage of this method is that for playes with few games, the estimated success rate is shrinked towards the population mean; extreme success rates due to highly uncertain success rate estimates for playes with few games are avoided.
Due to the similarity with Bayesian methods, this type of approach is often referred to as empirical Bayes. However, the parameters $\nu$ and $\rho$ used to specify the beta distribution are estimated using traditional frequentist methods (moment or maximum likelihood estimates).
NB: I'm assuming, although it wasn't stated clearly, that these are solitaire games: i.e. one-player games. If they are two-player games, the strength of the opponents must be taken into account. A similar approach may still be used to provide a prior distribution for the strength of new players, but that would have to be a rather different model than the beta-binomial.
As requested in the comments, here are some more details on how this is done. I'll do it using the beta-binomial model, but the same principle applies to a number of similar models (e.g. see Wikipedia's article on Empirical Bayes).
Let's assume we have $N$ players, where player $k$ has played $n_k$ times and won $x_k$ of them. We assume that player $k$ has an underlying probability $p_k$ of winning each time (the game is still solitaire, so no opponents on which this could depend) and so the number of wins, $x_k$, should come from a binomial distribution $\text{Bin}(n_k,p_k)$.
We could, of course, estimate $p_k$ based on $x_k$ and $n_k$ alone: i.e. $\hat{p}_k=x_k/n_k$. However, if $n_k$ is small, this estimate would be very uncertain.
In order to reduce the uncertainty of the estimate, we assume that the winning probabilities, $p_k$, come from a beta distribution. Why a beta distribution, you might ask? Because it is conjugate to the binomial distribution, which makes the maths easier.
Note that the beta distribution is usually defined as $$\text{Beta}(\alpha,\beta) \sim \frac{x^{\alpha-1}(1-x)^{\beta-1}}{B(\alpha,\beta)} \mbox{ where } B(\alpha,\beta)=\frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}. $$ Often parameters $\rho=\alpha/(\alpha+\beta)$ and $\nu=\alpha+\beta$ are used instead (which are the ones I used above), however I'll stick to $\alpha$ and $\beta$ here to reduce confusion.
If we assume the underlying (but unknown to us) winning probability, $p_k$, is drawn from a beta distribution with parameters $\alpha, \beta$, and then $x_k$ is drawn from $\text{Bin}(n_k,p_k)$, the posterior probability distribution is $\text{Beta}(\alpha+x_k,\beta+n_k-x_k)$. The expected values of $p_k$ given $x_k$ and $n_k$ is thus $$\text{E}[p_k|x_k,n_k]=\frac{\alpha+x_k}{\alpha+\beta+n_k}.$$
The tricky part is finding good estimates for $\alpha$ and $\beta$. Remember, these parameters govern how the underlying probabilities, $p_k$, are distributed: e.g. the expected value and the variance.
I believe the preferred method will often be maximum likelihood estimates: i.e. the values of $\alpha$ and $\beta$ that maximise $$ \prod_{k=1}^N \Pr(x_k|\alpha,\beta,n_k) =\prod_{k=1}^N \int_0^1 \Pr(x_k|n_k,p_k)\cdot\Pr(p_k|\alpha,\beta)\, dp_k $$ where the right-hand side contains the probability functions for the binomial distribution (of $x_k$) times that of the beta distribution (for $p_k$).
Another alternative are moment estimates.
Here's a quick walk-through of the computations.
The unknown parameters, $\alpha$ and $\beta$ of the beta distribution, describe the distribution of success probabilities of players, $p_k$ for player $k$: $$ \Pr(p_k|\alpha,\beta)=\frac{p_k^{\alpha-1}(1-p_k)^{\beta-1}}{B(\alpha,\beta)} $$ where $$ B(\alpha,\beta)=\int_0^1 x^{\alpha-1}(1-x)^{\beta-1} =\frac{\Gamma(\alpha)\Gamma(\beta}{\Gamma(\alpha+\beta)} $$ and $\Gamma(x)$ is the gamma-function ($\Gamma(x)=(x-1)!$ for $x\in\mathbb{N}$).
Given the success probability $p_k$ of player $k$ and the number $n_k$ of games played, the probability of $x_k$ wins is $$\Pr(x_k|p_k,n_k)={n_k\choose x_k}p_k^{x_k}(1-p_k)^{n_k-x_k}.$$
The likelihood of $x_k$ wins given $\alpha$ and $\beta$, but treating $p_k$ as an unknown, is then given by $$ \begin{split} \Pr(x_k|\alpha,\beta,n_k)=&\int_0^1 \Pr(x_k|p_k,n_k)\cdot\Pr(p_k|\alpha,\beta)\,dp_k\\ =&\int_0^1 {n_k\choose x_k} \frac{p_k^{\alpha+x_k-1}(1-p_k)^{\beta+n_k-x_k-1}}{B(\alpha,\beta)}\,dp_k\\ =&{n_k\choose x_k}\frac{B(\alpha+x_k,\beta+n_k-x_k)}{B(\alpha,\beta)}. \end{split} $$
If there are $N$ players, i.e. $x=(x_1,\ldots,x_N)$ and $n=(n_1,\ldots,n_N)$ are the number of wins and games played by each player, the likelihood function, i.e. the probability of $x$ given $\alpha$ and $\beta$ is $$ L(x|\alpha,\beta) =\prod_{k=1}^N \Pr(x_k|\alpha,\beta,n_k) =\prod_{k=1}^N {n_k\choose x_k}\frac{B(\alpha+x_k,\beta+n_k-x_k)}{B(\alpha,\beta)}. $$
The maximum likelihood method basically consist of finding the parameters, $\alpha$ and $\beta$, that maximises the likelihood function: i.e. the parameters that make the data as likely as possible. In order to do this, it is easier to write out the log-likelihood, i.e. the logarithm of the likelihood function, entering the expression for $B$:
$$ \begin{split} l(x|\alpha,\beta)=&\ln L(x|\alpha,\beta)\\ =&\sum_{k=1}^N \ln{n_k\choose x_k}+\ln B(\alpha+x_k,\beta+n_k-x_k)-\ln B(\alpha,\beta)\\ =&\sum_{k=1}^N \Big[\ln{n_k\choose x_k}\\ &\qquad+\gamma(\alpha+x_k)+\gamma(\beta+n_k-x_k)-\gamma(\alpha+\beta+n_k)\\ &\qquad-\gamma(\alpha)-\gamma(\beta)+\gamma(\alpha+\beta)\Big]\\ \end{split} $$ where $\gamma(x)=\ln\Gamma(x)$.
Finding the $\alpha, \beta$ that maximise $l(x|\alpha,\beta)$ is done numerically, e.g. using Newtons method which involves solving $\frac{\partial}{\partial\alpha}l(x|\alpha,\beta) =\frac{\partial}{\partial\beta}l(x|\alpha,\beta)=0$. Note that the binomials ${n_k\choose x_k}$ are constant with respect to $\alpha$ and $\beta$ and so can be ignored.
For the numerical solution, it is helpful to have to digamma function $\Psi(x)=\gamma'(x)=\Gamma'(x)/\Gamma(x)$ available since the derivatives of the log-likelihood is a sum of these. For large $x$ (not close to zero), $\Psi(x)\approx\ln(x-1/2)$; for small $x$, one may use $\Psi(x)=\Psi(x+k)-\sum_{j=0}^{k-1}\frac{1}{x+j}$, although I suppose there may be more efficient ways of computing it.
The estimated values of $\alpha$ and $\beta$, i.e. the values that maximise $l(x|\alpha,\beta)$, are usually denoted $\hat\alpha$ and $\hat\beta$ to distinguish them from the actual (but unknown) values. These estimated values are then plugged in to get an estimate for the success rate of player $k$: $$\hat{p}_k=\frac{x_k+\hat\alpha}{n_k+\hat\alpha+\hat\beta}.$$
You should compute a combined score that considers both the win/loss ratio and the number of games played. The combination will need a parameter that weighs how important win/loss ratio (or the number of games played) in the overall ranking. For example, the score of player 1 will be $score(p_1) = \alpha \frac{\#wins}{\#games\_played} + (1-\alpha)\frac{\#games\_played}{\#max\_num\_of\_games}$. You should set the value of $\alpha$ according to your taste or any constraints the ranking has (if any).