Jewels - Some Comments and a (personal) moan

As one of the very few people who doesn't own a mobile phone (partly as a matter of principle but also because I would need a magnifying glass to use the small screen and keyboard) I have not yet seen the game of Jewels. Nevertheless, Rodion's description is very clear so there is no need for any prior knowledge. After reading the problem description I thought that it was quite likely that potential solutions would run into time problems. I decided to investigate this by writing a simulation of the game (as described by Rodion) with an algorithm to choose the next move.

I found that, with the 8 x 8 board, that the valid moves often ran out before 200 moves had been made. Reaching move 500 was fairly rare and I never saw a game reach move 1000. For the three larger boards, reaching move 1000 was quite common and happened about 80% of the time for the 13 x 13 board. The number of valid moves available to choose from was often as large as 40 to 50 with the bigger boards. A simple algorithm which just finds a valid move and submits this will have no difficulty in reaching 1000 moves (where possible) on all 4 boards within the given time limit. However, if we want to make a reasonable choice from among the available valid moves then the amount of processing time needed goes up dramatically. There is scope for sophistication in choosing the optimum move but this is then dependent on the random choice of jewels which appear in the fill process; so is probably not worth pursuing. I decided not to consider any sophistications but just to compare the valid moves available and to choose the one which scores the most. For my Python program, a game, using all 4 boards, had a processing time of around 12 seconds. Almost 5 seconds of this is for the 13 x 13 board. I am fairly certain that 12 seconds would be outside of the time limit for the problem. But it might be the case that Lua is significantly faster than Python so the time limit might not be exceeded.

It would be interesting to know how the system for checking solutions has been set up. I assume that submission of a move which does not get a score would lead to some sort of error message. Otherwise there seem to be three reasons for ending a game. Either 1000 moves have been played, or the Quit move has been used, or the program has run out of time. In all three of these cases there should be a score to add to the total. I would hope that running out of time would not nullify the score. I would also hope that running out of time would not prevent testing of the algorithm on the larger boards. Scoring is likely to be highest on the largest board.

If timing is likely to be a problem then there are several ways of dealing with it. Reducing the maximum number of moves below 1000 is a possibility but this penalises simpler algorithms which will not need so much time; so I suggest keeping the limit of 1000. If it is straightforward to do so, I would recommend a separate time limit for each board size. These time limits should be roughly in proportion to the area of the board. Then an algorithm which runs out of time on a board is credited with the score accumulated on that board, up to that time. The algorithm then starts afresh with the next larger board.

There is one rather obvious question at this point. Why did I not simply write my test programs in Lua? The answer (unfortunately) is that I have zero familiarity with the language, despite having submitted solutions to the previous Lua problems on this site. I suffer from the problem that my retention of new ideas (which was never good) has deteriorated significantly over recent years. Several days after writing a program in Lua I cannot remember anything about the language. This includes the basic syntax, the special characters, loop structures, the common reserved words, whether or not indentation is used, etc. It is very frustrating! I make a point of using Python several times each week to avoid the same problems occurring with Python. Even then I work with a fairly minimal sub-set of the Python language so that there is less to forget and to minimise the number of times that I have to look up something which I use fairly frequently. Jewels is a challenge problem. The challenge for me is not in writing the solution or even writing it in Lua. (I am sure that it is just as easy to write a solution in Lua as it is in Python). The challenge is in assimilating all of the language ideas needed to write the solution and then writing it before the ideas have gone. Doing this in one long period of time seems to work best. I shall begin by reading Rodion's Introduction to Lua, for the nth time (n-1 being the previous number of Lua problems on the site). I shall then use the reference manual and other online sources to answer questions like "How do you do X in Lua?" and "Is X even available in Lua?" knowing that I have probably already looked for these things several times before when doing previous problems.

Rodion, There is absolutely no need to make this problem available for Python. I think it is really good that you put in problems to encourage the use of other languages like Lua. I described my personal circumstances in case people might be interested. There was no intention to suggest that I did not wish to see problems appearing in Lua. I have already started the process of working towards the Lua program and hope to finish before the end of tomorrow.

Rodion, Python 3 is not a problem for me. My code doesn't use any input or output or any divisions, so should work without any changes. The disappointing part is that it runs four times slower in Pypy2 (or Pypy3) compared with normal Python. I have noticed that Pypy is often slower than Python for some kinds of program. For others it can be very much faster. I tried submitting the program but it is timed out. I assume that you have decided not to go with my suggestions for dealing with the timing issue. In any case, given the speed problems with Pypy, I should probably aim to complete the Lua code and try that.

Rodion, There is no need to add normal Python. I don't thonk the speed issue is anything to do with the differences between my machine and the server. The difference seems to be entirely due to the type of processing being done. I have often used Pypy for the speed advantage; which has sometimes been as much as 40 times better. Equally I have often been very disappointed when Pypy has run considerably slower than Python.

For many of your problems there is an end point to be reached within a time limit. For this problem each move is an end point in itself. If you are able to stop a game after 1000 moves and count the score up to that point, are you also able to stop a game after X seconds and count the score up to that point? If this is easy to do then it makes sense to have separate time limits on each of the 4 boards (as I explained in my earlier post).

As I tried to explain in the earlier post, as soon as you change the algorithm from finding a valid move to finding the best of the valid moves, you immediately hit a huge increase in processing requirements. The only sensible way to choose between moves is to choose the move which scores the most. If you have 45 moves to choose from and have to find the score for each of those .... Well you clearly know what is involved.

I will press ahead with the Lua. I don't know what your overall time limit is but if Lua is 10 times faster than Python that could be enough.

If there is no easy way to have 4 time limits with scores up to that point, and the Lua code is not fast enough; I always have the fallback position of submitting an algorithm which submits the first move to be found. However, this doesn't seem to be in the spirit of the problem. I am interested to know your thoughts on my proposal for 4 separate time limits (proportional to board area) and all scores up to each time limit being counted.

Rodion, I am not suggesting that we have unlimited time. Say, for example, that the 12 x 12 board had a time limit of 0.5 seconds. A simple algorithm could easily get through all 1000 moves in that time but would then be halted by your checker. The scores for all 1000 moves would then be added to the running total. A more demanding algorithm would not be able to get through 1000 moves in this time limit. Suppose that the time limit kicked in after 96 moves had been made. No more moves will be allowed but the score for these 96 moves should be counted. Both algorithms should be able to perform on all 4 boards. In each case the stopping criterion will be the first to occur of 1000 moves, Quit or timeout. I fail to see why the timeout criterion should wipe out the score that has been accumulated up to that point. So we are treating all algorithms equally. More demanding algorithms will be stopped after fewer moves have been made; but they should get an equal chance on all four boards.

If you cannot implement a time cutoff in this way please say so and I will stop making these suggestions.

Unlike chess, a guessing strategy in this case is little better than choosing the first valid move. Certainly you would choose a line of 4 over a line of 3 but the real score changes occur when you look at the cascades.

Rodion, I finally completed the Lua program only to find that this is also timed out. Sadly, I have now disabled the part of the Lua program which chooses the best move. The program will still choose a line of 4 over a line of 3 but very little more than that. It is better than a random choice of move but not by much.

This is now accepted by the system!

Rodion, Thanks for the helpful explanations. One possible way to get around the difficulty of keeping the score before a timeout is to give the player some control over when to stop. If the function suggest is passed the move number for the current board, along with the board itself then the algorithm can call the Quit command if it decides that more moves are likely to result in a time out. For example, if I suspected that making more than 80 moves on a particular board would be likely to put my program over the time limit then I can simply add a command to quit on the 80th move.

I understand your points about move choosing but I think these tend to get swamped by the cascades. At least you can calculate the score for every valid move and then choose on that basis; but this then gets into time problems. Nevertheless I noticed that you did get a reasonable score with your algorithm. In my experiments with the problem on my own computer, I sometimes had scores with 9 digits; almost a billion. This did require a total time of 12 seconds in Python. However, the scores did vary considerably from game to game. Randomness and the exponential rise in score with each extra jewel are the reason for the huge fluctuations.

Thanks for the tip about --luajit. I tried adding this. Even without any other changes to the program it produced an error message that the program was broken. Removing --luajit got the routine working again. I assume that this is due to the 5.1 version, as you suggest. At this stage I don't feel like re-writing the code in a different version of Lua. I am happy to stick with what I have.

I don't think you need worry about anyone managing to gain sufficient information to determine what the puzzle is. There are far too many variables for this. However, you have commented yourself on the big changes in score from small tweaks. That is due to the nature of this game. Your decision to use several boards goes some way towards evening this out but the substantial variability will always be there.

I agree with your comments on the use of deepcopy. I did not use this to reverse the change made by swapping two jewels. I did decide to use it for reversing a cascade sequence. Some of the cascades are quite complex and several may occur one after the other. So deepcopy was used only once (in each case) to reverse a possible sequence of cascades.

Rodion, I have just noticed your latest post. I assume from your comments that the total time limit for the problem is 1 second. This is the first time that I have realised this. It might be helpful to give that information in the problem description, for problems of this nature. I am intrigued by the use of os.clock(). Does this measure time from the point where the server starts the puzzle? Is it also the case that the time simply continues to increase as each of the boards are worked in turn? If this is the case I could set time limits of say 0.1 s, 0.3 s, 0.6s and 0.95 s for each of the 4 boards. That assumes that they are presented in the order 8, 11, 12, 13. That information would also need to be made available to allow strategies like this. In Python I had not realised that global variables would be preserved between moves, still less between different boards. This gives me another possibility to try. However, I will have a break for a day or two first.

And to Mathias, congratulations on the score. I'm impressed that your optimisation skills allowed you to get it in, within the time limit.

Rodion, Thanks for all the effort with this problem. The additional parameters are very helpful, especially the move number, which makes it easy to quit before the time runs out. I notice that you have left the maximum number of moves at 300. You may as well leave it at this value now. It makes it less likely that people will run into time problems.