All of these tricks are intended to save a factor of at least two (and often ten or more) by local changes to code. Of course algorithmic improvement can provide much greater efficiency gains, so I am assuming that you have done all you can in this respect, BEFORE using these tricks.
Algorithmic Ideas
- Use a lookup table instead of calculating things when needed. Nowadays tables of 10^6 entries are cheap; indeed tables of 10^8 entries can easily be stored on a CD. Example: Noughts and Crosses (Amer. Tic-Tac-Toe): It may be amusing to write a planner for this game, but for efficiency... Pre-compute a table of size at most 3^9 (9 squares holding 0,X or blank) Positions encode `who is to move' by counting 0's and X's. Mark completed games (wins/draws/losses) as 1/0/-1 (unreachable positions like `both sides have won' can be marked randomly, e.g. draw). Back-propagate to mark all positions (using min or max according to turn). This will mark initial position with result if both sides play as well as possible (i.e. draw for this game). Adding a `best move' entry to the table for each position can be done cheaply during back-propagation. Cost is at most 9*3^9 operations (up to 9 predecessors of each position) which is 177147 steps. Cost to play a move is 1 instruction.
Low level hacks
These are all coded in strictly conformant ANSI C; we use 'unsigned' arithmetic to ensure overflow is ignored. Numeric postfixes like `unsigned32' mean that *at least* 32 bits are required to make this work. (ANSI C guarantees `long' has at least 32 bits, but does not necessarily provide a type suitable for `int64' etc). General assumption. If a routine tests (e.g.) a 32-bit integer having a certain property then the actual argument is assumed to be zero-extended to the size of the container type.
References: (Search for hakmem on the web) e.g.
http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html section of
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
0 মন্তব্য(গুলি):
একটি মন্তব্য পোস্ট করুন