Jump to content

  • Log In with Google      Sign In   
  • Create Account


Álvaro

Member Since 07 Mar 2002
Online Last Active Today, 05:40 PM

#5056977 Chess Engine - search development priority

Posted by Álvaro on 26 April 2013 - 09:03 AM

Please, print sizeof(Napoleon::HashEntry) and see if you get 18 (you won't).

 

I agree that there is nothing special to do about principal-variation moves when sorting, because using the move from the hash should be about the same thing as picking it from the PV.




#5056944 Chess Engine - search development priority

Posted by Álvaro on 26 April 2013 - 07:20 AM

The data structure seems correct. The only comment I have is that if you switch to using a 16-bit representation for the move, the size of a hash entry will go from 24 bytes to 16 bytes (this depends on the compiler, of course).




#5056781 Chess Engine - search development priority

Posted by Álvaro on 25 April 2013 - 06:46 PM

You need to debug the difference in perft with and without transposition tables. Can you post the definition of the type of your TT entries?


#5056621 C++ - freeing dynamic memory

Posted by Álvaro on 25 April 2013 - 05:19 AM


int ary = {5, 6, 7};
int* aPointer = &ary;


Both of those lines are wrong. Please, check your code for accuracy before posting it. Just run it through a compiler to make sure you didn't make some mistake, and then copy and paste it here.


#5056367 C++ - freeing dynamic memory

Posted by Álvaro on 24 April 2013 - 08:46 AM

Once you are done learning how to use dynamic memory allocation and naked pointers, learn how to use standard containers (particularly std::vector) and never do it again. If you are tempted to use dynamic memory allocation and naked pointers in the future when you need polymorphism, learn about standard (in C++11) smart pointers (particularly std::unique_ptr) and continue not doing it.


#5056364 Ternary Operator and Polymorphism

Posted by Álvaro on 24 April 2013 - 08:37 AM

Then you can get it to work by static_cast'ing each of the operands to A*.

That is right. Although a conversion from a pointer to a derived class to a pointer to its base class is implicit, the rules for the ternary operator are such that you need to explicitly cast at least one of them, so the compiler can deduce the type that the ternary operator will return:
  Base *b = (turn % 2 == 0) ? static_cast<Base *>(new Derived1) : static_cast<Base *>(new Derived2);



#5055852 Dealing with a large number of events in a BT system

Posted by Álvaro on 22 April 2013 - 03:48 PM

I am a big fan of utility-based architectures. You list the available actions, compute a function that maps action to a real number and pick the action for which the number is highest. The real number you compute is an indication of how happy the agent is with the action (technically it should be the expected value of the agent's utility function). The actions of any rational agent can be expressed in this framework (for some definition of "rational" that I happen to like).

For a video game, you can probably get away with your utility function being just a sum of terms that indicate features that make an action desirable or undesirable. In some situations there is a natural scale for measuring utility (e.g., dollars), but sometimes it is tricky to balance terms that are very different in nature. Most of the terms in the utility function can simply be one-variable functions: One for health, one for health of my allies, one for health of my target (if I have one), one for how much money I have, one for obeying an order... The exact shape of those functions could be data driven.

It might take a bit of work to get used to expressing behavior as maximization instead of more direct commands, but I have had very good experiences with these systems. In particular, they are easy to tweak when agents are not behaving as desired (especially if you build some dumping mechanism for debugging), and they prioritize desires extremely well in unusual circumstances (so they don't try to finish their coffee when someone walks into the room with a gun, because the satisfaction of having coffee is dwarfed by the desire to be safe).

I expect it would be relatively easy to integrate BTs and utility-based decisions, for instance by having some action-selection node in the BT that evaluates a utility function to decide which plan to take. I have no experience with these mixed systems, and I prefer to keep things uniform. But if you are heavily invested in BTs, you might want to consider this option.


#5055746 Chess Engine - search development priority

Posted by Álvaro on 22 April 2013 - 08:03 AM


I used to do that in my old engine (Ruy-López), but that requires you to generate all the moves before you even try the move from the transposition tables. Since this move very often produces a beta cutoff, it's worth writing a function that checks validity of a move on a given position and try to avoid generating the move list altogether.[/size]

I use a 16-bit format for the move, as described here: [/size]http://chessprogramming.wikispaces.com/Encoding+Moves

 
That's sound cheaper than what I implemented now, I'll try.
You said that you can encode a move in 16 bit, but as far as I know the minimum is 32 bit (how do you manage castle and en passants?).


Castling and en-passants are encoded in the 4-bit "move type" described in the page I linked to. That plus 6-bit "to" and "from" gets you to 16 bits.

Omitting this, I made some test when i was working on the move generator and it came out that my move encoding (which is a class with 4 byte fields ) is faster than using a single 32 bit integer for representing it. Should I change encode method for saving some memory in the transposition table?

No, you can always convert to and from the 16-bit format just for transposition-table access. That shouldn't be too slow.
 


That's a very difficult question. A few ideas:[/size]
* You can run a search up to depth D (I assume you are using iterative deepening) and then rerun it without clearing the transposition tables: It should be almost instantaneous.[/size]
* You can run a long search on a position with and without transposition tables, and the version with transposition tables should generally get to the same depth faster.[/size]
* You can match your program against itself, with and without transposition tables, at a fixed depth, and the results should be even.[/size]

 
for trying  point one I should first implement iterative deeping (when should i do that?).


Now would be a good time. It's basically impossible to implement time control without it, and it's very hard to work with an engine that doesn't control time properly.

P.S. I've just implemented MVV-LVA and the search is now MUCH faster! thank you.

Yup, that one is a biggie.


#5055734 Chess Engine - search development priority

Posted by Álvaro on 22 April 2013 - 07:05 AM

Thanks for your answer, now I see all more clear,  but I still have some doubts:
regarding Transposition tables, should i save leaf nodes during alphabeta (and maybe also during quiescence search)? I tried to run the program without saving them and it seems to work faster.

That's a minor detail. In my own engine, I don't use the transposition tables at all in quiescence search, but I know others do it. You will just have to test it. But it's not critical.

For storing the best move, can i just use the index of the move inside the array?

I used to do that in my old engine (Ruy-López), but that requires you to generate all the moves before you even try the move from the transposition tables. Since this move very often produces a beta cutoff, it's worth writing a function that checks validity of a move on a given position and try to avoid generating the move list altogether.

I use a 16-bit format for the move, as described here: http://chessprogramming.wikispaces.com/Encoding+Moves

P.S. i forgot one important thing: How can i prove my transposition table is working correctly?

That's a very difficult question. A few ideas:
* You can run a search up to depth D (I assume you are using iterative deepening) and then rerun it without clearing the transposition tables: It should be almost instantaneous.
* You can run a long search on a position with and without transposition tables, and the version with transposition tables should generally get to the same depth faster.
* You can match your program against itself, with and without transposition tables, at a fixed depth, and the results should be even.

I recommend you spend some time trying better replacement schemes. I use buckets of size 4, which seems to work very well.


#5055636 Chess Engine - search development priority

Posted by Álvaro on 21 April 2013 - 08:39 PM

Move ordering is probably the most important part, especially in the quiescence search. MVV-LVA is a simple and effective order for captures. For non-captures, search killer moves first and then everything else in history-heuristic order. You can then try to move captures with negative SEE to the end of the move list, so they are searched after non-captures.

Ah, and more important than most of those things, you should store the best move in the hash tables, and try it first in case of a hash hit where you cannot just return a score (because of not enough depth or a useless bound).

By the way, perft 6 in 1.2 seconds is pretty impressive, if it's from the starting position. My own engine fits a similar description to yours, and my perft is about 6 times slower than that (although we are not using the same hardware, of course).


#5054926 What do you think of my encryption algorithm

Posted by Álvaro on 19 April 2013 - 08:44 AM

Oh, there is also a Wikipedia page on the weaknesses of this type of encryption scheme: http://en.wikipedia.org/wiki/Stream_cipher_attack


#5054582 Bomberman AI approach

Posted by Álvaro on 18 April 2013 - 08:48 AM

Next approach i was planning to try was with game tree algorithms - minimax, alpha-beta pruning... At this point i realized that every article i found about minimax assumed that players alternate with moves. In bomberman this isnt true, everybody make action at the same time. With that information. If i have 4 players and 5 actions (moves and bomb place), at every cycle there could be 5^4 possibilities of actions. It is quite a large number and in game tree with depth 3 it is impossible to search.



So my question is - is there any better way? Or any algorithms that are based on this type of game where everyone make move at the same time? Or game tree is in this situation bad idea?

Not only does minimax require alternating turns, but it also only works for two players. There is another paradigm for building AI for board games that is way more flexible: Monte Carlo Tree Search. It can handle multiple players, simultaneous decisions and randomness without much trouble.

The best go programs use MCTS, even though it is in the class of games where minimax can be applied. The main reason for this is that, unlike minimax, MCTS doesn't require an evaluation function, and nobody knows how to write a decent evaluation function for go.

http://senseis.xmp.net/?MonteCarloTreeSearch
http://senseis.xmp.net/?UCT (UCT is a specific algorithm of the MCTS family)

If anyone has better links for MCTS, please post them.


#5054134 Heuristic for minimax - Board Game 'Odd'

Posted by Álvaro on 17 April 2013 - 04:02 AM

I have one thought about this game that might be relevant: This game is played on a graph, in the sense that the geometry of the hexagonal pattern (e.g., what's aligned) does not matter. It could be played on any other graph just fine. Towards the end of the game, small groups that cannot grow because they are totally blocked by the other color are irrelevant and can be removed from the internal description of the board. Similarly, large groups are equivalent, whether they have 5 stones or 15. This allows to simplify the graph structure towards the end of the game. The are more simplifications available, like identifying "pass" cells (empty cells where you can prove that it won't matter whether they end up being black or white) and ignoring what they attach to. I believe only the parity of the number of "pass" cells on the board really matters.

If you explore a position using minimax and you get a winning or losing score, you can store the simplified graph of the position (or some hash of it) and its score. Over time you can build a database of endgame positions that way, and then you can query this database in the search. If the graphs simplify as much as I think they will, this should allow you to deduce the true score of positions from pretty early on in the game.


#5053787 Easing with Max Speed

Posted by Álvaro on 16 April 2013 - 05:16 AM

Define a smooth function f such that f(0)=0, f'(0)=0 and f'(time_to_max_speed)=max_speed (f(t)=some_constant*t*t or some_constant*t*t*t would do). Then build your movement by using f until you reach max speed, then continue at that speed for a while, then use a flipped version of f to slow down.

I could fill in the details, but it's not much fun, and you should really try it yourself.


#5053558 Coding Style: Curly Braces

Posted by Álvaro on 15 April 2013 - 02:18 PM

If you are working with other people in a project, do what they do. That's really the only rule we follow in my company, and over time we have developed a pretty uniform style of code formatting, without ever having to argue over any of this.

In the specific case of curly braces, we use the latter style, which I prefer because I value vertical real estate in programming. But either one is fine.




PARTNERS