StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
14377892
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
6
CommunityOwnedDate
CreationDate
2013-01-17T11:18:18.123
FavoriteCount
0
LastActivityDate
2014-10-18T08:58:16.290
LastEditDate
2014-10-18T08:58:16.290
LastEditorUserId
173787
OwnerUserId
173787
ParentId
14365097
PostTypeId
2
Score
5
ViewCount
0
LastEditorDisplayName
text
Body
First you can check <a href="https://github.com/THeK3nger/Cobra-Draughts/blob/master/cobradraughts/core/DraughtsBrain.py" rel="nofollow">this piece of code</a> for a checkers AI that I wrote years ago. The interesting part is the last function (<code>alphabeta</code>). (It's in python but I think you can look at that like pseudocode). Obviously I cannot teach you all the alpha/beta theory cause it can be a little tricky, but maybe I can give you some practical tips. Evaluation Function This is one of the key points for a good min/max alpha/beta algorithm (and for any other informed search algorithm). Write a good heuristic function is the artistic part in AI development. You have to know well the game, talk with expert game player to understand which board features are important to answer the question: How good is this position for player X? You have already indicated some good features like mobility, stability and free corners. However note that the evaluation function has to be fast cause it will be called a lot of times. A basic evaluation function is <pre><code>H = f1 * w1 + f2 * w2 + ... + fn * wn </code></pre> where <code>f</code> is a feature score (for example the number of free corners) and <code>w</code> is a corresponding weight that say how much the feature f is important in the total score. There is only one way to find weights value: experience and experiments. ;) The Basic Algorithm Now you can start with the algorithm. The first step is understand game tree navigation. In my AI I've just used the principal board like a blackboard where the AI can try the moves. For example we start with board in a certain configuration B1. Step 1: get all the available moves. You have to find all the applicable moves to B1 for a given player. In my code this is done by <code>self.board.all_move(player)</code>. It returns a list of moves. Step 2: apply the move and start recursion. Assume that the function has returned three moves (M1, M2, M3). <ol> <li>Take the first moves M1 and apply it to obtain a new board configuration B11.</li> <li>Apply recursively the algorithm on the new configuration (find all the moves applicable in B11, apply them, recursion on the result, ...)</li> <li>Undo the move to restore the B1 configuration.</li> <li>Take the next moves M2 and apply it to obtain a new board configuration B12.</li> <li>And so on.</li> </ol> NOTE: The step 3 can be done only if all the moves are reversible. Otherwise you have to find another solution like allocate a new board for each moves. In code: <pre><code>for mov in moves : self.board.apply_action(mov) v = max(v, self.alphabeta(alpha, beta, level - 1, self._switch_player(player), weights)) self.board.undo_last() </code></pre> Step 3: stop the recursion. This three is very deep so you have to put a search limit to the algorithm. A simple way is to stop the iteration after <code>n</code> levels. For example I start with B1, <code>max_level=2</code> and <code>current_level=max_level</code>. <ol> <li>From B1 (current_level 2) I apply, for example, the M1 move to obtain B11.</li> <li>From B11 (current_level 1) I apple, for example, the M2 move to obtain B112.</li> <li>B122 is a "current_level 0" board configuration so I stop recursion. I return the evaluation function value applied to B122 and I come back to level 1.</li> </ol> In code: <pre><code>if level == 0 : value = self.board.board_score(weights) return value </code></pre> Now... standard algorithm pseudocode returns the value of the best leaf value. Bu I want to know which move bring me to the best leaf! To do this you have to find a way to map leaf value to moves. For example you can save moves sequences: starting from B1, the sequence (M1 M2 M3) bring the player in the board B123 with value -1; the sequence (M1 M2 M2) bring the player in the board B122 with value 2; and so on... Then you can simply select the move that brings the AI to the best position. I hope this can be helpful. EDIT: Some notes on alpha-beta. Alpha-Beta algorithm is hard to explain without graphical examples. For this reason I want to link one of the most detailed alpha-beta pruning explanation I've ever found: <a href="http://www.cs.ucla.edu/~rosen/161/notes/alphabeta.html" rel="nofollow">this one</a>. I think I cannot really do better than that. :) The key point is: Alpha-beta pruning adds to MIN-MAX two bounds to the nodes. This bounds can be used to decide if a sub-tree should be expanded or not. This bounds are: <ul> <li>Alpha: the maximum lower bound of possible solutions.</li> <li>Beta: the minimum upper bound of possible solutions.</li> </ul> If, during the computation, we find a situation in which <code>Beta < Alpha</code> we can stop computation for that sub-tree. Obviously check the previous link to understand how it works. ;)
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POMinimax / Alpha Beta for Android Reversi Game
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USDavide Aversa
UserOwnerUserId
1. USDavide Aversa
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POMinimax / Alpha Beta for Android Reversi Game
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.