#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2003
    Location
    Greece
    Posts
    63
    Rep Power
    12

    "virtual intelligence!"


    I'll make it clear.

    In a game like Dominoes or Tic-Tak-Toe , or Bridge and Chess or even a simulator , a Rpg or an adventure etc. how does the computer "MAKE ITS MOVE".

    I mean the Computer just "knows" a set (list) of allowed possible future moves to make but how is the BEST of them choosen?(in the long term its even more difficult)



    i think of it like an example of a maze. when we were children we tryed to find the exit by drawing along the path wich was "nearer in sight" and if it was wrong we draw backwards till the first "crossing" and draw the other way along.


    Q: The "game" should search in the "LIST OF ALLOWED MOVES" for ALL the solutions and store them in ....? another list? and then create anoter LIST OF ALLOWED MOVES (for each possible move?) and how is the list "UPDATED" after each possible move and after each HUMAN move? (deleting it each time and re-creating it is ofcourse programming failure)?

    So there is a LIST OF LISTS and the smaller which finds a BETTER GOAL is the best? (if you cant win just make a DRAW)

    PS: sorry my english is not so good and the subject is messing me.
    No sign
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Oct 2000
    Location
    Back in the real world.
    Posts
    5,966
    Rep Power
    191
    (deleting it each time and re-creating it is ofcourse programming failure)?
    I think it comes down to making a list of all possible moves and weighting them for probability of success. You would probably make a hierarchical structure (linked list -> binary tree) and drop the first level in the hierarchy and the branch that did not apply on each move. But this is just a guess.

    Im not into AI programming (yet), but i found the programming articles and tutorials on this site to be great. On the first glance, they also offer some (good?) articles on AI programming and different algorithms:

    http://www.gamedev.net/reference/list.asp?categoryid=18

    hope this helps....
    M.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2003
    Location
    Greece
    Posts
    63
    Rep Power
    12
    since the readings are quite many but noone anwsers i write my code down ....
    well its not at any means correct and since i use C++ and its a general algorithm i think its the correct forum, else im sorry in advance and the mod please (if possible) move the threat to the C forum!


    class Node
    {
    int Data;
    Node *nextmove;
    List Listofmoves;
    public :
    Node () {Data=0; nextmove=0; }
    Node (int d , Node *n) {Data=d, nextmove=n; }
    ~Node () {}
    friend class List;
    friend List move(List);
    };

    class List
    {
    Node *Head;
    Node *Last;
    Node *Now;
    public :
    List () ;
    ~List () ;
    List & append(int);
    List & next();
    int find_move(List);
    friend List move (List);
    friend class Node;
    };

    List :: List ()
    { Head=0; Last=0; Now=0;}

    List :: ~List () {}

    List & List :: append(int i)
    {
    if (Head==0)
    {
    Head = new Node(i,Last);
    Last= Head;
    }
    else
    {
    Last = new Node(i,Last);
    }
    return *this;
    }

    List & List :: next ()
    { if ( Now !=0 ) Now = Now->nextmove; return *this; }

    int List :: find_move(List l)
    { l.next(); return l.Now->Data; }


    List move (List listl)
    {
    if (listl.Last!=0)
    move(listl.append(listl.find_move(listl.Last.Listofmoves)));
    else
    return(listl.Push_in_list_of_goaling_Lists);
    }

    All the "check" is done in the recursive function MOVE.

    I want to ADD to A List OF POSSIBLE MOVES the element of a List OF NEXT MOVES from the LAST element OF THE List OF POSSIBLE MOVES.

    AT the end the output is stored in a 3rd List and then the List of the Lists that have the desired goal are check 1 by 1 for the best solution.

    any comment or idea appritieted.
    No sign
  6. #4
  7. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,646
    Rep Power
    4248
    I think I see what you're saying here. I actually used something slightly similar when I wrote a chess program a long time ago. The way I recall it, I had a board class that stored the position of all the pieces as well as a push down list for adding moves to it. I had a copy constructor so I could copy a board position. I would pass the current board position to the move() function. The move() function would loop through all the possible moves a side could make and generate the new board positions. It would recursively call itself for each one of these positions and pass the new board position. I did this for a depth of 2, 4 or 6 (depending on the difficulty setting), so that it would generate moves for both sides. When the function recursed to the max depth, I pushed the final board class structure into the linked list (not the intermediate positions, since they're stored as part of the push list in the board class structure). Then I would evaluate the final positions from the list and decide which was the best position to get to. Then I would use that push list that was part of the board structure and make that move.

    Here's my pseudo-C++ code for that. Hope this helps
    Code:
    class Board() {
       public:
          char positions[80];
          Board() { movelist = NULL; }
          Board(const board& p); // Copy constructor
          Node *movelist;
          AddMove( Move *move);
          RemoveMove(); // Pops the last move
    };
    
    void make_move(int side, Board b, int depth);
    
    int main(void) {
    ..
    ...
    Board board;
    
    board.Initialize();
    
      while (! done) {
        ...
         depth = 0;
         clear_postion_stack();
         make_move(computer_side, board, depth++);
    
         // Now evaluate the position stack to find best board position
         // and make the move based on first item in Board.movelist
      }
    }
    
    void make_move(int size, Board b, int depth) {
     Board temp = b;
     Move *move;
     MoveList *movelist;
    
     // If max depth is reached, push this board class into a stack
     if (depth == max_depth) {
         push_position_stack(b);
         return;
     }
     
     for (int i=1; i < 80; i++)
        if temp.positions[i] { // if something is there at this position
           gen_move(side, temp, i, movelist); // Generate all moves for this piece
          // Now go through all the moves for this piece
           for (int j=0; j < movelist->count; j++) {
             move = movelist[j];
             // Add this move to the board
             temp.AddMove(move);
             // Recurse into make move for the other side)
             make_move(1 - side , b, depth++);
             // Remove the last move and evaluate next possible move
             temp.RemoveMove()
          }
    }
    Last edited by Scorpions4ever; February 14th, 2003 at 01:45 PM.
  8. #5
  9. jasondoucette.com
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Location
    Canada
    Posts
    378
    Rep Power
    12
    I am not 100% sure what the original question was, but from my understanding of it, here is my answer from my own experience with AI programming:

    - AI engines choose their move by assigning a value to each move. This value for each move needs no other meaning other than a move that is better than another move should have a higher value. The computer picks the move with the highest value.

    How does it value each move?

    The way the computer assigns values to its moves is with a game tree. It takes the current position, and makes all possible moves on it, and then makes all possible moves on each of these positions, and so on (via recursion) until it runs out of time. At the end of this game tree is all possible positions the computer has analyzed. Let's say it has enough time to compute 8 ply ahead, then the positions at the end of the tree are all possible positions after 4 moves for each side. The computer gives a value to all of these positions. Assuming both sides play perfectly, it picks the original move that results in the highest value of these ending positions.

    Here is a great page that better explains my rather poor attempt:
    http://www.xs4all.nl/~verhelst/chess/search.html

    For the other things that have been mentioned in this thread:

    - For a chess engine, the best way to create all of these positions in a game tree, is to move as less memory as possible. This means you should not copy an entire position so that you can make a move on it. Store only the information that you need to make and un-make the move. This means more processing (i.e. more coding), but it means less memory is being moved, so it is faster.

IMN logo majestic logo threadwatch logo seochat tools logo