I'm working on a chess AI and have concerns for the performance later down the road.
Right now, my negamax tree contains every game state as you would expect, though each state stores the entire board in ASCII form, along with the fitness and methods.
Would the tree perform better if I were to trim the stored information down to, say, just the moved piece?
For example, instead of storing the entire ASCII board, store just "b2a2" (b2 moved to a2).
Thanks.
Would a minmax / negamax tree perform significantly better if the stored states contained little information?
135 Views Asked by Tyler At
1
There are 1 best solutions below
Related Questions in PERFORMANCE
- Slow performance on ipad erasing image
- Can Apache Ant be told to cache its XML files?
- What are the pros and cons of the picture element?
- DB candidate as CouchDB/Schema replacement
- python member str performance too slow
- Split a large query (2 days) into pieces to increase the speed in Postgres
- Use GUI displayed results of SQL query vs new queries?
- fastest way to map a large number of longs
- Bash regular expression execution hangs on long expressions
- Why is calling a function so slow in Javascript?
- Performance of element-compare in java collections
- "Capture GPU Frame" in XCode -- iOS only?
- Efficiency penalty of initializing a struct/class within a loop
- Change the rotating speed of the circle when the mouse moves using javascript
- Replace foreach to make loop into queryable
Related Questions in OPTIMIZATION
- Does compiler optimize operation on const variable and literal const number?
- Optimizing for Social Leaderboards
- 3D FFT with data larger than cache
- Optimum directory structure for large number of files to display on a page
- How to make faster queries on my mysql table?
- Xib taking long time (>1s) to load. UIFont cache seems to blame
- How to speed up string comparisons in an array with a for loop?
- How to load all symbols from shared library on start up?
- Cython speed vs numpy
- Improve Speed of Piecewise Function in MATLAB
- How to check that all values are equal in array using recursion?
- PHP split string into known tokens and remaining words add to single-worded array
- Python: why is my O(n) slowing down as it progresses?
- Hint indexes to mysql on Join
- Error When Compiler Optimizations are on
Related Questions in TREE
- prolog traverse nonstandard tree left to right
- Why would one use a heap over a self balancing binary search tree?
- recursively editing member variable: All instances have same value
- D3.js collapsable tree - visualise set number of levels
- java - How to generate Tree from two dimensional array
- Haskell, Tree problems
- d3 indented tree close other nodes with child and open only specific node
- Function that return average depth of a binary search tree
- SQL Tree Structure Table
- Java: make prefix tree remember last value that was not null
- C++: no matching function call
- Building SQL tree from random parent updates
- Use significant attributes only, or use full set of attributes to build J48 model after checking information gain?
- Trie Data Structure in Finding an Optimal Solution
- How to store data in a tree structure in R?
Related Questions in CHESS
- Eight Queens Puzzle in CLIPS
- Chess Engine TypeError: unhashable type: 'list'
- Making a chess game in Java, I want to move the pieces
- Are recursive computations with Apache Spark RDD possible?
- What is the maximum strength of a chess engine with a board representation using an 8 by 8 array?
- Get enemy's possible moves in chess to a 2D array - Python
- Collection View Cell Loading time
- telnetlib for python, how telnetlib can help me to figure out who is the person sending a tell to my BOT?
- friend declaration specifying a default argument must be a definition error
- N-Queens puzzle, but with all chess pieces
- Chess Validation Move input wanted
- How to put .gif files in the build directory
- Using a for-each loop within MouseClicked to getX and getY of each object
- C++ Builder - Piece.cpp(20): E2316 'Button1Click' is not a member of 'TForm'
- C++ Builder - Using same Event TWICE
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Short answer: Yes, storing only the moves should be faster.
Long answer:
At each position, you have to have access to the current board. In general, chess engines use a data structure for the board, which includes a MakeMove and UnmakeMove operation. Then it is sufficient to store only the moves.
Technically, it is possible to avoid implementing a real UnmakeMove operation by internally keeping a stack of the positions. Then UnmakeMove just pops the stack. On some older architectures, this used to be very fast. If I'm not mistaken, Cray Blitz used that technique in the 80s.
Today, all engines that I know implement an UnmakeMove operation, as on todays machines cache efficiency is very important. Keeping a stack of positions puts too much pressure on the cache, so it is avoided.
By the way, as you mentioned that you are using an ASCII representation of the board, I would encourage you to read the Board Representation article on the chessprogramming wiki. Using an efficient representation of the board is crucial for performance.