![]() ![]() The question our AI has to answer is: “Out of all the possible moves at Layer 0, which guarantees the maximum score?” Layer 0 is the current game state, and the goal is to maximize our score. At each recursive layer, the maximizing and minimizing roles are alternated. Positive and negative infinity are wins and losses respectively. We are the maximizing player, attempting to maximize our score, while the opponent is the minimizing player, attempting to minimize our score.Īt the leaf nodes, the evaluated score is backtracked. We can represent the possible moves as a game tree, where each layer alternates between the maximizing and minimizing player. ![]() *Each node is a chessboard instance, and has children corresponding to the possible moves that can be taken from the parent node.Įssentially, minimax aims to minimize the possible losses, assuming both players are rational decision makers. We can represent chessboard positions as nodes in a *game tree. Now that we have an evaluation algorithm, we can start making intelligent decisions! We will use the minimax algorithm for this, and I highly recommend reading up on the Wikipedia article to better understand this decision strategy. Note that instead of iterating over 64 squares for each evaluation, we simply start from 0 and add or subtract from the score according to the latest move, keeping track of the previous score. The following is my implementation of the evaluation function. I certainly am not a chess expert, so the piece weights and PST values are adapted from Sunfish.py. This is from white’s perspective, so it would have to be reflected for black. For this, we use *piece square tables *(PSTs), which assign an additional score delta to each piece based on its position on the board.įor instance, the PST for knights encourages moving to the center: For instance, positions that grant higher mobility should be more favourable. We now have a score based on which pieces exist on the board, but some positions are more favourable than others. If our AI plays from black’s perspective, any black pieces will add to our score, while any white pieces will subtract from our score, according to the following weights: The first aspect of our evaluation involves assigning weights to each piece type. Of course, this does not consider future ramifications - what if Move A gives our opponent the opportunity to attack? We will overcome this hurdle in the following sections by performing lookahead to anticipate subsequent moves. The AI will be able to compare between the two potential scenarios, and decide that Move A is the better move. Let’s say Move A captures a queen, putting our score at 900, while Move B captures a pawn, putting our score at 100. Later on into the game, we are faced with a decision between two moves: Move A and Move B. ![]() Therefore, when assigning a score from our AI’s perspective, a positive score implies an overall advantage for our AI and disadvantage for its opponent, while a negative score implies an overall disadvantage for our AI and advantage for its opponent.įor instance, the score for the starting position is 0, indicating that neither side has an advantage yet. Advantages can come in the form of capturing opponent pieces, or having pieces in favourable positions. Any advantages gained by Player A implies disadvantages for Player B. each set of positions of pieces on the board) so that our AI can make decisions on which positions are more favourable than other positions.Ĭhess is a zero-sum game. Basically, we want to assign a ‘score’ to each chessboard instance (i.e. But how do we implement an AI that plays (reasonably) good chess? Well, we’re going to need an evaluation function. With these libraries, you should be able to create a working chess game by following the examples (5000 through 5005 in particular) on the chessboard.js website. the chess board itself.Ĭhess.js handles the game mechanics, such as move generation / validation. This allows us to direct our focus towards only the most fascinating aspect of the application: the decision-making (AI) part! For this, we will be using external libraries:Ĭhessboard.js handles the graphical interface, i.e. Getting the GUI and game mechanics out of the way. These will be explained in-depth later on, and should be relatively simple to grasp if you have experience in programming. The two main algorithms involved are the minimax algorithm and alpha-beta pruning. Everything else will be covered as part of this tutorial. You should know basic programming and the general concept of a tree data structure. Uses the chess.js and chessboard.js libraries. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |