Graph theoretic Difficulty Analysis

Game: freecell
Game #: 782490518


What would you like to see?


I am a former theoretical physicist trying to break into the tech industry. I have an idea for a graph theoretic analysis of non competitive game difficulty and I would like to try to validate it against your leader boards. Is there any way I can get access to a snapshot of the leader boards as csv file, get information on how to translate game numbers to card configurations? I will share my work with you if successful. I feel you could use it to develop progression features and give user focused rankings rather than competitive rankings (the competitive rankings reward people for replaying configurations from memory rather than their ability to solve a difficult game from scratch).

Comments

  • Easy on the stash B)

  • slow down boy !!!!

  • Scabs as a new comer to the games thats a lot of big words !! WHAT is it that you really want..

  • sounds like a russian plot to fix the next election

  • Why is it the new comers has all the complaints and all the answers We've been playing for years with no problem!!! This site is good as it is!! No downloads ;No ads ;;No noise and i get to talk to people all over the world . WHAT MORE COULD I ASK FOR ???

  • For me, nothing :)

  • I totally agree with you, reminds me of everytime you turn on the news you hear about Donald Trump , getting in trouble with his tweets. Only been hear a few months, and this one takes the cake, on the newcomer you messaged scabs about his vocabulary I ain't the brightest , speak in lamens term we might understand what he's complaing about, :(

  • Thanks for the backup Springrain & Gerald64 this is one of the best sites i've been on for a long time I feel i don't need to win or make the leader board I just like to play and talk to real people every now and then.

  • I don't care if I'm first, last, or some place in the middle. All I want is a nice place to forget the aches and pains of the day where I'm not rushed nor forced to compete. To those who enjoy competing, great, I'm happy for you.

  • Springriin i agree with you 100% thanks for the comments and i still hope you get that Washington Wabbit

  • For the record I wasn't complaining. I was offering to do free high level programming work for the site in exchange for the use of the leader board data and the right to post my code and the data on my code repository and put it on my cv.

  • I will probably just write a crawler to scrape the site if I don't get a reply.

  • It's only game, not a scientific institution.Play on.

  • It's SOL-IT-AIRE ...right? I don't want it to be competitive but, to be honest, I do notice who whoops my fanny when my score pops up. But ...to each their own. I'm a newbie myself so I'll let the powers that be decide.
    Good luck to ya, Scabs

  • daviddavid REGISTERED, ADMINISTRATORS
    edited February 2018 76.170.47.184

    I don't understand the hostility guys. I'm curious about what @Scabs wants to do. Can you tell Jim and I more about your idea?

    As for data: It depends on what kind of data you need. Currently our games database is 3TB, which makes it a bit unwieldy (only 1.2TB of that is "proper" high score data—but still unwieldy). Honestly I'm a bit hesitant to just give out large chunks of data (speaking just for myself here—Jim might have a different opinion).

    For converting Game # ("seeds") into card layouts—We're a bit embarrassed by that code :-). We're currently using an imperfect shuffle algorithm and a simple (but not great) RNG ported from newlib. I got real close to changing that in the past few weeks (our goal is perfect shuffle + Mersenne Twister), but got stalled by some annoying legacy DB technicalities (we've got some bad data in there that I need to either fix or destroy).

    One idea I've been toying with is online "matches" that take place in real time, similar to the way other competitive online games work (think Call of Duty style shooters). That would take away the memorization factor, since you'd only be allowed to play something once, sight unseen. For the people who like the competition, it might be a more attractive way to compete (people who don't like to compete—don't worry, we'll never take away the ability to just casually play).

  • Hi David,
    on the plus side of being able to play the same game more than once is the learning/honing skills aspect. My game of choice is Scorpion and often when I've finished a game and other players have higher scores I will replay the game to see if I can find the way to reach the higher score.

    but yes, fair call on the 'game of the day' having only one crack at it for scoring purposes would make it more skill driven, rather than memorisation. Happy for the first attempt score to count as competitive (i.e. Displayed on the score card) but would still like a chance to try again and better my score even if that means only I can see the result of playing again and the published score card is not affected. :)

  • Fwiw, I would be very interested in seeing a difficulty metric that can be computed in a computationally efficient manner for arbitrary layouts. Please let us know if you make progress on this, Scabs.

  • I can't understand any of this.Must be my age.

  • I agree with fingsaint, as I have replayed many a scorpion game to achieve your score. :-) I also have some background in graph theory so I would be interested to see the write-up if anything comes of the analysis by Scabs.

  • I agree with homedoggy it's a political fix , why we have our president. Some of that analytical mumbo jumbo. can't spell to much time on river. Chasing that varmint rabbit some folks talk about on here. It was delicious! :# >:)

  • I could start with an easily analyzable game and a subset of data. I came up with the idea while playing freecell. Maybe just a dump of about 10,000 games with the 25th, 50th, and 75th percentiles along with the top value for all the performance metrics you track. My idea is to represent each valid game configuration as a node and each legal move as an edge.
    I can then quantify difficulty using standard graph algorithms. Example: what is the expected length of a random walk starting at the initial game configuration and terminating at the victory state. The analysis I imagine should be efficiently computable because there are relatively few legal moves, as long as the game is non-adversarial and deterministic. For games with reshuffles I could get expected values for many of the same quantities using a Markov-chain Monte Carlo algorithm, but this might be beyond the scope of what I need to do.
    If you do not want to share your source code maybe you could send me a link to a web aplet that inputs a seed and outputs a formated file that represents the game configuration? I could access it using python and parse it into a format I can use. I was thinking of crawling your site and using image recognition to pull the configs but that seems like over kill.
    I have another project in the works right now so its not like there is a big rush to do any of this. Think it over, and if this seems like it is worth your time post some links here for me to look at and when I am done I will post my source code on github and link to it from the forum.

  • This should work in principle, and be practicable for games that have limited legal moves. Scorpion and pyramid come to mind. I’m not so sure about freecell, where there are a minimum of eight legal opening moves (not counting trivial variations) and the number of subsequent legal moves may increase (although not indefinitely, of course). However, it might still be doable in reasonable time, especially with the speed of modern processors.

    Good luck in your endevors.

  • The great thing about using graph algorithms is that you don't have to enumerate every possible path. I will work only with quantities built off shortest paths and this will keep the sample space small.

  • Gerald64Gerald64 REGISTERED
    edited February 2018 107.129.116.44

    Scabs, when you use that crawler , crawl up under the rock

  • Winner of this round is a tie... only because i dont know what a crawler is and if it were alive why would it craw under a rock ????

  • rewind I was refering to scab to crawl under a rock, accutally he got what he wanted as we reply to his mumbo jumbo he speaks, Only crawler I know about is a night crawler which is and earth worm , in technical talk, is what he has done to get us to comment on his post he is the bird we are the worms, :o :'(

  • Well i guess this could be BAD because the early bird allway's gets the worm...

  • gonna get that bird as well as that rasically rabbit

  • daviddavid REGISTERED, ADMINISTRATORS

    @Gerald64 Unnecessary rudeness only adds noise. Please don't comment if you don't have anything substantial to add.

  • Seriuosly. You guys must have picked on the nerdy kids in school. I'll try to keep to one syllable words from now on.

  • Scabs, I think your project is fascinating, and I hope I get to see it someday. It's unfortunate that there are people here who hate things they don't understand.

  • ScabsScabs REGISTERED
    edited February 2018 68.41.53.231

    Gerald64, a crawler is a program that autonomously accesses websites in order to collect information either from the sites themselves or the structure of their connections.

  • daviddavid REGISTERED, ADMINISTRATORS

    @Scabs: What you are describing sounds a lot like a solver. I've poked around some of these before (fc-solve is a Freecell solver I've used). Do you think "number of moves" to complete a game is a good difficulty metric (that's effectively what counting nodes while walking the graph gives you)? I kind of think there's something else to it. Like how many possibilities there are vs how many possibilities produce win conditions. And how deep in the graph you have to go before the real solution gets bottlenecked.

    I'd like to see something that rates new games' difficulties. The best we can do now is look at the statistical data for each game and rate it that way—and even then there's a lot of factors and we really haven't come up with one that is both easy to compute and gives good data. That requires that multiple people play the game first.

    maybe you could send me a link to a web aplet that inputs a seed and outputs a formated file that represents the game configuration

    The problem with that is that the games are all written in Javascript and run in your browser (including the shuffle and dealing code). The backend that stores the scores and loads high score tables is not written in Javascript, so to add an endpoint that outputs dealt states we'd have to shell out to node and I'm not particularly keen on that.

  • all this technical talk is making me excited....hehehehehehehehe

  • @Gerald64... Google "website crawler". In laymans terms it is a program that searches a site for information and reports back so that data can be analyzed...possibly used to create statistics. In respect to this conversation (at least I think in what little I have read) the crawler would gather information on games played, how many moves, time, scores and a determined difficulty rating(?). It would then pass this information on to another program to calculate your performance level.

    There are many of us who would probably not be interested in this info but I understand why others might be. Having this crawler would not affect the game play of us not so serious players...you have nothing to worry about.

  • Ooops...Sorry Scabs...I didn't realize that you had already explained what a crawler is...I guess that I should read ahead before I respond.

  • I apologize I lost my my computer for DUMMY'S I was just running off at the mouth and keyboard, want happen again. :'(

  • My idea is to collect many graph metrics (things like shortest paths to victory, path lengths from other leaf nodes to victory, random walk expectations, presence of a bridge edge on the path to the victory node etc) and then do some kind of regression algorithm on the different performance metrics.
    As a note: the expected length of a random walk would be a way of estimating the ratio of possible moves closer to the victory condition relative to moves further from the victory condition without explicitly enumerating every possible path. The precision of the estimate should scale proportional to 1/sqrt(n_random_walks) by the generalized law of large numbers. I doubt I need that much precision so it shouldn't take too long to compute.
    After doing some feature selection that penalizes different factors based on their computational complexity I could choose a model that balances compute time with predictive power.
    I think this is a neatly constrained problem that will show off my graph theoretic and machine learning skills, if I can just pull the data I need without having to reverse engineer the web code, or learn how to do image recognition in tensor flow for card configs. I just need a text box where I can type the seed # and hit a button and in return get a plain text page that encodes the card config, and a link where I can get a plain text table of some subset of the leader board data. Writing a script to scrape the data from that should be trivial. Otherwise a csv file with a data set would be easier for everyone. I don't know java or html that well, I am more interested in the math parts of coding.

Leave a Comment

BoldItalicStrikethroughOrdered listUnordered list
Emoji
Attach file
Attach image
Align leftAlign centerAlign rightToggle HTML viewToggle full pageToggle lights
Drop image/file
Home Feature RequestsComment As ...