• Content count

  • Joined

  • Last visited

Community Reputation

166 Neutral

About Verminox

  • Rank
  1. My first AI attempt

    Quote:Original post by AlphaCoder At the leaves, though, I'd still need to evaluate some kind of integer score based on all the "chains" in the leaf position, right? Yup, that time you can just go through all the chains at that position and calculate a weightage value based on the length of the chain and how many open ends it has, etc. Obviously, you will have to account for which player owns that chain and accordingly add or subtract the weight. You might also want to give bonuses if two chains of the same player share an open end (because putting a piece there would fuse the two parts and make a longer chain), although I'm not entirely sure having such chains is a good thing because I havn't played much Gomoku. There is never a hard and fast rule on how to rate different types of "assets" in these type of games (in your case "assets" are chains, in chess it might be pieces). The best way of perfecting your evaluation function is keep trying different tricks which you think are logical (bonuses for patterns that seem smart, penalties for patterns that get you blocked in a corner somewhere, etc.) and play different versions of your engine against each other and analyze games. A lot of tuning may be required before you are satisfied with the result.
  2. My first AI attempt

    Quote:Original post by AlphaCoder I don't understand what you mean by the "score" of a position being a list of chains. Usually, in games like chess, you would evaluate the whole board during leaf nodes of the search tree and give it a "score" based on the piece advantage, mobility, threats, etc. In your game, I see no reason to evaluate the whole board (19x19) because every move just changes the state of the game with respect to that particular position. For example, Here, black has 8 chains of 3 (including diagonals) and 1 chain of 2, while white has 1 vertical chain of 3, 4 chains of 2, and singleton pieces here and there. Now, if white plays move 22 above the piece #8, this move only affects the chain count containing that position (the vertical white expands to size 4 and becomes 22-8-4-6, the black chain 15-13-21 gets blocked at one end, and white gets a diagonal chain 22-2) white all other chains on the board remain unchanged. This goes to show that instead of evaluating the whole grid whenever u want a "score" for the game state, you can just store the chain structure at each point in the game. When you want the "score", you just add up the weights of each chain (and bonuses for double open chains, etc) to get the "score". Quote:Original post by AlphaCoder You are suggesting I create a "chain" datatype that contains the length of the chain and information about it's openness at the ends. Yes, exactly. And store, along with each board representation, a list of current chains. You might want to store more information about the chain such as which position is it open at, or what is the orientation of the chain (vertical, horizontal, diagonal) to make it easy to pick a chain during calculations. Quote:Original post by AlphaCoder And I don't quite understand what you mean with the chain-map structure. The chain-map, is an associative mapping between a given position, and all chains that have a piece or open end on that position. Basically, for each position on the board, you have a list of pointers to chains that contain this position (either because a piece here was part of the chain, or the position is a free end of the chain). So the next time you move/undo on this position, you have to only update the chains mapped to this position, and in case of any updates to the chains (eg. new piece added to the end of the chain), also update the mapping for other positions. For example, doMove(x,y) /* (x,y) are the grid co-ordinates */ { grid.set_piece(x, y, current_player) /* put piece on board */ chain_list = map.get_chain_list_for(x,y) /* find all chains associated with this position */ foreach(chain in chain_list) /* go through all chains associated with this position */ if( chain.open_end == (x,y) ) /* putting a piece at the end of a chain */ if( chain.player == current_player ) /* expansion of chain */ chain.length += 1 /* increase length of chain */ open_end = next_position /* set the open end as the adjacent position */ map.associate(open_end, chain) /* so that the new open end is now related to this chain */ else /* blocking opponent's chain */ chain.open_end = null /* there's no opening for this now */ } Apply reverse for undoMove(). Note that in the above pseudo-code I have not accounted for some situations (eg. putting a piece between two small chains fuses the two chains into one, and the fact that there are two open ends so the checks done above will have to be done twice). This method ensures that at each move, you have a count of the number of chains in the current state of the game. If any chain's length becomes 5, the game is won. No need to keep doing a "Game over test" everytime. If you don't use this method, and you decide to evaluate the entire board at one go, then you will need a real good algorithm to recognize chain patterns... possibly loop through all horizontals, verticals and diagonals (3 iterations of the 19x19 board!!).
  3. [web] PHP - Load Page

    1. Make sure to clean the argument to loadPage for any slashes, etc. or else it is vulnerable to attacks. A user can put anything under ?page= and access private files. I see you have considered this. 2. If your script cannot resolve ?page=404 properly, you will go into an infinite loop. 3. I don't think it is necessary in any design to open a file so many times. You have two fgets() and one include of the same page. I am assuming you are initializing $title for the HTML title. I generally avoid page loading and directly use requests to /about.php. <?php include '/section/html.php'; htmlBefore('About'); // Prints html head section with given title and menus /** ALL CONTENT HERE **/ htmlAfter(); // Prints footer section of html ?> I like this method for many reasons. For one, when open an arbitrary PHP file for editing, you can read the include lines at the top and tell whether it is a page with HTML contents, or if it includes mysql.php it is a page that accesses the database, etc. Also it makes the URLs look cleaner. index.php i reserve only for the front page which has the links to all top level pages and actually behaves like an index. Also that way your other _GET arguments make sense. search.php?term=foo and user.php?id=25 I find nicer than index.php?page=search&term=foo where 'term' is not an argument for other instances of index.php. If you want a custom 404 error page, you can configure that using .htaccess. Also, this is probably be more search engine friendly than the page loading method (unless you are using URL rewrites to rewrite /about to /index.php?page=about
  4. My first AI attempt

    Quote:Original post by AlphaCoder I'm not sure I understand why I need a function which undoes moves. What you are doing is making a copy of the entire board with the new position. This means you are remaking the entire 19x19 grid and all associated properties. You should minimize the number of dynamic memory allocations in the search. Instead if you use a single copy of the board and perform moves and undo moves on it, you will save quite a lot. In fact, in a game like gomoku it is much more efficient because all you have to do is set/unset a piece at a given position and update the chain structure. Why would you want to copy the entire board when the remaining 360 positions are going to be the same and hardly 2-3 chains are getting affected at every move? I learnt this the hard way myself sometime back (thanks alvaro [smile]). The speedup acheived was tremendous. Also, I'd suggest returning the score rather than the best move in your search. You need the best move only in your root search everywhere else you just want to compare scores. state = { grid[19][19], player_turn, chains[] } /* global or class member */ function search(depth) returns int score: if(depth==0): return state.calculate_score() /* sums up weights of chains[] */ else: foreach(legal_moves() as x): state.do_move(x) /* Updates grid[][], player_turn and chains[] */ x_score = search(depth-1) state.undo_move(x) /* Reverts all changes */ if(state.player_turn is min): best_score = min(best_score, x_score) else if(state.player_turn is max): best_score = max(best_score, x_score) return best_score You will see how the integer score is much more valuable to return when you do alpha-beta pruning, etc. If you use transposition tables, you can search even faster and there is no need of comparing moves at the root either because you can just get the best move from the hashtable.
  5. My first AI attempt

    Regarding scoring: Each move has to be adjacent to an existing piece. Therefore, each move is either a 'block' or 'extension' or a combination of multiple instances of them. There is no quiet move. Therefore, instead of evaluating the entire board for every leaf node in the search tree, you can store the static evaluation in the data structure itself and incrementally update it for every move made because the change in evaluation only affects all chains that contain the last move square. The only disadvantage is that the evaluation will be computed at every step in the search tree, but since this method uses only incremental updates, the computations at each step are less. Instead of storing evaluation as an integer score, you can store the evaluation as a list of open chains (a chain object can have data about how many elements in that chain (1-4) and whether it is open on only one end or both ends). You can then use a chain-map structure that can basically give you a list of pointers to chains that position X belongs to. The total integer score for any board position can just aggregate the open chain list. Make sure to use logarithmic weights as InnocuousFox mentioned because a 4-chain is more valuable than three 2-chains. Also note that a game is trivially won when a player has a double open 4-chain or more than one 4-chain with distinct open ends (because whatever the opponent does, you can win at the next move). Storing all this information for one position will not take much space. You should just make sure that your putPieceAt(X) and removePieceFrom(X) (for undoing the move in the search tree) should accurately update the chains-list and chain-map for position X. This method is something that is difficult to do in a game like chess where the effects of a move may be seen elsewhere (eg. discovered check, exposing a passed pawn, a bishop's diagonal gets free) so the entire board has to be evaluated from scratch. In your game the effects of a move are concentrated on that part of the board only. The question of "this will cause a series of forced moves later" will be handled by the tree search. Use a minimax-like search with pruning techniques and other optimizations like alvaro mentioned.
  6. [web] PHP flush

    As ToohrVyk mentioned, PHP by default echos the output immediately without any buffering so no flush should be required. If you (or some script you are using) has turned output buffering on, you might want to use ob_flush() or ob_end_flush() to turn it off completely. See PHP Output Control. Try putting the following lines before your loop starts: ob_implicit_flush(true); ob_end_flush(); If this makes any difference, then the problem was with PHP's output buffering. Also remember that sometimes web servers and web browsers also perform their own buffering, this is something you cannot easily control via PHP. If you are using Apache you might want to read this comment that shows how to disable all kinds of buffering and gzip compression at the start of the script. And to quote more from that page: Quote:Several servers, especially on Win32, will still buffer the output from your script until it terminates before transmitting the results to the browser. Server modules for Apache like mod_gzip may do buffering of their own that will cause flush() to not result in data being sent immediately to the client. Even the browser may buffer its input before displaying it. Netscape, for example, buffers text until it receives an end-of-line or the beginning of a tag, and it won't render tables until the </table> tag of the outermost table is seen. Some versions of Microsoft Internet Explorer will only start to display the page after they have received 256 bytes of output, so you may need to send extra whitespace before flushing to get those browsers to display the page.
  7. Chess Transposition Tables

    Getting back on topic of transposition tables... I have greatly improved the performance by optimizing storage of the hashtables. Instead of using Java objects (which take up a lot of space) I'm using a number of arrays of bytes, shorts, etc. in parallel. Surprisingly (or unsurprisingly), this takes 4 times less space. Using arrays combined with my move hashing technique* each entry in the transposition table is taking just 14 bytes! I am currently running Frittle with 4.2 million transpositions (56MB) and it works great! * Instead of storing the heavy Move object in the hashtable, I generate a 16-bit (actually only 15-bit) unique hash for a move (6 bits for source square, 6 bits for destination square, 3 bits for promotion type). @DpakoH: I just uploaded relese 0.2: This is a HUGE improvement from the earlier version. See the changelog if you are intrested in the stages of development as you said. Adding support for time controls and pondering was really tricky. When using multiple threads, bugs become a way of life.
  8. Chess Transposition Tables

    alvaro: I can't thank you enough. [smile] I refarctored my move generation into using only one board copy at a time and generation of only legal moves without further validation (it took a lot of time and debugging for this) and my perft tests have improved drastically!!! I am now generating over 750,000 moves per second!! That's more than 10 times faster than before. As far as searching goes, I am able to search around 180,000 nodes per second... It will probably reduce when I improve my evaluation function and I know that it's still not as fast as the best engines out there, but I am satisfied for the day [grin] Thanks a lot once again. PS: Those links you provided helped. Bruce Morland's articles were instrumental in my code refactoring. Thanks... Edit: DpakoH - Let me just debug these modifications and then you can give it a test once again... I'll let you know when I upload to sourceforge... And my engine will still play badly at the end because the evaluation does not yet distinguish between middlegame and endgame... In fact I have not added any sense of endgame component in the AI. So that still needs to be done.
  9. Chess Transposition Tables

    Quote:I don't understand the last part about not being "able to order by moves"... Sorry about that, wrote that in the wrong place. That was for your first suggestion (about move validation). What I was trying to say was that my validation part occurs while I try to create the new board state. It is only after the new state is formed can I lookup the hashtable for a score from a shallower search which will help my move ordering. So my move 'validation' has to occur before I decide to start searching. I can't validate them as I search, because I won't know their tentative score (from shallower searches) and hence won't be able to order them. Anyway, I'll try to use only one copy of the board. But that would probably take some time. Thanks a lot for your help. PS: How do you get your engine to be rated (ELO)? I know WinBoard doesn't have a rating system but I think Arena does... How many tests wold I have to go through to get an approximate rating? (I know it won't be very accurate unless thousands of games are played). PPS: Which chess engine have you worked on? Is it freely available? Edit: I performed some Perft tests on my move generation and indeed it is the generation of moves itself that is hampering my search speed. In opening positions with lots of pieces I can barely generate 30,000 nodes per second, and in the endgame with few pieces I can generate about 75,000 nodes per second. Either way, I suppose until I improve my move generation there is no scope for search speeding... [Edited by - Verminox on April 25, 2009 5:55:16 AM]
  10. Chess Transposition Tables

    Quote:Original post by alvaro You don't really need to validate every move. You can delay the validation to the point when you are about to try the move, instead of validating all the moves when you generate them. In an alpha-beta search there will be many nodes where you hopefully only have to consider a few moves, since you'll get a beta cut. In my program the 'validation' is synonymous to generating the new board position after the move (which in turn, lets me retreive information from the transposition table), so without that, I would not be able to order by moves for the alpha-beta search. Quote:Original post by alvaro Most programs have a single copy of the board (or one per thread, if you go parallel), where you do and undo moves. You basically never need to make a copy of the board, which is expensive. I hope some of that helps. Oh, well, in that case, yeah I have a lot of dynamic memory allocation. A lot of GameState (position) objects being copied and each creating their own evaluation results and generating their own move list... You think using only one copy of the board will help improve speed? I had thought of doing this earlier but I wasn't able to implement undo-ing the move. That would require storing a lot of information about the move (like which piece was captured and if there was a promotion involved)... and what about if you had to undo 5-6 places back (coming out of the depth first search)? Gah! I now feel like my entire code has been approached wrongly... [Edited by - Verminox on April 25, 2009 12:00:17 AM]
  11. Chess Transposition Tables

    Quote:Original post by alvaro Congratulations on your progress! You shouldn't be using exceptions in the middle of the search. In a chess engine exceptions can be useful for things like interrupting the search at the user's command, and little else. The other thing you should avoid is dynamically allocating memory. You can organize everything with fixed-size arrays. Perhaps Java is not the best language for this? Why are you using Java in the first place? Also, you haven't told us how many nodes per second your program is visiting. Hmmm.. I guessed as much. I know Java isn't the best language for chess, but I like Java and since I am just doing this as a hobby I thought I could afford the slight performance hit. I feel my move handling is messed up. In my game, there are two different functions for move validation (given source and destination square, is the move valid? if yes, return the new position of the board) and legal move generation (which generates all the possible moves for all pieces on the board and validates them). Considering that the validation function takes decent time and throws an exception in case the move is not valid, I think I am spending most of my time in the search just generating/validating moves (there must be thousands of exceptions being thrown in every search). I need to be able to generate only legal moves so that I can skip the validation step. My program is searching around 12,500 nodes per second, which I know is extremely sluggish. My whole move generation is based on the exception model, so refactoring that is going to be a big task. But I think it is really necessary to speed things up. On the topic of fixed size arrays: How do you mean? The only dynamic data structure I am using is a vector when generating moves, because I don't know how many moves might be possible. Plus, they need to be re-ordered before searching. The transposition table and opening book use fixed size data structures.
  12. Chess Transposition Tables

    alvaro: Thanks for your help. My engine has finally started playing sensibly. I am still not able to reach 6 ply in under a minute, so I need to improve the search a bit. I think my move generation is very slow, and using lots of Java exceptions is not helping. DpakoH: I am using Java to develop the chess engine. I call it Frittle, after the butterfly Frittillus that has chess-board like markings... You can download my first attempt at anything sensible. The current version has beaten amateur human players (like me) but fails against other engines even in easy mode. I still have a lot of things to improve. I just started this around 10 days ago. ..
  13. Chess Transposition Tables

    Quote: Ah. Then I recommend you do things in a different order: * quiescence * alpha-beta * move ordering (for instance: killer move first, then captures in largest-victim/smallest-attacker order, then non-captures in history heuristic order) * iterative deepening * time control * transposition tables * pondering (thinking while it's not your turn) * null-move pruning Ahh, I did not know that quiescence search was so important. I thought it was to extend the search at violent positions, how would it help speed up the search? Maybe I am getting it wrong... Quote:Yes, implementing an opening book is quite trivial. Are you using UCI as the interface to talk to your GUI? If you are not, you should definitely consider it. Some UCI GUIs will deal with the opening book for you. I am using the XBoard protocol. Regardless, I want to implement my own opening book because I want the program to work fine without a GUI as well as I want the experience (I am doing this as a casual hobbyist project anyway).
  14. Chess Transposition Tables

    Quote:Original post by alvaro About twice that. :) Of course, this depends a lot on what you include in the quiescence search and what moves you extend or penalize. But I wouldn't be comfortable if you cannot get to depth 9 in about 10 seconds. Have you tried any move-ordering techniques? How many nodes per second are you visiting? I have just about started writing the program so I have yet to implement quiescence search and other such extensions. My move ordering is based on values of the score retreived from the transposition table which was stored during a shallower search, no guesswork. However, my evaluation function is very weak at the moment (just scans material and mobility) and I feel that is causing bad move ordering. My hopes of a faster search rely on improving my evaluation function. Also I need to implement an opening book because searching 4-6 ply in the opening is giving me dissatisfactory results.
  15. Chess Transposition Tables

    Quote:Original post by alvaro Assuming you are using alpha-beta pruning (and if you are not using it, drop everything and implement it first), you are missing a two very important pieces of data: 1) An enum indicating if the score stored is an exact score, an upper bound or a lower bound. 2) The move that was found to be best or that generated a beta cut. This link seems to have a good description of what to put in the table: Yes, I am indeed using Alpha-Beta pruning. I do check for accuracy of the score but did not implement it correctly in my transposition table, so thanks for remingind me that I have to fix it :-P. And yes, the bestMove is stored in the transposition table but I was just wondering whether the entire ordered list of moves should be stored, and you answered my question. Thanks. The link is also very useful. Quote: There are several possibilities. What I do is simply erase the transposition tables when a move is played on the board. This might make the program a bit weaker, but it has two key advantages: 1) If you find a bug, you can reproduce it, since you start from a fresh state on every move. 2) Time control combined with iterative deepening is a bit easier to do. Hmm, I suppose so. I'll give that a shot then... Thanks for your help... PS: How deep should an amateur chess program be able to search? Mine can search around 4-5 ply in a few seconds in the opening (not yet implemented books) and middle game but searching to 6 ply kinda kills it :-(