Imp-training

I am myself interested in getting an A.I. thud player up and running and was wondering what software you are using and how u got it? I couldn't find your question amongst the discworld stuff!

Making training imps to become aware is fairly hard, they tend to become aware of lots of things that we instantly can dismiss as unimportant.

This is going about a mile over my head: someone help?!

ohly problem with training imps is that they may become too aware and start linking up their evil A.I minds around the entire globe and build a giant robot army and launch nulcear missles to destroy the human race. i get this problem alot.

<--evil robot

I've made it in Flash. Not the fastest imp-environment but the one I'm most used to at the moment . The main problem making it fast enough is to limit the number of moves it test without making it dumb. The trolls are nice: only eight and with a very limited number of possible moves. The dwarfs make more trouble, as allways . The main algorithm I intend to use is called min-max algorithm. It is used a lot in board games.

So it is important to not let the playing imps link their mind through L-space. If they become to nasty, we'll just push them over the edge and hope they start playing Thud with A-Tuin. They will probably die before A-Tuin make his first move

I have on the to-do list, the task of publishing a spec for people who want to teach imps and have them compete on the server. THAT would be sexy Imp vs imp (aka bot vs bot) competitions! People never needing to hunt for an opponent because there are always imps online!

The most obvious requirement is to have it very obvious that an imp is an imp - maybe a requirement that the name begins with "bot" or something. This way, it'll automatically be placed in a different set of ranking tables and such. People deliberately trying to pass imps as real users probably need hefty condemnation: deletion of accounts, suspension or perm-banning from the game, removal from the league tables, etc.

Nextmost is that it be able to deal with a decent subset of the THUD protocol - for that, I'll release the spec, then try to write either a full client or at least an API in all major languages like C, Java, PHP and suchlike. Then documentation is required for each of course...

I'd have done this already, except that I need to totally rewrite the MOVE command syntax to be able to deal with optional takes and Koom Valley rules. Since that's a relatively significant command in the game, release of the spec is waiting until I've figured that one out.

But that should all make it a lot easier for people to train imps to communicate safely through L-space. Where "safely" is a relative term of course, used in a sense that might be used by Leonard of Quirm.

[I was VERY complimented recently, on being compared to de Quirm :D]

wow! thats well cool. I wish i was as quality at programming and the like as you guys. your crazy linguo sounds klatchian to me.

i have been likened to the librarian. I don't know whether to take that as a compliment or an insult...

If you ever meet the librarian, remember two things: don't mention your doubt, and don't call him a monkey!

My vote goes to (imp) in front of the imp-players name. I like to keep the discworld feel of the game .

About the Koom Valley moves, I've put much of the move logic inside the classes for the pieces, so I intend to populate the board with Koom Valley dwarfs, trolls and stone when that is played (only made the pieces for the normal game so far).

I've made invisible squares (actually only zeros in the array) to put where there are no squares on the board, and yesterday I got an idea. If I put invisible squares all around the board (i.e. index 0 and index 16) I can drop the index test and just check if it tries to step on an ivisilbe square (which I have to do anyway since the board isn't square). Don't know how you do it, but if it is something similar, dropping the index test should make the AI faster.

I do too - but not where it obcures the intuitiveness of the interface. I considered "imp" when I was writing the post, but felt that "Imp" isn't a very obvious or intuitive indication that the alt is a bot. Does it mean imp (and if so, is that a rank of player, or a clan name, or...) or is it short for imperial, or imperative, or imperfect, or...

A new player coming to the game and seeing a user "[bot]playmate" is far more likely to understand that this is an automated player than seeing "[imp]playmate". They're less likely to become upset when speaking to a roomful of bots.

Yes, I changed from bot_playmate/imp_playmate: the brackets make it much clearer.

This could be improved by showing computer-screen icons by the names of bots, and face-icons by the names of real players.

I'm not convinced that "[bot]" is the best prefix to use, though: it's definitely not perfect, and I'm interested in other suggestions: NPC? Auto? They need to be short, and yet clear in meaning. Preferably even to people who's first language isn't English, since a lot (most) of our player are from outside the UK/US/AU zone.

I'm just confident that it's much more likely to be widely understood by new users than "imp".

I'll probably make it so that the client displays a message letting the user know it's an automated client, too, when the bot speaks or challenges them. Maybe make that a requirement for clients.

In PHP on the server, I do store the board in that way, but since I want to be able to return a unique error type for "off the board", I don't use it for bounds checking. You still need to rectangle-bounds-check it to make sure they don't place anything outside the bounding rectangle of the game (index -1 or index 17), so adding four more tests isn't hard.

The check for being on the board is pretty fast anyway: here's the version form the client:

  public boolean isBoardSquare(int x, int y) {
    return ((x > 0) && (y > 0) && (x < 16) && (y < 16)
      && (x+y > 5) && (x+y < 26) && (x-y < 10) && (y-x < 10));
  }

Note only the four tests on the second line could be omitted if objects were used for the board edges.

Comparing that to the rest of the move/capture validation below, that's hardly a significant overhead! (for regular Thud, not Koom Valley, I'm afraid).

Note that this code doesn't even include a method for allowing the user to select which dwarfs he wants to take, yet.

  private boolean isValidCapture(BoardPiece bp, Point p) {
    if (!isBoardSquare(p)) {
      return false;
    }
    BoardPiece target = getServerPiece(p);
    if (bp.getType() == BoardPiece.troll) {
      // Trolls can't land on things.
      if (target!=null) {
        return false;
      }
      // Trolls must land BY dwarves.
      boolean cannotTake=true;
      for(int x = -1; x < 2; x++) {
        for(int y = -1; y < 2; y++) {
          target = getServerPiece(p.x + x, p.y + y);
          if ((target != null) && (target.getType() == BoardPiece.dwarf)) {
            cannotTake = false;
          }
        }
      }
      if (cannotTake) {
        return false;
      }
      // Trolls must move in a straight line.
      // Trolls cannot move through things.
      ThudChat.debugToConsole("Checking line - taking with troll.");
      if (!isStraightLine(bp.getServerPoint(), p)) {
        return false;
      }
      // Trolls must move a bumpable distance.
      if (!isBumpable(bp, p)) {
        return false;
      }
    }
    else {
      // Dwarves must land on trolls.
      if ((target==null) || (target.getType() != BoardPiece.troll)) {
        return false;
      }
      // Dwarves must move in a straight line.
      // Dwarves cannot move through things.
      ThudChat.debugToConsole("Checking line - taking with dwarf.");
      if (!isStraightLine(bp.getServerPoint(), p)) {
        return false;
      }
      // Dwarves must move a bumpable distance.
      if (!isBumpable(bp, p)) {
        return false;
      }
    }
    return true;
  }

  private boolean isValidMove(BoardPiece bp, Point p) {
    if (!isBoardSquare(p)) {
      return false;
    }
    if (bp.getType() == BoardPiece.troll) {
      // Trolls must move one square or less.
      if ((Math.abs(bp.getServerPoint().x-p.x) > 1) || (Math.abs(bp.getServerPoint().y-p.y) > 1)) {
        ThudChat.debugToConsole("Failed to move... big troll move.");
        return false;
      }
      // Trolls can't move onto things.
      if (getServerPiece(p) != null) {
        ThudChat.debugToConsole("Failed to move... trolls cant stomp.");
        return false;
      }
    }
    else {
      // Dwarves must move in a straight line.
      // Dwarves cannot move through things.
      ThudChat.debugToConsole("Checking line - moving dwarf.");
      if (!isStraightLine(bp.getServerPoint(), p)) {
        ThudChat.debugToConsole("Failed to move... dwarves must walk straight.");
        return false;
      }
    }
    return true;
  }

  // Note bug: Trolls can bump one space further than they should.
  // Won't bother fixing this just yet, since I need to be able to test
  // wrong moves against the server.
  public boolean isBumpable(BoardPiece bp, Point p) {
    Point q = bp.getServerPoint();
    BoardPiece testPiece;
    // Points are in a straight line, we trust. Or we wouldn't be here.
    ThudChat.debugToConsole("Trying to bump.");
    int xi = 1, yi = 1;
    if (p.x < q.x) xi = -1; if (p.x == q.x) xi = 0;
    if (p.y < q.y) yi = -1; if (p.y == q.y) yi = 0;
    // Note1: Beware double initialiser and incrementer.
    // Note2: Beware also, for we MUST check all the target squares.
    // Note3: Because of this, I end at q, rather than starting there.
    // Note4: Using 2q-p to give a position on the other side of q from p.
    for (int x = q.x+q.x-p.x+xi, y = q.y+q.y-p.y+yi ;  (x != q.x)&&(y != q.y);  x += xi, y += yi) {
      testPiece = getServerPiece(x,y);
      if ((testPiece == null)||(testPiece.getType()!=bp.getType())) {
        ThudChat.debugToConsole("Bump not long enough - gap at "+x+","+y+" from "+p.x+","+p.y+" to "+q.x+","+q.y);
        return false;
      }
    }
    return true;
  }

  // Checks for straight lines, and for blockages.
  public boolean isStraightLine(Point p, Point q) {
    // Drop out immediately if it's not a straight line.
    if ((p.x != q.x)
      && (p.y != q.y)
      && (Math.abs(p.x - q.x) != Math.abs(p.y - q.y))) {
    ThudChat.debugToConsole("Walked wonky, from "+p.x+","+p.y+" to "+q.x+","+q.y);
      return false;
    }
    // It's a straight line... so far. Loop along it for blockages.
    ThudChat.debugToConsole("Walked straight.");
    int xi = 1, yi = 1;
    if (p.x>q.x) xi=-1; if (p.x==q.x) xi=0;
    if (p.y>q.y) yi=-1; if (p.y==q.y) yi=0;
    // Note1: Beware double initialiser and incrementer.
    // Note2: Beware, for we must NOT check the target square.
    for (int x = p.x + xi, y = p.y + yi ;  (x != q.x) || (y != q.y) ;  x += xi, y += yi) {
      if (getServerPiece(x,y) != null) {
        ThudChat.debugToConsole("...but piece in the way, at "+x+","+y+" from "+p.x+","+p.y+" to "+q.x+","+q.y);
          return false;
      }
    }
    return true;
  }

I totally agree that when the server (or client) need to check that a player move is legal, the time used to do index check isn't a topic at all. I was thinking about when the AI need to test: can I move troll1 one square to the left, left and up, up, up and right, right, right and down, down, down and left, can I move troll2...

Even then I'm not sure how much time it would save, but with 8 trolls and 32 dwarfs, and looking a few moves ahead, it will be doing the test many times.
With the zeroes it could do something like:
switch (board[x][y]){
case 0: return false;
case 1: //whatever needs to be done when empy square
case dwarf: //whatever needs to be done when a dwarf occupy square
case troll: //whatever needs to be done when a dwarf occupy square
case stone: return false;
}

About the trolls optional dwarf captures, I would suggest: On the server side, add a array parameter for dwarf captures (or a comma separated string that can be split into an array). I think it is the clients responsibility to say which dwarfs it want to capture. On the client side, test if the user is pressing a key (for instance control) when doing the move. If not, capture all dwarfes possible. If the user press control, do some interface thingy to let the user choose which dwarfs to capture (for instance highlight which dwarfs the troll might capture and let the user deselect the ones he doesn't want to capture, and then press some ok-button).
(I haven't tried your client yet, so if the suggestion doesn't make sense, I'll appologize in advance )

And all this time I thought that i was the only one to think of building an impbox. Well, not really, but it is a good idea.

I would be a lot more worried about squirrels on nibbled acorns if I were you !!