This will thus have a chance of trying every move, but will still favour those that provide immediate benefit.īeam Search tries all moves, but rather than keeping only the one best result, keeps a larger number (called the beam width). Randomised Hill Climbing makes a small number of random moves and takes the best of those, rather than trying every move. However, straight Hill Climbing will not detect this because adding a knight always gives a greater benefit in one move.Īs a result two variant algorithms have been used. However, in most positions it is easier to apply multiple Arrows without them blocking each other, which yields a greater benefit than using Knights. In production when Knights and Arrows are available, the total score added by a single Knight is greater than that added by a single Arrow. This is especially the case in NGU industries because of the way wider beacons can stack. It will eventually reach a state which cannot be improved in one move, but is not necessarily the optimal state available, nor even the best that could be reached with a larger number of changes this is called a local maximum (plural maxima). This will quickly produce an efficient map, but it will often not produce the most efficient map, because it focuses entirely on improvements that can be achieved in one move. Hill Climbing is based on taking the "current" map, trying every possible single move (adding, removing, or replacing a beacon) and seeing which one yields the highest score, then repeating the process. There are several approaches that have been implemented so far. These are based on searching only positions that are close to the current position, then repeating this process to gradually move towards better solutions. A computer that could score 1,000,000,000 (1 billion) states a second would still take millions of years to check them all, so it is clearly not possible to evaluate every combination.Īs a result, most programs have used local search techniques instead. If only Square beacons are available, then each of these squares can either have a beacon or not, meaning that the number of potential combinations is a 132-bit number - 5,444,517,870,735,015,415,413,993,718,908,291,383,296. Tutorial Island, the smallest map, has 132 available squares. It is so far the only program that can optimize for efficiency or combinations including efficiency. Rabbit's program provides a visual view of the effect of all beacons and the solving process. It can also generate graphical maps from textual ones and can optimize for speed+production combined. MisterCodo can tie on some maps and exceed on a few others. Hyphz v2 can tie with Rebrane but has not yet exceeded it it can however generate (relatively) higher scoring maps more reliably. The following programs exist for creating optimised beacon maps:īeam Search with Randomisation and In-Place Type OptimisationĬurrently Rebrane's program gives the most optimal maps, which are found on User:Rebrane/Optimal beacon configuration.
0 kommentar(er)
