An unbeatable AI
February 11, 2002 09:53 PM
In a chess ai, is it best to make an algorithm the searches through a ''moves'' tree to see which move will provide the most favorable outcome. Then if the favorable outcomes are the same then the shortest to a win. Then if a player moves, it makes its descisions based on what it should do next by looking at favorable outcomes. Is this possible? Or is it too slow?
---START GEEK CODE BLOCK---GCS/M/S dpu s:+ a---- C++ UL(+) P(++) L+(+) E--- W++ N+ o K w(--) !O !M !V PS- PE+Y+ PGP+ t 5 X-- R tv+ b+ DI+ D G e* h! r-- !x ---END GEEK CODE BLOCK---
122
February 11, 2002 10:03 PM
My guess would be that chess AI brances off into different move
combinations from a table of decisions based from good chess
players.
Sort of like scripted AI, I suppose.
Course, you might be right, but I believe that would take
forever.
-Hyatus
"da da da"
combinations from a table of decisions based from good chess
players.
Sort of like scripted AI, I suppose.
Course, you might be right, but I believe that would take
forever.
-Hyatus
"da da da"
February 11, 2002 10:05 PM
I believe that this is called the "Min Max" algo for chess. The computer will search through every possible move a few levels deep, and score each move by what will be most favorable for the AI, and less for the other side. Because each "level" of the tree grows exponentially, it can be very slow. However, by limiting the how many levels the computer searches, it is _very_ do-able.
124
February 12, 2002 03:04 AM
...the hard part of course beging how to determine what is "favorable" and what isn''t.
134
February 12, 2002 04:24 AM
I think the term is that a game has been ''solved''. Like, naughts and crosses is ''solved'' because it is possible for the person who goes first to never lose.
Chess has not been solved yet, but I would guess that plenty of people are trying to do it.
Trying is the first step towards failure.
Chess has not been solved yet, but I would guess that plenty of people are trying to do it.
Trying is the first step towards failure.
Trying is the first step towards failure.
122
February 12, 2002 11:07 AM
Actually, in chess its possible to always win... Provided you have a massive (and complete) data tree and move first.
February 12, 2002 11:28 PM
Tricron2, do you even know anything about chess?
Going first or second has nothing to do with winning or
losing.
Order of turn determines what strategy you use.
White, which always goes first, is the aggressor and must
attack with skill and cunning.
Black, which always goes second, is the defender and must
trap the other.
Going first or second has nothing to do with winning or
losing.
Order of turn determines what strategy you use.
White, which always goes first, is the aggressor and must
attack with skill and cunning.
Black, which always goes second, is the defender and must
trap the other.
124
February 12, 2002 11:29 PM
Tricron, that is just not true at all. If someone has claimed this it is a joke. (maybe you are joking?)
The number of possible board positions in the game of chess is greater than the number of subatomic particles in the universe. It is possible that the game will never be solved in the lifetime of the universe.
Now maybe your statement was just a joke... you are surmising that given a "complete" game tree then the player who goes first could always win. This is not necessarily true, remember you can play to a DRAW in chess! It''s like Tic-Tac-Toe, going first does not give you an advantage, even if you have a tree of all possible moves, the opponent can still force a draw. No one knows whether this is true for chess or not.
The number of possible board positions in the game of chess is greater than the number of subatomic particles in the universe. It is possible that the game will never be solved in the lifetime of the universe.
Now maybe your statement was just a joke... you are surmising that given a "complete" game tree then the player who goes first could always win. This is not necessarily true, remember you can play to a DRAW in chess! It''s like Tic-Tac-Toe, going first does not give you an advantage, even if you have a tree of all possible moves, the opponent can still force a draw. No one knows whether this is true for chess or not.
February 13, 2002 12:12 AM
Just some more thoughts about the MIN MAX algo:
Regarding how to determine the "favorablity" of the initial move, why not simply recurse through every possible move for perhaps about three levels? Then add a score for each favorable thing (IE, taking a piece, or putting the king in check), and subtract for anything unfavorable (losing a piece, or being put in check). The initial move (top level of the recursion) with the highest score attached to it would be the move chosen (because it has the most potential for becoming favorable). Even if a move may lead to a piece being lost, it would be ultimately considered because of the other possibilities that branch from it.
This is hardly original, but I hope it helps some.
Regarding how to determine the "favorablity" of the initial move, why not simply recurse through every possible move for perhaps about three levels? Then add a score for each favorable thing (IE, taking a piece, or putting the king in check), and subtract for anything unfavorable (losing a piece, or being put in check). The initial move (top level of the recursion) with the highest score attached to it would be the move chosen (because it has the most potential for becoming favorable). Even if a move may lead to a piece being lost, it would be ultimately considered because of the other possibilities that branch from it.
This is hardly original, but I hope it helps some.
122
February 13, 2002 03:33 AM
re: What is favourable ?
I wrote a draughts (checkers) game once and I had this same problem. So for each move I would award a score based on good things happening, for example,
1) Reaching the side or end of the board - can''t be taken (need to be hopped over).
2) Reaching the end of the board - get made into a king
3) Taking an opponents piece
etc
However, this was WRONG. In the end, the correct algorythm, was to just award points for taking a piece, and deduct points for losing a piece. This is because items 1 & 2 above, automatically figure, because if you are at the edge of the board you will lose less pieces, and if you are a king you will gnerally take more pieces.
I can not remember if the score scale downwards the further up the tree the calculation got. I imagine they did because those moves were less likely to happen, and so should not have had the same weight as the first move.
Not sure if any of this makes sense, let me know if it comes over as gibberish.
I wrote a draughts (checkers) game once and I had this same problem. So for each move I would award a score based on good things happening, for example,
1) Reaching the side or end of the board - can''t be taken (need to be hopped over).
2) Reaching the end of the board - get made into a king
3) Taking an opponents piece
etc
However, this was WRONG. In the end, the correct algorythm, was to just award points for taking a piece, and deduct points for losing a piece. This is because items 1 & 2 above, automatically figure, because if you are at the edge of the board you will lose less pieces, and if you are a king you will gnerally take more pieces.
I can not remember if the score scale downwards the further up the tree the calculation got. I imagine they did because those moves were less likely to happen, and so should not have had the same weight as the first move.
Not sure if any of this makes sense, let me know if it comes over as gibberish.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
