Loading ...
Sorry, an error occurred while loading the content.

Re: [gamedesign-l] neural net approach

Expand Messages
  • James Margaris
    ... From: Brandon J. Van Every [clip] ... designing ... system. The history of the system is akin to player skill. If in our
    Message 1 of 57 , Jul 1, 2001
    • 0 Attachment
      ----- Original Message -----
      From: "Brandon J. Van Every" <vanevery@...>

      [clip]

      > > So, what I an suggesting here is something that takes the past
      > > into account a bit more than the current proposals.
      >
      > Speak for your own proposal. Your basic flaw is you have not been
      designing
      > for systemic drift and latency. You've been refusing to accept that
      > systemic drift actually exists and insisting that scores actually measure
      > skills. Scores don't measure skill: they measure the history of the
      system.

      The history of the system is akin to player skill. If in our system player A
      has always lost to player B, B is better than A. This is a fair statement
      most of the time.

      If you don't beleive that your scores measure skill in some fashion, what do
      you beleive exactly?

      > > I'm not sure exactly how the system
      > > would work, (actually I am later in the post) but essentially when it
      got
      > > new results it would assume that the old results were flawed and
      > > recalculate everyone who came in contact with the flawed results.
      >
      > Well, try just brutally averaging incorrect scores as your starting point.
      > Let me know if you ever think of anything that's better or more fair.

      Ok, I'm letting you know. Last time. I notice you *never* respond directly
      to to my complaints about this system.

      Let us take the following scenario:

      I beat Tiger Woods.

      Now, under your system, Tiger Woods and I are the same? Okay........now me
      beating Tiger Woods is pretty unlikely, but look at the US Open. Nobodies
      won. Are they as good as Tiger Woods now?

      Was Mike Tyson the same as Buster Douglas when he was beaten? Hell no, Tyson
      was still way better.

      What happens if I'm playing and my game bugs out? I lose so now I'm no
      better than my opponent?

      This makes ZERO sense. The thing you seem to be missing here is that if
      someone is ranked higher is doesn't mean they should win EVERY time. If I am
      better than you, I can still lose to you. That doesn't mean that our
      rankings were incorrect...people lose. I may consitently win 7/10 times we
      play. So should our scores diverge, meet, diverge again, meet again? Why?
      Nothing is changing. Our skill is not changing, neither of us is getting any
      better or worse. Essentially in your system you are only as good or bad as
      your last game...foolishness.

      Your paradigm flies in the face of common sense. Gee, I watched a Baseball
      game where Barry Bonds hit ZERO home runs and John Olerud hit ONE. I guess
      Bonds and Olderud are the same when it comes to hitting home runs...?

      Say we have A and B.
      A beats B
      A beats B
      A beats B
      A beats B
      .... (repeat 1 billion times
      B beats A ONCE
      B and A play at the same skill level. This is what I mean by following
      axioms. A *very* basic axiom would state that if I beat you a full one
      billion times in row, and then you beat me once, I am still *WAY WAY* better
      than you.''

      Now say that our skill levels are such that I will normally beat you at a
      billion to one odds. So say we go a nice even 1 billion wins, loss, 1
      billion wins, loss, etc etc etc. Over that period we are both playing at a
      predictable, consitent pace, yet my ranking goes crazy. Now say we have a
      parallel pair of C and D who started at the same place as A and B did, and C
      also beats D at 1 billion to 1. It is a reasonable axiom that we should
      expect A and C to be about equal, and B and D to be equal. This is certainly
      what the player would expect, since A and C are performing identically, as
      are B and D.

      Yet, under your system if we phase shift these, things get totally out of
      wack. We may find that D is much lower than B at some points, and at others
      C is much higher than A...yet there is *no* difference between the play of A
      and C, or the play of B and D.

      This is what I mean by fullfilling basic axioms. I haven't seen any proof
      that your system models perfection any better than mine, and furthermore
      your system totally defies player expectations and common sense.

      Under your logic, the ranking that A built up by beating B ONE BILLION times
      was a "lie" which we must correct.

      Let's put this another way:

      If you assume that the rankings are going to be really wrong no matter what,
      you're done. You don't beleive rankings exist. Fair enough. don't bother
      then.

      You logic is:
      I assume rankings are wrong
      I correct them
      now they are...? Still wrong? Less wrong? Right?


      [clip]
      > >
      > > A beats B beats C beats A a bunch of times. They are all about equals.
      > >
      > > A beats D 10 times in a row.
      > >
      > > At this point we say "hey, wait a minute, D was ranked too high and A
      was
      > > ranked too low. A should have been ranked at 70, and D at 30." So now,
      we
      > > say "hey, B and C were about even with A, they should also be at 70."
      Then
      > > we think "everyone who lost to D is clearly worse than we thought, and
      > > everyone who beat D proved less than we thought..." So we
      > > back-propagate the changes.
      >
      > Why do you assume A, B, and C can beat D, when only A beat D?


      Once again, your over-literal ranking is pointless. In "real life" (tm) you
      aren't going to be able to have every player play every other player. Notice
      that *your* system ranks people under this "fallacy" as well. If you do the
      math under your system, A is ahead of B and C, who are ahead of D.

      In your system, everyone starts equal. First game *ever* played, one person
      beats another. Now the winner is the highest ranking person in the world,
      the loser the lowest ranking. You just assumed that the winner should be
      able to beat everyone else. You may correct that assumption later, while at
      the same time making many more assumptions...your system makes the same
      assumption as mine.

      In real life the players aren't going to play one universe wide super
      tourney, then not play any more until the next super tourney. You *have* to
      make reasonable assumptions. It is *reasonable* to assume that if A beats B
      and B beats C, A beats C. It depends somewhat on your game, and on the
      frequency that A beats B and B beats C, but my system takes that frequency
      into account. (If A beats B just a bit, and B beats C just a bit, nothing
      much happens)

      In real life we make these assumptions *all* the time. If I arm wrestle some
      guy and lose badly, and *he* arm wrestles someone else and loses badly, I
      can be *pretty* certain I would lose to that guy. Inference. Deduction. Call
      it what you will. Yes, depending on the game, cyclical beating can occur,
      but what game are you creating, rock paper scissors?

      As far as your Dojo example, find me a guy who can kick your ass, then find
      me a guy who can kick his ass. If you and the second guy fight, I bet on
      him...and that is the smart thing to do. This is undeniably true.

      Hey, maybe I could beat Mike Tyson at boxing, and Pete Sampras at tennis,
      with my wacky stylings. Then again, maybe Tyson would punch me in the face,
      lights out...

      Once again, this is a reasonable assumption, we make it in real life all the
      time, there is ample evidence that it is reasonable, nearly all of the time.
      Once again, unless there is an overriding rock paper scissors aspect to your
      game, this isn't a problem.

      If your point is just going to be that you can't rank unless everyone plays
      a super-tourney, then hibernates until the next one, why bother? I guess you
      don't beleive that Duke can beat me at my friends at basketball unless you
      see it with your own eyes? Because our "poor shooting/dribbling/passing"
      style is too much for them?

      In the
      > martial arts we call this "Dojo Syndrome." It's the belief that you'll be
      > good on the street or against any other style or fighter simply because
      > whatever you're doing works in the dojo.

      No, that is not the same at all. You have TOTALLY missed the point. In this
      example above, you are talking about an isolated group with no outside
      contact.

      Your example is just wrong. To make it right, consider this:

      Two rival dojos.
      A guy in your dojo can beat the best guy in another dojo.
      The guy in your dojo is not the best guy in your dojo, you can beat him.
      Assumption: You can beat the best guy from the other dojo.

      No, this is not ALWAYS true. Maybe your styles match up well. But, the worse
      you beat him, and he beats the other guy, the safer the assumption becomes.
      If you can trash him, and he can whip the other guy in a few seconds, all
      money would be on your in an inter-dojo matchup.

      What you are missing here is the connection. If you are totally isolated,
      you don't know much about your skill compared to the outside world, but that
      is *not* what we are talking about. We are saying that A beats B, B beats C,
      so A beats C. Your example was A beats B, A beats C, so A beats D. (Which in
      the absence of *any* other info, is still more reasonable to think than the
      opposite. And both our systems make this assumption as well. But, as I noted
      before, this can only arise from isolation, in which place our rankings
      don't really matter too much anyway since those players don't interact. It
      is a good idea, though, to come up with systems that quickly correct the
      problem once the isolation ends)

      > If you're a systemic purist you
      > don't reward people for beating people they actually haven't fought. If
      you
      > follow boxing matches, you don't assume A beat B beat C beat D beat E
      means
      > that A will beat E. Hierarchy is one possibility, cyclicity is another
      > possibility.

      Of course you assume that. Announcers assume that. Trainers assume that.
      Boxers assume that. If A just barely beat B, who just scraped by, etc etc,
      and they all have about even records, we might assume it would be a tossup.
      Under my system you wouldn't get much change there. (The neural net system,
      that is) But if in one link, say C really whips D, it is reasonable to
      assume that A and B can also beat D. We *do* reward people for beating
      people they haven't fought. That is why the New York Yankees can be ranked
      the #1 baseball team, even though they never actually beat the Iowa
      Cornballers, a team of retired farmhands.

      Let me put it another way: Why can't I be the co-boxing heavyweight champ?
      (If I weighed that much?) After all, no current or former champ has every
      beaten me. You never know till you have the fight, right?

      Here is another point:
      Supposition A: You can't guess the result of any match, it *must* be played
      Supposition B: Not all matches can be played
      C: Your ranking works how, exactly? *Your* ranking WILL rank people who have
      never played each other, and it MUST. This is a requirement. There is no way
      around that. Any real-world ranking system MUST rank people who have never
      directly met. Otherwise, instead of saying "Pete Sampras is #1" we would
      have to say "Well, Pete Sampras beat this guy and that guy, but hey, he
      never played against James, so who knows? Better not make any rash
      predictions about the outcome of a James-Pete tennis match. That would be
      *foolish*!!!


      [clip]

      > Wall Street back propagates all the time. Look what it does to currency
      > markets. Propagation does not equal solution, it can reverberate
      endlessly
      > and destructively.

      So, I make sure my system doesn't do that.

      [clip]

      > The purpose of neural net configuration is to predict outcomes. If your
      > neural net is incapable of predicting outcomes, then you've found a
      > complicated way of engineering something totally useless.

      It does predict outcomes. That is the point. Or rather, it predicts outcome
      percentages. Actually, depending on how you structured it exactly, it could
      do either, it would be the same in the end most likely.

      Look, it really is very simple.

      We have one hundred players. They start with 100 points. We assume that
      players should win in the ratio of their points. (So, 100:100 is 50% chance
      of winning)

      First match is played, A beats B, adjust neural net. (We want a limit on
      overtraining, so we need a learning co-efficient, but let's ignore it for
      now) To make the neural net 100% accurate, we lower B rating to 0. (We will
      limit them to 0-100 scale, it really doesn't matter) Now, our network is
      100% acurrate for the results so far.

      But now, B beats C. Golly, now what? Lower C to 0? No, that is still a 0:0
      ratio. Maybe we put C at 0 and B at 100 again? Nope, that doesn't minimize
      error over our test data, because now that A and B ratings are causing error
      again. (it shoud predicts that A beats B) So, how about A = 100, B = 1, C =
      0. That seems like it would minimize error pretty well. B beats C all the
      time, which is consistent with our data. A beats B at 100:1, which is not
      *quite* consitent but pretty damn close.

      Oh boy, now D beats A. Now what? Maybe A = 50, D = 100, B = 1, C = 0. (Just
      a guess at this point) Not *too* bad. Now B beats D!!! Erghh...now we let
      the math take over...

      [important aside]
      In a normal neural net, we would only correct for the result we just got. So
      if B beat D, we would correct the B and D values only, without regard to how
      it changed the error for the previous data sets. So what we are really doing
      is adjusting B and D, stepping back in time one match, adjusting that,
      stepping back, adjusting, etc etc. This approach has the advantages I
      described above with the quicker adjustment of related players. But really I
      would have to think about it a bit more.

      Another point: my model has no hidden layer. It has input and output. All
      the input nodes lead to the output node. For each connector, the points I
      have been referring to are the "weights." This is because we just want to
      look at rank and derive those the best we can. If we had a hidden layer it
      would probably work out that we would predict results between players much
      better. With a hidden layer instead of just a flat rank, we could actually
      handle a cyclical case, and accurately predict that A beats B beats C beats
      A. The problem with the hidden layer is that it has the intermediate
      weights, instead of just the point total, which would have to remain hidden
      since there would be many values and it would be hard as hell to explain
      what they meant. (Assuming we even knew for sure) The other problem is that
      a hidden layer would probably require more training to start functioning
      well, and our data would just trickle in a match at a time. It could be
      possible to run one without and one with and switch to the one with the
      hidden layer when it becomes more accurate overall.

      But, with a hidden layer you could ask "what is the chance I beat B" and get
      a more reliable answer. The downside is that you wouldn't have one "weight"
      you could spit out to the player.

      (I think, it's getting late)
      [end important aside]

      So, maybe the key question is what does this system do:

      Answer: It configures itself so that it *would* have predicted the test data
      we have so far as well as possible.

      Two more questions:
      #1: How accurate is it? Answer: We can measure that exactly. Probably
      accurate enough.
      #2: Assuming it is fairly accurate, how well does it work with new data?
      Answer: If you beleive that the present is connected to the past, it should
      work fairly well.

      Say I told you that I had a system that predicted the winner of past NBA
      games with 90% accuracy. Would you bet for or against my prediction the next
      time a game rolled around? (To be fair, I could have made the system based
      on a bizarre trend like last names or something, but we are ruling that out
      here. You have to *try* to get that sort of result, it won't pop up out of a
      good faith effort)

      Past success is good indicator of future success.

      Does anyone other than Brandon have any comments about this? Neural nets
      work well in real life, and the one I have proposed seems reasonable. (It
      could be improved with more thought and actual test data analysis, adding
      conditions, extra inputs, etc) But hey, I made a backgammon neural net that
      consistently beat me, that wasn't any better designed than this.

      > You've also hit
      > upon the technical reason why I don't thing AIs are ever going to be
      better
      > than human intelligence, even if those AIs are capable of pondering more
      > things at once as they make their decisions, and thus solving certain
      > limited problems more quickly. Nature itself has an inherent
      combinatorial
      > complication that defies analysis. At some point, you only know by doing.

      I don't want the AI to play the game! But even if I did, AI can beat 99.9%
      of chess players, and the *best* backgammon player in the world is a
      computer. Human players have actually changed their strategies to mimic the
      AI. (It was also a neural net, but far better than mine! Mine was good
      enough to beat beginner to low-intermediate though....)

      AI is *better* than human intelligence for doing certain things, specific
      things. We have ample proof of this. What I am proposing certainly isn't any
      more complicated than a lot of existing AI's. The programming is even pretty
      easy.


      > You could try to come up with heuristics for your neural net, based on
      > in-game behavior and not just empirical win/loss data. Maybe if you
      measure
      > all the resource productions and player movements, a neural net can notice
      a
      > stable pattern. Or maybe it can't. But if it can, and the pattern
      matches
      > a lot of win/loss behavior, you might be able to predict with more
      > confidence what *styles* can dominate a game. You'd stop worrying about
      > cyclicities of style if you get games where players are clearly using a
      > particular style.

      I don't think style would be a big issue, and a proper neural net could
      account for that anyway :) (Need a hidden layer!) You don't need any sort of
      designer idea of what different styles are. In fact, a clever person could
      probably analyze the hidden layer of a neural net and through some analysis
      get a good idea of how many different styles there are, and how they do
      against each other. What those actual styles would be, on the other hand,
      could not be ascertained.

      I think we agree that trying to measure anything other than win/loss is not
      a good idea.

      [clip]

      > But if you're going to use neural nets to solve your problems, you should
      > realize that neural nets converge to their *own* patterns. If they do.
      > There is no guarantee that it has to converge, let alone to the results
      you
      > wanted a priori.

      There is no guarantee. In fact, it is almost guaranteed not to work.
      Perfectly, that is. Oh well. Perfection is not our goal.

      [clip]

      > > As soon as we realize that
      > > some rankings we wrong, we adjust not only the 2 rankings in question
      but
      > > *everyone* else who came in contact with them.
      >
      > This is foolishness. As you contemplate it further, I'm sure you'll
      realize
      > why.

      I've comtemplated it, and it still makes sense. You can deal with cycles in
      the way I outlined above. You can further restrict the number of
      propagations if you want, but it is at most the number of matches played.
      (Or played between people with some connection) There are plenty of ways to
      deal with cycles. They aren't an issue. If computation time is a problem you
      cut it off somewhere, yay.

      Clearly, your progagation can't trigger more propagation. Well actually it
      can, as long as there is some limit. And there is.

      Essentially you do this:
      Make your change for that matchup.
      See how that screwed up everything else.
      Fix those.
      See what that screwed up.
      Fix those.
      Repeat until:
      Time is out.
      You are close enough.
      You can't do any better.

      Getting into the specifics of the exact training or correction method is
      pretty pointless. My question would be, is a general sense could a neural
      network do the job I am asking it to do. (Which, is to predict outcomes to
      good accuracy, however you measure that)

      If it helps, neural networks in general do good jobs, especially non-naive
      ones that have some hand-tuning by someone who understands the domain. But,
      neural networks don't do well predicting the stock market, for example. (In
      part because the stock market is largely based upon perception and
      psychology, which are not only very complicated but not used as inputs in
      the neural nets.)

      So, on a base level, is this something that could work for a neural network?
      I certainly think the answer is yes.

      James M
    • James Margaris
      ... From: Brandon J. Van Every [clip] ... over ... is ... more ... it ... I had a response to this written out, essentially
      Message 57 of 57 , Jul 2, 2001
      • 0 Attachment
        ----- Original Message -----
        From: "Brandon J. Van Every" <vanevery@...>


        [clip]

        > Why, because you want to live in the delusion that we have more control
        over
        > the situation than we actually do? You need to study Combinatorial Rank
        > more thoroughly. Then the light bulbs will start popping as to why this
        is
        > all social engineering. If you want to wrap your head around something
        more
        > empirical, go study currency markets. What's the "rank" of the dollar
        > today, James? What's the fundamental reason for it having that rank? Is
        it
        > the "skill" of the USA?

        I had a response to this written out, essentially pointing out that while
        the currency market "ranking" may not work that doesn't say much about
        ranking systems in general, especially when given plenty of real-world
        systems that do work. But I'm just going to leave it at that. I can't say
        anymore that isn't obvious to anyone who agrees with me already.

        Based on the concerns that people have expressed to me privately, I think it
        is best to wrap this thread up and move on.

        James M
      Your message has been successfully submitted and would be delivered to recipients shortly.