Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence

From Sokoban Wiki

Jump to: navigation, search
_______________________________________________________________________________________________________
Begin of email to Institute of Informatics, Brazil 
_______________________________________________________________________________________________________

_______________________________________________________________________________________________________
Att.:
  Institute of Informatics 
  Federal University of Rio Grande do Sul, Brazil

Email:
  [...]

cc:
  [...]
  
Subject: 
  Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence

Dear Sirs and Madams:

When you have scrutinized the material presented in the two attached documents, I will appreciate it very much if you will answer the following questions:

1. Will you withdraw any academic credits the four article authors may have received for their article?

2. Can and will your university take measures to stop their article from circulation?

3. If the article authors still are staff members, students, or otherwise affiliated with your university, will you penalize them in other ways for their misconduct, ineptitude, and failure to live up to basic academic standards? 

Yours faithfully
Brian Damgaard

Email:
  BrianDamgaard@jubii.dk

Attached:
  Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence.txt
  Solving Sokoban Optimally with Domain-Dependent Move Pruning.pdf

_______________________________________________________________________________________________________
End of email to Institute of Informatics, Brazil 
_______________________________________________________________________________________________________

_______________________________________________________________________________________________________
Begin of text document
Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence.txt
_______________________________________________________________________________________________________

_______________________________________________________________________________________________________
Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence
Author: Brian Damgaard, Denmark, 2016

__________
Contents
1. Summary
2. Terms and Definitions
2.1. Document Terms and Definitions
2.2. Sokoban Terms and Definitions
3. Background
4. Evidence
4.1. Impossible Familiarity with PI-corrals
4.2. False Description of PI-corrals
4.3. False Accusations 
4.4. Lies
4.5. Circumstantial Evidence
4.5.1. Stupidity
4.5.2. Indecency
4.5.3. Timo Virkkala's Master's Thesis
4.5.4. DDMP instead of PI-corral*
4.6. Cover-up
5. Incompetence 
5.1. Flawed Algorithm
5.2. No Research
6. Conclusion
7. References
7.1. Texts
7.2. Webpages
8. Exhibits

____________
1. Summary

This document will show that the authors of the article "Solving Sokoban Optimally with Domain-Dependent Move Pruning" have:

1.1 Stolen an idea.

1.2 Made a cover-up by not listing the source material they have used.

1.3 Misrepresented the original idea, adding insult to injury by accusing the original discoverer of the mechanism (Mr. Matthias Meger) and me (Brian Damgaard) of lack of insight, and of implementing a flawed version of the idea.

1.4 Neglected to mention and reference any of the existing, publicly, and easily available material describing the idea.

1.5 Presented a flawed version of the idea, a flaw which is not there in the original and true version of the idea.

(Given the article authors' contemptible behavior, it is impossible not to give in to a vicious streak and ridicule them for point 1.5).

Briefly explained by using Sokoban technical terms (see 2.2), the article "Solving Sokoban Optimally with Domain-Dependent Move Pruning" is built around these misstatements:

1.6. The Sokoban community has only discovered I-corrals, not PI-corrals.
1.7. The Sokoban community has falsely attributed PI-corral pruning properties (admissibility) to I-corrals.
1.8. The article authors have rectified this error by discovering PI-corrals.

All three points are false, as this document will show.

It cannot be emphasized strongly enough that the easiest way to understand what this is all about, is first to read the "Informal Overview" located at the very end of this document as "Exhibit X". The informal overview sacrifices rigor for clarity, and its informality does not reflect the severity of this matter. Thus it would be inappropriate to incorporate it as a part of the main text, so instead it has been relegated to "Exhibit X".

__________________________
2. Terms and Definitions

____
2.1. Document Terms and Definitions

In this document, the following terms are frequently used.

2.1.1. The article (The PI-corral article) (The DDMP article):
  The article "Solving Sokoban Optimally with Domain-Dependent Move Pruning". [1]
2.1.2. The article authors:
  Renato R. Leme, André G. Pereira, Marcus Ritt, and Luciana S. Buriol. [1]
2.1.3. Solver (Solver program):
  Sokoban puzzle solver program.
2.1.4. [1], [2], ...:
  References listed at the end of this document. 
  Please note that these are the reference numbers used in this document, not the reference numbers used in the article.
2.1.5. (A), (B), ...:
  Exhibits placed at the end of this document.

____
2.2. Sokoban Terms and Definitions

Only Sokoban terms and definitions of particular relevance for this document are included. For a general introduction to Sokoban, see [5].

2.2.1. Boxes (Stones)
  The objects on the board which the player can push around.

2.2.2. Corral
  An area of the board which the player cannot reach, surrounded by a barrier made of one or more boxes, and any number of walls.
  The corral includes all the boxes on the barrier between the inside and the outside of the corral, and all interior boxes, if any.

2.2.3. I-corral
  A corral where all boxes on the barrier can only be pushed into the corral by the first push.

  The "I" in "I-corral" is a reference to "inside" or "inward".

2.2.4. PI-corral
  An I-corral where the player can perform all legal first pushes into the corral, meaning the player can reach all the relevant boxes from all relevant directions.

  The "P" in "PI-corral" is a reference to "player" or "pusher".

  Please note that the three diagonal boxes in "Fig. 3" in the article do not create a PI-corral but just an I-corral.

  Please also note that it is untrue when the article authors say, that the PI-corral pruning algorithm from the Sokoban community does not differentiate between I-corrals and PI-corrals.

  Please also note that the article authors do not mention that their "Fig. 3" depicts a PI-corral created by all four boxes, meaning that the PI-corral pruning algorithm from the Sokoban community would have performed pruning in this example, if there had been other pushable boxes on the board. 

2.2.5. PI-corral pruning (PI-corral algorithm) (PI-corral mechanism) (PI-corral technique) (PI-corral idea)
  Usage of the PI-corral property in a search algorithm to prune game positions from the search.

  The PI-corral property in itself is not enough to permit pruning. There is the additional constraint that sooner or later, at least one of the boxes on the barrier must be pushed into the corral in order to solve the puzzle. There are different reasons why such a push may be necessary, so this constraint can be implemented with various degrees of sophistication. 

  The constraint "Pruning is only permitted if at least one box in the PI-corral is not on a goal square, or if at least one goal square in the PI-corral does not contain a box" can be implemented by simple inspection of the game position. A more sophisticated solver may form plans which permit pruning for more involved reasons, e.g., "The player must pass though the corral", or "A box from the outside must be parked inside the corral". 

  Please note that neither this document nor the referenced material do always make a clear distinction between "PI-corral" and "PI-corral pruning". Sometimes, the term "PI-corral" is used where strictly speaking "PI-corral pruning" is meant.

_______________
3. Background

In 2005, Mr. Matthias Meger from Germany had a brilliant insight and discovered a completely new and important pruning mechanism for the Sokoban game. 

Mr. Meger presented the idea to me in the private mail-correspondence we had at that time about Sokoban solver programming (see A). There was, and is, no doubt about that his idea was a novelty. Neither the academic Sokoban papers nor the Sokoban solver programs available at that time mentioned or claimed having anything with the slightest similarity to his new pruning mechanism.

Mr. Meger's mechanism had several remarkable and highly attractive properties for a Sokoban solver program:

3.1. It pruned a significant number of game positions from the search.
3.2. It steered the search towards positions with a certain class of deadlocks, thereby helping to find these deadlocks early on, increasing the pruning even further.
3.3. It did not destroy any push-optimality guarantees provided by the solver.

Solving Sokoban puzzles is a very difficult task for a computer program, and with such a plethora of attractive properties, Mr. Meger and I promptly implemented the mechanism in our respective solvers, JSoko [7] and YASS [8]. 

Ca. 2010, I described the algorithm and documented the results in an informal manner in my "Scribbles" [4] (see J, O). I had early on coined the terms "corral", "I-corral", and "PI-corral" to facilitate the description of different aspects of the idea, and it was here in [4] that the term "PI-corral" appeared in public for the first time. As it will become clear later, the article authors' familiarity with this term is of a major importance, eliminating the possibility that the article authors' work is an independent discovery of the same mechanism.

In autumn 2010 (see B), Mr. Pavel Klavik published his technical report "Sokoban solver - a short documentation" [2], with a reference to the Sokoban wiki [10] as the source of information about PI-corral pruning. The Sokoban wiki [10] links to [4], so this was in effect an indirect reference to [4].

In April 2011 (see V), Mr. Timo Virkkala's master's thesis "Solving Sokoban" [3] gave PI-corral pruning its first thorough academic treatment, with a reference to [4] as the source of information about the mechanism. 

Mr. Virkkala's thesis contains a description of PI-corrals as well as a statistical analysis of the effect of PI-corral pruning. Thus, the article authors can neither claim that their article is the first academic paper describing the idea, nor can they claim that their article is the first academic paper with a detailed statistical analysis (see O).

_____________
4. Evidence

This section proves the counts listed in the summary. Since some of the counts are inseparable, the evidence will be in the form of logical deductions based on an analysis of revealing quotes from the article, combined with easily verifiable facts drawn in from the material [1]..[13] listed at the end of this document. Facts of particular importance are presented at the end of this document as exhibits (A)..(W).

____________________________________________
4.1 Impossible Familiarity with PI-corrals

The article says:

:: In the Sokoban community, notably in the solvers JSoko [11] and YASS [12], 
:: we can find a domain-dependent technique called PI-corral. 

There are only three ways the article authors can have acquired that piece of information, and all three ways are impossible and logically inconsistent with the article authors' claim of having discovered the algorithm themselves. The three ways are:

4.1.1. The article authors have read it in material listed in their references.
4.1.2. The article authors have read it elsewhere, in material not listed in their references.
4.1.3. The article authors have read a description of PI-corrals elsewhere, and after inspection of JSoko and YASS material concluded that they implement PI-corral pruning.

______
4.1.1. The article authors have read it in material listed in their references

This is impossible for the following reason.

The only materials referenced in the article, where such a piece of information might have appeared, are the JSoko and YASS projects themselves. If the article authors had looked here, they would not have found a description of a concept named "PI-corral".

The two projects do indeed implement Mr. Meger's idea, and the algorithm is indeed called "PI-corral pruning" after [4], but the "PI-corral" term is not used anywhere by these projects simply because the term was not well-established at the time the algorithm was implemented, and by happenstance the term has not crept into the projects' materials in newer versions (see C). 

So to establish a link between the term "PI-corral" and the projects JSoko and YASS, the article authors must have looked elsewhere.

______
4.1.2. The article authors have read it elsewhere, in material not listed in their references

This is logically inconsistent with the article authors' claim for the following reason.

There are two known sources stating that the YASS project implements PI-corral pruning: [3] and [4] (see D and E). Since [4] says that it is Mr. Meger's idea, it would be fair to grant the article writers the benefit of the doubt and allow them to assume that his JSoko solver program implements it too (see F). The document [2] does not say that YASS implements PI-corral pruning, but YASS is mentioned (see G).

But [2], [3], and [4] all contain complete descriptions of PI-corrals (see H, I, J), including, of course, what the article authors call the "accessible" constraint, which they falsely claim to be their idea. 

It is impossible to extract or infer the information "JSoko and YASS implement PI-corral pruning" from [2], [3], and [4] without reading these definitions of a PI-corral. Consequently, the article authors have no other option but to postulate that they are not acquainted with [2], [3], and [4], otherwise the article authors cannot claim having developed the algorithm themselves.

The article authors cannot weasel their way out of this predicament by saying they have read it elsewhere. Even if they had the information from some obscure and difficult to find source, the article authors were required by academic standards to reference their information, or in this case to check the material, i.e., to verify that the two projects do indeed implement PI-corral pruning.

There are no such references in their article, and 4.1.3 will prove that it is impossible to inspect the JSoko and YASS projects' material and not seeing that they implement the full PI-corral pruning algorithm, meaning they include what the article authors call the "accessible" constraint. 

______
4.1.3. The article authors have read a description of PI-corrals elsewhere, and after inspection of JSoko and YASS material concluded that they implement PI-corral pruning.

This is logically inconsistent with the article authors' claim for the following reason.

In this scenario, the article authors would have to look at the material belonging to the two projects. But just like the texts [2], [3], and [4] contain complete descriptions of PI-corrals, so do both projects contain complete descriptions of the PI-corral pruning. The relevant source code in both projects is accompanied by well-written commentary describing the full algorithm, just without using the term "PI-corral" anywhere (see K and L). 

It is impossible to inspect the relevant source code without seeing the comments, and it is logically impossible for the article authors to have seen the comments and then claim having developed the same algorithm.

______________________________________
4.2. False Description of PI-corrals

The article says:

:: In the Sokoban community, notably in the solvers JSoko [11] and YASS [12], 
:: we can find a domain-dependent technique called PI-corral. 
:: [...]
:: This technique considers that a set of stones is a PI-corral, if all stones 
:: in the frontier of the unreachable zone, can only be pushed into the unreachable zone
:: (called corral). 

As already documented in 4.1, this is a false description of the PI-corral concept. (see H, I, J, K, L). The definition of a PI-corral has, of course, always included the "accessible" constraint, which the article authors falsely claim to be their idea.

The quotation from the article contains a description of an I-corral (see 2.2.3, J), not a PI-corral (see 2.2.4, J). The article authors do not explain where their flawed PI-corral definition comes from. There are no known sources for it. For instance, a 2016-04-29 Google search for "PI-corral Sokoban" produces a list of links to correct definitions, including [2], [3], and [4], and not a single wrong definition seems to appear in the search result. 

Interestingly, there exists another text, predating the article, where one of the article authors presents the same material as the article, but with yet another false description of PI-corrals (see U). Given that the PI-corral article revolves around the PI-corral concept, it can only be seen as a display of utmost incompetence, that the article authors cannot even agree on the same false interpretation of what a PI-corral is.

Even if the article authors today could present some obscure webpage with such a flawed PI-corral description as the one given in the quotation, it would not give the article writers the right to use it as a fig leaf and claim that such a webpage is enough as foundation for their article, and to claim they are in the clear. 

The article authors would not be able to explain how they linked such a flawed definition to JSoko and YASS. That is impossible (see 4.1), and even if the article authors again could come up with an almost plausible explanation, academic standards would as a bare minimum have required the article authors to check if the two projects really suffered from such a severe error, before the article authors published their false accusations about lack of insight.

________________________
4.3. False Accusations

The article says:

:: In the Sokoban community, notably in the solvers JSoko [11] and YASS [12]
:: [...]
:: As they argue 
:: [...]
:: They claim without proof that this technique, as presented, maintains optimality 
:: of the solution. But, as we can see in Figure 3, this is not true.

This is scandalous for a great many reasons but before getting into that, two observations of a semantic nature are important.

4.3.1 "They" are Mr. Meger and me.
The article authors are here using "they" as a reference to the authors of the JSoko and YASS material, in effect Mr. Meger and me (see M). 

4.3.2. "Argue" and "claim" are references to material with a line of reasoning about PI-corrals.
By using the words "argue" and "claim" the article authors admit having read material with a line of reasoning about PI-corrals (see N), as opposed to, say, making a summary based on an analysis of JSoko and YASS source code. 

As documented in section 4.1, it is impossible to inspect JSoko and YASS material without seeing a correct PI-corral pruning implementation, just without ever seeing the word "PI-corral". This is in itself enough to conclude that "they argue" and "They claim" cannot be references to JSoko and YASS material. 

But furthermore, there is nothing in JSoko and YASS material which allows a summary like "they argue" or "They claim" in relation to PI-corrals. It is inherently difficult to prove the non-existence of such material, but on the other hand, the article authors have not documented where in the JSoko and YASS material they have found anything that justifies that type of summary. 

The only possible conclusion is, that "they argue" and "They claim" are not references to JSoko and YASS material. The article authors must be referring to something else.

My "Scribbles" document [4] is the only existing piece of material written by JSoko and YASS authors to which these instances of "they argue" and "They claim" are applicable, whether the statements are true or not. But the article authors cannot proclaim that "they argue" and "They claim" refer to this document. That would be logically inconsistent with the article authors' claim of having developed the PI-corral algorithm themselves for the following reasons.

4.3.3.
As already mentioned several times before, for instance in section 4.1.2, the document [4] contains a correct definition of PI-corrals and PI-corral pruning (see J). 

4.3.4.
The document [4] is not a part of the JSoko and YASS material, and JSoko and YASS material do not mention or make references to that document. Consequently, the article authors would have had an obligation to put [4] on their list of references, in order to live up to basic academic standards. 

___________
4.4. Lies

The article says:
:: They claim without proof that this technique, as presented, 
:: maintains optimality of the solution. 

Aside from the fact that this is a false statement (see 4.2), the existence of this statement itself is irrefutable evidence, proving that the article authors are acquainted with the document [4], even though it is not listed among their references. This follows from the following facts.

4.4.1.
The article authors are here using "they" as a reference to the authors of the JSoko and YASS material, in effect Mr. Meger and me (see M). 

4.4.2
The article authors' false statement refers to this sentence in [4]:

:: (This entails that PI-corral pruning even has the extremely pleasant property 
:: that it doesn't interfere with the push-optimality of a solution.) 

There are no other published statements about the push-optimality of PI-corral pruning by the authors of JSoko and YASS material (before this document), so the article authors cannot deny having read this statement in [4]. Consequently, the article authors are acquainted with the document [4].

4.4.3.
The push-optimality statement in [4] is buried deeply inside the document, far away from its sections with headlines indicating that the section is about PI-corrals. This means the article authors cannot feign stupidity by saying they have merely skimmed the sections in [4] about PI-corrals and misunderstood it all. In that case, the article authors would not have stumbled over the push-optimality statement in [4].

4.4.4.
The other way around, the article authors cannot feign stupidity by saying that they by happenstance stumbled over the push-optimality statement in [4], but did not read the sections about PI-corrals in that document, and suffered from a misconception acquired elsewhere about, what a PI-corral is.

Feigning stupidity that way is impossible because the push-optimality statement in [4] appears in connection with a thorough and unmistakable PI-corral definition (see Q), which even has the sentence "no outside boxes on the board blocks the player's access to the corral boxes". 

Notwithstanding minor grammatical errors in that sentence, it unmistakably refutes the article authors' claim of having discovered and added anything. That sentence loudly and clearly explains that the three diagonal boxes in the article authors' "Fig. 3" create an I-corral, not a PI-corral. The article authors have read that sentence, and yet they go ahead and make false postulates about the Sokoban community not knowing the difference between I-corrals and PI-corrals.

That the article authors have read the "no outside boxes..." sentence follows from the following fact.

4.4.5.
Unknowingly, the article authors make a full confession of having read not just the push-optimality sentence in [4], but also the context in which it occurs. Saying "They claim without proof", as the article authors do, logically implies having checked that the push-optimality sentence in [4] is not accompanied by a proof. As a bare minimum, the article authors' statement entails having read the sentence in its context, and having observed that the sentence is not accompanied by a proof in the near neighborhood.

The sentence "no outside boxes on the board blocks the player's access to the corral boxes" appears in the near neighborhood as a part of the context of the push-optimality sentence (see Q). Consequently, the article authors cannot deny having read the "no outside boxes..." sentence.

(In a proper academic article, saying "They claim without proof" even logically implies having checked that there is no such proof anywhere in the entire document [4], or in any other publication by the authors of JSoko and YASS. Otherwise, the claim would have been moderated by saying that it is document [4] which does not contain such a proof.)

4.4.6.
The article says:
:: the results found by the community point to the effectiveness of this approach 

Given the context, and the lack of references to other material with a treatment of PI-corrals, "the community" is also here a reference to the authors of the JSoko and YASS material, in effect Mr. Meger and me. Again, the only material to which this statement is applicable is my "Scribbles" document [4]. It contains cursory statistics, showing the effects of PI-corral pruning for a set of 107 small puzzles (see P). The statistics appear twice in the document.

But both appearances of the statistics are located far from them quotation listed in 4.4.2. Consequently, the article authors cannot feign myopia and stupidity, i.e., claiming they have only read a small and specific section of [4], and misunderstood it all. 

The article authors must have read the document [4] practically in its entirety. This means the article authors have read not just one, but a number of independent PI-corral descriptions spread across the document, including several example diagrams showing the differences between I-corrals and PI-corrals (see R). 

4.4.7. 
To summarize, there is irrefutable evidence (4.4.2), proving that the article authors have read at least one of the unmistakable descriptions of PI-corrals in document [4]. In particular, the article authors have read the PI-corral description which contains the sentence "no outside boxes on the board blocks the player's access to the corral boxes" (see Q), a sentence which loudly and clearly refutes the article authors' claim of having discovered the PI-corral concept themselves. 

Furthermore, there is irrefutable evidence (4.4.2, 4.4.6), proving that the article authors have read the document [4] practically in its entirety. This means the article authors have seen more than one description of PI-corrals, and the article authors have seen examples clearly showing the differences between I-corrals and PI-corrals (see R).

4.4.8.
This adds up to, that the article authors have seen several and unmistakable descriptions of the difference between I-corrals and PI-corrals, but despite of that, the article authors have the nerve falsely to accuse the Sokoban community represented by Mr. Meger and me of not being aware of the difference. That is what the article authors do when they write:

:: Although the results found by the community point to the effectiveness 
:: of this approach, it doesn’t guarantee optimality, as shown by Figure 3. 

In technical terms, the corral created by the three diagonal boxes in the article authors' "Figure 3" is not a PI-corral but just an I-corral. So after provenly having read more than one unmistakable PI-corral description in document [4], the article authors paint a completely different picture of what a PI-corral is. 

It is inconceivable that such a misrepresentation should be the result of a misunderstanding by as many as four article authors. The misrepresentation can only be the result of lying. Just for comparison, the documents [2] and [3] show that other authors have had no problems reading and understanding the document [4] correctly (see H, I).

The only possible motivation for deceiving the unwary reader of the article this way, is to give the false impression that the article authors have discovered PI-corrals themselves. That is what the article authors falsely claim when they continue:
 
:: DDMP takes the main concept of PI-corrals and adds an extra restriction 
:: that guarantees optimality of the solution of a solver equipped with such 
:: domain-dependent technique.

The "DDMP" term in this quotation is nothing but obscuring mumbo jumbo for "PI-corrals". The "PI-corral" term in the quotation is falsely used to denote I-corrals, like the one created by the three diagonal boxes in "Figure 3". After cleansing this statement for all its deceptions, it is just a statement about (not a definition of) PI-corrals:

:: PI-corrals takes the main concept of I-corrals and adds an extra restriction 
:: that guarantees optimality of the solution of a solver equipped with such 
:: domain-dependent technique.

______________________________
4.5. Circumstantial Evidence

__________________
4.5.1. Stupidity

4.5.1.1
Are we really to believe that with as many as four article authors, nobody understood the descriptions of I-corrals and PI-corrals in document [4] correctly?

The document [4] is the article authors' primary source of information, and they have provenly read is practically in its entirety (see 4.4). Even though the document clearly is written by someone (me) with less than perfect command of the English language, nobody else seems to have problems with the description. Mr. Klavik's technical report [2] and Mr. Virkkala's master's thesis [3] are good examples of that (see H, I).

4.5.1.2
Are we really to believe that with as many as four article authors, nobody got the thought to do what every normal and intelligent person would do?

The article says:
:: They claim without proof that this technique, as presented, 
:: maintains optimality of the solution. But, as we can see 
:: in Figure 3, this is not true.

If the article authors really thought that JSoko and YASS suffered from such a serious flaw as described in the article, then any normal and intelligent person, who also works with programming, would at some point during the article writing process get the thought that it would be a good idea to inspect the readily available source code, to see if that really could be true. 

As documented in section 4.1.3, it is impossible to inspect the relevant source code without noticing the comments, which loudly and clearly show that both projects implement the full and correct PI-corral pruning algorithm. 

4.5.1.3
Are we really to believe that with as many as four article authors, nobody found it strange that the PI-corral pruning algorithm from the Sokoban community works at all, and even works well, if it worked the way the article authors say it does?

According to the article authors, the Sokoban community has only implemented "I-corral pruning", pruning game positions based on I-corrals, not PI-corrals (see 4.2, 4.3). When this algorithm finds an I-corral on the board, then all pushes are pruned, except the pushes leading into the I-corral. It is this algorithm which for the sake of clarity is called "the weak algorithm" in the "Informal Overview" (see X), as opposed to "the strong algorithm" which is the PI-corral pruning algorithm.

The article says:
:: Although the results found by the community point to the effectiveness 
:: of this approach, it doesn’t guarantee optimality, as shown by Figure 3. 

The consequence of the alleged flaw is not just a failure to honor a push-optimality guarantee. I-corral pruning amounts to implementing an uninformed forward pruning of the game positions. The pruning is uninformed because pushes are pruned, not because of an estimated inferior value, but just because they happen not to go into an I-corral. 

Forward pruning makes the search incomplete, so there is a risk of pruning some, or even all solution paths, making it more difficult or even impossible to find a solution. Given how difficult it has been in other search domains to make informed ("intelligent") forward pruning work satisfactory (see W), it sounds improbable that an uninformed ("blind") I-corral forward pruning suddenly should work successfully in the Sokoban game. The idea seems so unlikely to succeed, that nobody has tried it yet and published the results.

The article authors must have been aware of the perils of forward pruning, and they must have wondered if it really could be true that "the results found by the community point to the effectiveness of this approach", as the article authors write. 

If the article authors really thought that JSoko and YASS claimed getting good results by using something so unusual as a forward pruning algorithm, then any normal and intelligent person, who also works with programming, would at some point during the article writing process get the thought that it would be a good idea to inspect the readily available source code, to see if that really could be true. 

As documented in section 4.1.3, it is impossible to inspect the relevant source code without noticing the comments, which loudly and clearly show that both projects implement the full and correct PI-corral pruning algorithm.

__________________
4.5.2. Indecency

Are we really to believe that with as many as four article authors, nobody got the thought to do what every decent person would do?

JSoko and YASS are currently among the three best existing solvers, and if the article authors really thought these solvers suffered from such a serious flaw as described in the article, then any normal and decent person would at some point during the article writing process get the thought, that the only just thing to do, was to alert the authors of JSoko and YASS, in particular because the article authors knew their article would be underway for quite some time, and that it would appear with restricted access behind a paywall. 

All it takes, is to send an email, or to send the article after it was finished. Both projects are on the article's list of references, so the article authors have had direct access to the relevant email addresses. No such communication has been received (see T).

________________________________________
4.5.3. Timo Virkkala's Master's Thesis

Are we really to believe that the article authors have not read such a prominent document as Mr. Timo Virkkala's master's thesis from 2011 [3], including its well-written PI-corral description and statistical results?

The article authors have written other articles about Sokoban (albeit some with so infinitesimally little content, that the articles for a practitioner in the field look like jokes, like halfhearted, uninspired work just written to meet some academic minimum research quota), and as could be expected, the article authors are very well informed and up-to-date about Sokoban literature and programs. For instance, the article authors list references to the three currently best known solver programs, dated 2013 (see S).

It is not every year that Sokoban gets such a comprehensive treatment, and when it happens, it is something which everybody working with Sokoban solver programming will notice, if not immediately then certainly long before the article authors published their PI-corral article.

For instance, there has been a link to this master's thesis from Wikipedia's Sokoban page since 2014-09-24. A plain web search for material related to Sokoban has surely linked to this thesis long before that time (see V).

___________________________________
4.5.4. DDMP instead of PI-corral*

Are we really to believe that the name "DDMP" is not a carefully chosen smoke screen, obscuring the fact that the article authors just have renamed the PI-corral pruning algorithm?

The article says:
:: DDMP takes the main concept of PI-corrals and adds an extra restriction [...]

In computing, there is a long tradition for a certain naming convention in such a case. The convention is to append an asterisk, i.e., "*", to the name of the base concept. In this case, the natural name for such a new concept would be PI-corral*, if it existed.

The article authors are very well aware of this naming convention. They use it themselves in [13] when they write:

:: The Rolling Stone (RS) solver 
:: [...]
:: There is also an admissible version of RS (which we call RS*). 

Instead of talking about "DDMP stones", "the criteria of DDMP", etc., as their PI-corral article does, the term "PI-corral*" would have been more descriptive, e.g., "PI-corral* stones", "the criteria of PI-corral*", etc.

It is impossible not to get the thought, that the article authors deliberately have chosen otherwise. The "DDMP" name is obscure, and the article is hidden behind a paywall. The article authors could get whatever academic credits they have received for the article, with practically no risk of anyone from the Sokoban community reading it, and even if somebody did, practically nobody would notice that something is wrong, and even if somebody did, practically nobody would care enough about it to make objections.

_______________
4.6. Cover-up

As documented in section 4.4, the article authors misrepresent the PI-corral idea, despite the fact that the article authors provenly have read several detailed and unmistakable descriptions of the idea in document [4].

Naturally, the article authors will feign stupidity and say that they just have misunderstood everything. But not even the four article authors can be so unintelligent. After all, they have been able to write a computer program (albeit a flawed one, if it adheres to their own algorithm description) to produce the statistical data for their article. 

A plausible explanation is that the article authors are lying about PI-corrals in order to present the idea as their own. As documented in section 4.5, there is also sound circumstantial evidence to support that conclusion.

In case of lying, it follows logically that the article authors are not interested in making it easy for the article readers to see what is going on. The article is constructed precisely as it should be for making a perfect cover-up after lying.

4.6.1.
No material with a description of PI-corrals has been put on the article's list of references. By checking such a reference, the article readers would see immediately what is wrong with the article, i.e., that it is built around the misstatements listed in the "Summary" section, repeated here for convenience:

1.6. The Sokoban community has only discovered I-corrals, not PI-corrals.
1.7. The Sokoban community has falsely attributed PI-corral pruning properties (admissibility) to I-corrals.
1.8. The article authors have rectified this error by discovering PI-corrals.

Naturally, article readers may find other documents about PI-corral pruning on their own initiative, but the next step in the cover-up makes it appear unnecessary to look further for such a verification of the basics presented in the article.

4.6.2.
The next step in the cover-up is to put the two projects JSoko and YASS on the article's list of references. That is a very clever move, when the purpose is deception. These two projects do indeed implement PI-corral pruning, so the article authors can begin with the true statement:

:: In the Sokoban community, notably in the solvers JSoko [11] and YASS [12], 
:: we can find a domain-dependent technique called PI-corral.

Since there are no other solvers on the article's list of references, this gives the article reader the false impression that all statements in the article like "they argue..." and "They claim..." can be substantiated by checking the JSoko and YASS material. 

If the article readers look at that material, they will be a little puzzled by not finding PI-corrals mentioned anywhere, but then the readers will just conclude, that the article authors have used "they" in a broader sense, as a reference to even more, but unspecified, source material from the Sokoban community.

A tenacious article reader may dig a little deeper after not having found anything about PI-corrals in the JSoko and YASS material. This reader finds out that both projects implement PI-corral pruning correctly, just without ever using the term "PI-corral". But this reader will just conclude that both projects in the meantime have been updated in accordance with the discoveries made by the article authors. 

This makes the deception complete.

_________________
5. Incompetence

_______________________
5.1. Flawed algorithm

The article says:
:: In our approach, a subset of stones in a state is DDMP-applicable
:: if all of its elements have three characteristics: 
:: i) they are frontier of an unreachable zone; 
:: ii) they only can be moved into this zone; 
:: iii) they are accessible.

This is a flawed algorithm. One additional constraint is necessary before the algorithm is admissible, as promised by the article authors. The missing constraint is:

5.1.1. At least one of the boxes in the subset is not located at a goal square.

This constraint has always been an integral part of the PI-corral pruning algorithm (see I, J). The article authors have the nerve falsely to accuse the original discoverer of PI-corral pruning and me of lack of insight by mistaking I-corrals for PI-corrals in our implementations of PI-corral pruning. Therefore, it is ironic and hilariously amusing that the joint effort of the four article authors just results in a flawed implementation of PI-corral pruning.

Note that the article authors cannot defend themselves here with lame excuses by referring to their "Formal Definition" section, which may or may not cover the additional constraint; that is irrelevant. The quotation, with its three and not four characteristics, is the article authors' determinative algorithm definition, and as such it is obligated to be a full and correct definition.

Note also, that the article authors cannot defend themselves here with the lame excuse, that the three characteristics amount to a description of a PI-corral (see 2.2.4). The word "DDMP-applicable" in the quoted text implies that the intention is to describe the algorithm, i.e., PI-corral pruning (see 2.2.5), not the underlying PI-corrals (see 2.2.4).

__________________
5.2. No Research

It is wrong to say that the article authors have made no research. They certainly have, e.g., by reading [4] (see 4.4), but they do not tell about it, and they misrepresent what they have read (e.g., see 4.2).

But let us for a moment assume, that the article authors acted in good faith and honestly believed that the Sokoban community had only discovered I-corrals and not PI-corrals. If that scenario was true, then the article would be so poorly researched that it could only be called a display of completely unacceptable ineptitude, and a completely unacceptable failure by the article authors to live up to basic academic standards for the following reasons.

5.2.1.
The article authors have not searched for, read, or referenced the existing material about PI-corrals. In particular, the article authors cannot have read the documents [2], [3], and [4]. Reading just one, anyone, of them would immediately have extinguished any misconception the article authors might have had about discovering PI-corrals themselves (see H, I, J).

5.2.2.
The article authors have not lifted a finger to check the veracity of their false postulates about JSoko and YASS. A quick look at the projects' material would immediately have revealed that JSoko and YASS implement PI-corral pruning correctly.

_______________
6. Conclusion

6.1.
It is a false statement on two counts, when the article authors say in their conclusion:

:: We have proposed an approach to make an important Sokoban’s community insight admissible.

6.1.1.
It is untrue that the article authors have added anything on top of "an important Sokoban's community insight". 

The mentioned insight from the Sokoban community is Mr. Meger's PI-corral pruning algorithm. The article authors misrepresent that idea by saying that the Sokoban community has only discovered I-corrals, not PI-corrals, and then the article authors have the nerve falsely to claim having discovered PI-corrals and the PI-corral pruning algorithm themselves (4.4.8).

6.1.2.
It is untrue that the article authors have proposed an admissible pruning algorithm.

The algorithm presented by the article authors is flawed. It misses a constraint like "at least one corral box is not at a goal square" before it can live up to the admissibility promised by the article authors. Adding such a constraint makes it a correct PI-corral pruning algorithm.

6.2
The article authors have provenly read the document [4] practically in its entirety (4.4). There is nothing in the article indicating that the article authors have other sources of information about PI-corrals than [4], but even so, the article authors hide that fact from the article readers by not putting that document on the article's list of references. This makes it impossible for the article readers to check the veracity of the article authors' false accusations about flaws and shortcomings in the original PI-corral idea.

6.3.
The article authors have provenly seen sentences like "no outside boxes on the board blocks the player's access to the corral boxes" in document [4] (4.4.4), which notwithstanding minor grammatical errors, unmistakably explains the crucial difference between I-corrals and PI-corrals, and yet the article authors shamelessly misrepresent it all, saying that the Sokoban community has only discovered I-corrals, not PI-corrals (4.4.8). 

It is inconceivable that such a misrepresentation should be the result of a misunderstanding by as many as four article authors. The misrepresentation can only be the result of lying. For comparison, the documents [2] and [3] show that other authors have had no problems reading and understanding the document [4] correctly (see H, I).

6.4.
People, who think the article authors are just incredibly stupid and have misunderstood everything, must acknowledge the following facts.

6.4.1. The article is constructed precisely as it should be for making a perfect cover-up after stealing and lying (4.6). 

6.4.2. There is sound circumstantial evidence indicating that the article authors are stealing and lying (4.5).

By also taking all the falsities in the article into account, it all sums up to that it is a consistent and legitimate conclusion that the article authors are stealing and lying, even though some readers of this document may disagree with that conclusion.

6.5.
People, who think the article authors are just incredibly stupid and have misunderstood everything, must also acknowledge the following facts.

6.5.1. If the article authors have misunderstood everything, then the article does not live up to basic academic standards (5.2).

It should be noted that "not live up to basic academic standards" is an euphemism for absolutely zero research (5.2.1), for a non-existing fact validation (5.2.2), for false accusations against the authors of JSoko and YASS (4.3), and for other forms of despicable behavior (4.5.2).

6.5.2. The article's falsities and the injustice done primarily to Mr. Meger, but also to me, are scandalous, no matter what the cause is.

6.6.
A great injustice has been done to Mr. Meger. PI-corral pruning is his brilliant idea, and it is exactly his idea which the article authors have the nerve to call their own, but first after adding insult to injury by falsely postulating, that Mr. Meger and I lack insight and have attributed PI-corral pruning properties (admissibility) to I-corrals.

I can only imagine what Mr. Meger must feel about all this. He can and will surely speak for himself, if and when he finds it worthy to comment on this matter. 

My personal interest in raising this complaint is, that the article also does injustice to me. The article authors falsely accuse me of being so unintelligent that I have not noticed and understood the difference between I-corrals and PI-corrals, and that I have attributed PI-corral pruning properties (admissibility) to I-corrals. 

The false accusations are not even the worst part of it. What really fills me with rage is, that the readers of the article have no chance of finding out that the accusations are false. If only the document [4] had been on the article's list of references, then the article readers could at least find out, that it is the article authors who are either so incredibly stupid that they have misunderstood everything, or they are stealing and lying.

I will not put up with, when I am dead and gone, to be a footnote for all eternity in a botched up academic article, which basically says that I was an unintelligent idiot, for the wrong reasons!

6.7.
The article authors must see to it, that all the following actions are performed immediately.

6.7.1. The article must be taken out of circulation.
6.7.2. The article must be requested to be forgotten by all internet search engines.
6.7.3. The article must be requested to be forgotten by all other known indices, résumés, etc.

_______________
7. References
____
7.1. References - Texts

[1]
Title:
  Solving Sokoban Optimally with Domain-Dependent Move Pruning
Authors:
  Leme, Renato R. 
  Pereira, André G.  
  Ritt, Marcus  
  Buriol, Luciana S. 
Published in:
  2015 Brazilian Conference on Intelligent Systems (BRACIS) 
Date of Conference:
  4-7 Nov. 2015
Page(s):
  264 - 269 
INSPEC Accession Number:
  15836334 
Conference Location:
  Natal 
DOI:
  10.1109/BRACIS.2015.47 
Publisher:
  IEEE 
URL retrieved 2016-04-20:
  http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=7424030&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D7424030

[2]
Title:
  Sokoban Solver — a short documentation
Author:
  Klavik, Pavel 
URL retrieved 2016-04-20:
  http://pavel.klavik.cz/projekty/solver.html

[3]
Title:
  Solving Sokoban 
Author:
  Virkkala, Timo
URL retrieved 2016-04-20:
  http://weetu.net/Timo-Virkkala-Solving-Sokoban-Masters-Thesis.pdf

____
7.2. References - Webpages

[4]
Title:
  Sokoban solver "scribbles" by Brian Damgaard about the YASS solver
Author:
  Damgaard, Brian
URL retrieved 2016-05-18:
  https://web.archive.org/web/20160518031312/http://sokobano.de/wiki/index.php?title=Sokoban_solver_%22scribbles%22_by_Brian_Damgaard_about_the_YASS_solver
Original URL retrieved 2016-04-20:
  http://sokobano.de/wiki/index.php?title=Sokoban_solver_%22scribbles%22_by_Brian_Damgaard_about_the_YASS_solver

The text found on the original webpage is subject to change. The foundation for this document is the version saved on the web archive. It is the current version as of 2016-05-18. Its date is 2014-09-28. The first registered version of the text has the date 2010-02-01. There are 12 intermediate versions. Apart from minor corrections and additions, nothing has changed between these two dates. In particular, nothing related to PI-corrals and the text segments referenced from this document has changed, except perhaps for the correction of one or two minor and obvious spelling errors.

[5]
Wikipedia - Sokoban
URL retrieved 2016-04-20:
  https://en.wikipedia.org/wiki/Sokoban

[6]
JSoko Website
URL retrieved 2016-04-20:
  http://www.sokoban-online.de

[7]
JSoko Solver Program 
URL retrieved 2016-04-20:
  https://sourceforge.net/projects/jsokoapplet/

[8]
YASS Solver Program
URL retrieved 2016-04-20:
  https://sourceforge.net/projects/sokobanyasc/

[9]
Sokoban Solver, by Pavel Klavik
URL retrieved 2016-04-20:
  http://pavel.klavik.cz/projekty/solver.html

[10]
Sokoban Wiki
URL retrieved 2016-04-20:
  http://www.sokobano.de/wiki/

[11] 
11 is the reference number from the article to [7] 

[12]
12 is the reference number from the article to [8] 

[13]
Title:
  Solving Sokoban Optimally using Pattern Databases for Deadlock Detection
Authors:
  André G. Pereira, Marcus Ritt, Luciana S. Buriol
URL retrieved 2016-05-12:
  http://www.lbd.dcc.ufmg.br/colecoes/eniac/2014/0090.pdf

_____________
8. Exhibits

_____
(A) : First description of the PI-corral pruning mechanism 
      (In puzzle diagrams, empty floor squares have been changed from [Space] to "-".)
____
A.1. German Original (English translation follows below)

From: mmeger[...]
To: "Brian Damgaard" [...]
Subject: 
Date: Wed, 18 May 2005 06:45:20 +0800


Hi Brian!
[...]

Mittlerweile habe ich aber eine ganz andere, neue Idee, mit der ich
mich beschäftige:
Ich habe angefangen Penaltys zu berechnen. Die angehängte Version
kann bereits sehr einfache Penaltys erkennen. Wenn also z.B. alle
Zielfelder in einem Bereich sind wie in diesem  Beispiellevel, dann
wird ein Penalty von 2 errechnet:
########
#--#---#
#.-#---#
#.--$$-#
#--#---#
#--#-@-#
########

Solche Penaltys sind nur in wenigen Leveln zu finden. Ich habe
diese Erkennung auch nur programmiert, damit ich eine Basis habe.
Rolling Stone hat sehr komplexe Penaltyberechnungen und ich wollte
erst mal mit etwas einfachem anfangen. Du kannst Dir die
Penaltyfelder in einem Level folgendermaßen anzeigen lassen: Debug
-> Zeige Penaltyfelder

Nun zu meiner neuen Idee:
Während ich über Penaltys nachdachte, habe ich auch über die
folgende Stellung nachgedacht:
####
#--##
#---#
#---#
##$$#
#---#
#-$-#
.....

In diesem Fall habe ich gedacht, müsste ich ein Penalty von 4
errechnen. Das würde die Stellung in der Suche 2 Iterationen weiter
nach hinten schieben und damit ggf. ganz aus der Suche schieben (da
vielleicht schon in der nächsten Iteration die Lösung gefunden
wird).
Solche Corrals haben aber noch eine andere Eigenschaft: Alle
weiteren Pushes der Corralkisten führen IN das Corral. Damit können
sie unmöglich andere Kisten im Level negativ beeinflussen. Eine der
beiden Kisten muss also während der Lösungssuche irgend wann auf
jeden Fall um ein Feld nach oben geschoben werden.
Normalerweise würde mein Solver alle möglichen Verschiebungen aller
DREI Kisten (und falls es 30 Kisten im Level gibt aller 30 Kisten!)
für den nächsten Zug in Betracht ziehen. Da aber feststeht, dass
eine der beiden Kisten im Corral auf jeden Fall nach oben
verschoben werden muss und diese Verschiebung die anderen Kisten
nicht stört sind für den nächsten Push nur die beiden Corralkisten
zu berücksichtigen!
Wird nun eine der beiden Kisten nach oben verschoben:
####
#--##
#---#
#-$-#
##-$#
#---#
#-$-#
.....

so entsteht wieder ein Corral. Erneut müssen für den nächsten Push
nur die beiden Corralkisten überprüft werden! Dies kann den
Suchbaum in bestimmten Situationen um viele Stellungen verkürzen.
Diese Verkleinerung des Suchbaums ist vergleichbar mit Tunneln.
Wird eine Kiste in einen Tunnel geschoben, so muss als nächstes
auch nur der Push der Kiste im Tunnel berücksichtigt werden und
nicht alle möglichen Pushes aller anderen Kisten.

Ich habe mir als ersten Ansatz folgende Kriterien überlegt:
1. Es gibt ein Corral
2. Das Corral kann nur durch mindestens 2 Pushes aufgelöst werden
3. Der Spieler kann alle Corralkisten so verschieben, wie er sie
auch während der Corralprüfung verschieben kann (während der
Corralanalyse werden ja alle verschiebbaren Kisten, die nicht zum
Corral gehören vom Feld genommen, so dass der Spieler eventuell
mehr Möglichkeiten hat als in der Originalstellung, in der ja alle
Kisten auf dem Feld sind)

Falls alle drei Kriterien zutreffen, muss der Solver für den
nächsten Push nur die Corralkisten berücksichtigen!

Das interessante ist, dass alle drei Bedingungen nicht sehr
kompliziert zu programmieren sind, da die Corralprüfung ja sowieso
durchgeführt wird. Falls diese Idee funktionieren sollte könnte man
die drei Bedinungen eventuell noch verfeinern.

Falls Du mal eine Pause von Deiner Sokobanpause machen solltest 
wäre es nett, wenn Du mir schreiben könntest, ob Du einen
Denkfehler in dieser Idee gefunden hast oder ob Du glaubst, dass
das ganze funktionieren könnte.
Ich werde das ganze wohl mal ausprobieren.

____
A.2. English Translation, by Brian Damgaard
Notes about the translation:
* The translator is neither a native English speaker nor a native German speaker. 
* The translation attempts to mirror the original text and its meaning as closely as possible. Proper English is only of secondary importance. 

From: mmeger[...]
To: "Brian Damgaard" [...]
Subject: 
Date: Wed, 18 May 2005 06:45:20 +0800

Hi Brian!
[...]
But meanwhile, I've got a new and completely different idea, which I've worked on lately:
I had begun to calculate penalties. The attached version can already calculate very primitive penalties. So, for instance, with all goal squares in a zone like in this example, the calculated penalty is 2:

########
#--#---#
#.-#---#
#.--$$-#
#--#---#
#--#-@-#
########

This specific type of penalties rarely occurs in puzzles. Thus, I have only implemented this pattern in order to have something to start with. Rolling Stone has much more complicated penalty calculations, and I wanted to start with something simpler. You can make the penalty squares in the puzzle visible by using this option: Debug -> Show penalty squares.

Now to my new idea:
While I thought about the penalties, I also considered this game position:
####
#--##
#---#
#---#
##$$#
#---#
#-$-#
.....

In this case, I thought, I should compute a penalty of 4. That would push the position 2 search iterations further down, and thereby maybe eliminate it completely from the search (because the next iteration might find a solution).

But corrals of this type have yet another property: All the next pushes of the corral-boxes go INTO the corral. Consequently, they cannot have a negative influence on the other boxes in the puzzle. Thus, at some point during the search, at least one of the boxes must be pushed one square upwards.

Normally, my solver would generate and consider all legal pushes for all THREE boxes (and if the puzzle has 30 boxes, then for all 30 boxes!). But since it is certain, that at least one of the boxes in the corral must be pushed upwards, and this push does not incommode other boxes, then only the two corral-boxes need to taken into account as candidates for the next push! 

If one of the two boxes now is pushed upwards:
####
#--##
#---#
#-$-#
##-$#
#---#
#-$-#
.....

then yet another corral appears. Again, only the two corral-boxes need to be taken into account as candidates for the next push! In some game positions this can reduce the search tree with a great many positions. This type of search tree pruning can be compared with tunnels. When a box is pushed into a tunnel, then it also suffices to take this box into account as candidate for the next push, not all possible pushes for all other boxes.

As a starting point, I have considered the following criteria:

1. There is a corral
2. The corral can only be opened by at least 2 pushes
3. The player can push all the corral-boxes exactly as they also can be pushed during the corral-analysis (during the corral-analysis, all boxes which do not belong to the corral are removed from the board, hence, it may be so, that the player has more possible pushes than he/she has in the original game position, where all the boxes are on the board)

If all three criteria are met, then the solver needs only consider the corral-boxes as candidates for the next push!

What makes it interesting is, that it is not that complicated to program these three criteria, given that the corral-analysis is performed anyway. If it turns out that this idea works, then maybe it will be possible to refine the three criteria further.

Just in case you take a pause from your Sokoban-pause, I will appreciate it, if you will write back, telling if you have found a logical flaw in this idea, or if you think it could work. I will probably give the whole thing a try. 

_____
(B) : Date of Publication of "Sokoban Solver — a short documentation" 
The PDF document [2] has the date 2010-07-29, and Mr. Pavel Klavik, the author, has informed me by email that the project and the document were published on the internet shortly thereafter.

_____
(C) : The term "PI-corral" is neither used nor described in JSoko and YASS project material

C.1. JSoko
The word "PI-corral" appears exactly twice in JSoko project material.

C.1.1.
The word "PI-corral" appears in a list of references found in the file JSoko/src/development/References.txt. The word appears in connection with a reference added more than 5 years after the development of the algorithm:

:: Publications that reference JSoko
::	--> http://larc.unt.edu/techreports/LARC-2011-01.pdf
::	--> http://weetu.net/Timo-Virkkala-Solving-Sokoban-Masters-Thesis.pdf (PI-corral detection of JSoko)

The article authors cannot use this occurrence of the word to claim having found information about PI-corrals in JSoko material for the following reasons. 

C.1.1.1.
The sentence does not say anything about what a "PI-corral" is, and it is not connected to anything else in the project material. 

C.1.1.2.
The sentence is grammatically incorrect ("of" should presumably be "in"), making it unclear what it means, hence a proper academic treatment of this piece of information requires at least a minimum of further investigation, which in this case means inspecting the referenced document. The referenced document is Timo Virkkala's master's thesis "Solving Sokoban" [3], and it is logically impossible for the article writers to read its description of PI-corrals, and then claim having developed the same idea themselves.

C.1.1.3.
The article authors cannot use [3] to infer that JSoko implements PI-corral pruning since JSoko is neither mentioned nor referenced in [3] (see D). So when JSoko lists [3], saying that [3] contains a reference to JSoko, this is not really so. What [3] does, is to describe Mr. Meger's PI-corral pruning idea, with a reference to [4] as source of information.

C.1.2.
The word "PI-corral" appears in the title of a test puzzle in the file JSoko/testlevel/Solver testlevel/Tunnel.sok. The file contains several small test puzzles, and one of them has the title "Tunnel durch Freeze (PI-Corral erkennt das)". This title consists of a mixture of German and English words, and the Sokoban technical term "PI-corral". The title does not aspire to form a grammatically correct German sentence, even if the English word "Freeze" is translated to German. The title is more a quick note which explains the purpose of the test puzzle. The portion of the title related to PI-corrals translates literally to "(PI-corral detects it)". 

The article authors cannot use this occurrence of the word to claim having found information about PI-corrals in JSoko material for the following reasons. 

C.1.2.1.
The sentence does not say anything about what a "PI-corral" is, and it is not connected to anything else in the project material. 

C.1.2.2.
Maybe common sense reasoning allows the reader to infer from the sentence, that JSoko implements PI-corral pruning, even though it strictly speaking is not what the sentence says. But because of the small uncertainty, a proper academic treatment of such a derived piece of information requires a confirmation found elsewhere in the material, and there is none.

C.2. YASS
The word "PI-corral" does not appear anywhere in YASS project material.

_____
(D) : YASS implements PI-corral pruning
[3] (Timo Virkkala's master's thesis "Solving Sokoban") p. 28-29:

:: The YASS solver contains a technique that hasn't yet been documented in scientic literature [Dam10].
:: [...]
:: This is called PI-corral pruning.

_____
(E) : YASS implements PI-corral pruning
[4]: (Brian Damgaard's "Scribbles") The existence of statistical results implies that the algorithm has been implemented:

:: this new technique is itself able to prune at least 20% of the search tree according to my experiments, 
:: and empirically the savings always outweigths the extra costs. 

_____
(F) : JSoko implements PI-corral pruning
[4]: (Brian Damgaard's "Scribbles") The readers may get the impression that Mr. Meger has implemented PI-corral pruning, even though it strictly speaking cannot be known with certainty without checking it:

:: I've had a correspondence with Matthias Meger for some time regarding Sokoban solvers 
:: and deadlock detections, and recently, he had a stroke of genius and discovered a 
:: completely new pruning technique for a solver!

_____
(G) : "Sokoban Solver — a short documentation" mentions YASS
[2] p. 1:

:: We are also grateful the authors of [2],  especially the correspondence 
:: with the author of the solver YASS was very useful. 

The reference [2] in the quotation is the reference [10] in this document.

_____
(H) : PI-corral and PI-corral pruning definition from "Sokoban Solver — a short documentation"
[2] p. 2: 

:: Most of the time, there are locations, called corrals, that are inaccessable 
:: for Sokoban. A corral is called PI-corral if all the boxes on its border can 
:: be pushed only inside and all the moves are possible right now, not blocked 
:: by another box.
:: [...]
:: If the position inside a PI-corral is not solved yet, we have to push a box 
:: on its border, sooner or later. 

_____
(I) : PI-corral and PI-corral pruning definition from "Solving Sokoban"
[3] p. 28: (PI-corral definition)

:: They call a zone that the player cannot access a corral. 
:: If all the stones on the barrier can only be pushed into the zone, 
:: the corral is an I-corral. Furthermore, if the player can reach all 
:: the stones on the barrier and perform the legal pushes inwards the 
:: corral is a PI-corral.
:: [...]
:: So, if the corral has to be dealt with eventually, it is best to 
:: deal with it right away and all other moves can be eliminated 
:: from consideration. This is called PI-corral pruning.

_____
(J) : PI-corral and PI-corral pruning definition from "Scribbles"
[4]: 

:: An "I-corral" is a corral where all boxes in the outer fence only can 
:: move inwards in their first move. 
:: [...]
:: A "PI-corral" is the important sub-class of the I-corrals where the 
:: player can reach all the outer corral boxes and perform all their 
:: legal inwards moves.
:: [...]
:: Unless all boxes in the corral are sitting on goal-cells, then the player 
:: must sooner or later do something about the corral, that is, the player 
:: must push at least one of the boxes in the fence.

_____
(K) : Corral-pruning comments in JSoko source code
[7]: 
	 * Identifies the boxes which are relevant for the search.
	 * If a corral occured it is possible that not all boxes are releveant for the search.
	 * E.g. in the following situation:[...]
	 * ####
	 * #  #
	 * #  #
	 * #$$#[...]
	 * only these two boxes are relevant, since they must be pushed anyway, and cannot
	 * block other boxes in doing so.
	 * <p>
	 * Conditions:
	 * <ol>
	 * <li>There must be a corral</li>
	 * <li>all possible pushes of the corral boxes must go into the corral</li>
	 * <li>not all corral boxes are located on goals</li>
	 * <li>the player can perform already now all theoretically possible legal pushes
	 *     (not generating a deadlock) into the corral</li>
	 * </ol>

_____
(L) : Corral-pruning comments in YASS source code
[8]:
          // find:
          // 1. floor squares in the "pocket" that the player cannot reach, and
          // 2. inner boxes and boxes surrounding the "pocket";

          [code block]  
          
          // check that corral-boxes only can be pushed inwards
          // and that all these pushes are possible in the current position

_____
(M) : "They" refers to the authors of JSoko and YASS material

The article says:

:: In the Sokoban community, notably in the solvers JSoko [11] and YASS [12] [...]
:: As they argue [...]
:: They claim [...]

M.1.
At the very least, the JSoko and YASS material, in effect the project authors, must be members of "they". This follows from the fact that JSoko and YASS are mentioned this way at all, even emphasizing them by using the word "notably". 

M.2.
If the article authors did not mean to say that also JSoko and YASS suffer from the alleged shortcomings and flaws, then the article authors would surely have written which other projects and authors this "they" was referring to. 

M.3.
If the article authors did not mean to say that also JSoko and YASS suffer from the alleged shortcomings and flaws, then the article authors would have had a heavy obligation not falsely to accuse the authors of JSoko and YASS of making errors, if the article authors in reality meant somebody else.

M.4.
The JSoko and YASS projects are the only sources mentioned on the article's list of references which deal with PI-corral pruning. 

_____
(N) : "Argue" and "claim" are references to material with a line of reasoning

The article says:

:: In the Sokoban community, notably in the solvers JSoko [11] and YASS [12] [...]
:: As they argue [...]
:: They claim [...]

N.1. Argue
A dictionary lookup establishes the fact that "argue" is a reference to material with a line of reasoning.

N.1. Argue
Dictionary lookup, 2016-05-01
http://www.thefreedictionary.com/argue 

argue
[...]
v.intr.
1. To put forth reasons for or against something

N.2. Claim
A dictionary lookup of "claim" does not in itself establish the fact that "claim" is a reference to material with a line of reasoning. 

Theoretically, "they argue" and "They claim" can refer to two different pieces of material. At any rate, in order to live up to basic academic standards, the article authors should have documented what they are referring to with "they argue" and "They claim".

Dictionary lookup, 2016-05-01
http://www.thefreedictionary.com/claim

claim
[...]
tr.v.
[...]
3. To state to be true, especially when open to question

_____
(O) : PI-corral pruning statistics
[3] (Timo Virkkala's master's thesis "Solving Sokoban") p. 57:

:: As expected, the amount of nodes explored by the PI-corral-pruning-enhanced version of 
:: BFS solver is always smaller than that of the unenhanced one. Unfortunately, adding the 
:: enhancement slows down the processing speed in nearly every case (puzzles M4, M40, M90, 
:: M93, and M146 being the exceptions) and thus increases the solution time. Nevertheless, 
:: the BFS+PI solver still solves a third of the puzzles faster than the plain BFS solver.
::
:: While the IDDFS solver enhanced with the PI-corral pruning enhancement is much slower than 
:: the BFS solvers, it does surprisingly outperform the IDDFS+PP+IMO solver, which does not 
:: have the PI-corral pruning enhancement, on the majority of the puzzles. This does indicate 
:: that it might be a good addition to an iterativedeepening-based solver such as Rolling Stone.

_____
(P) : PI-corral pruning statistics
[4] (Brian Damgaard's "Scribbles"):

:: Statistics - SokEvo/107 - Forwards search - no packingorder
::
:: A. A* search + transposition table: 11974023 positions 51938064 pushes 65 seconds
::
:: B. A* search + transposition table + corrals: 4632203 positions 11918161 pushes 21 seconds
::
:: C. A* search + transposition table + precalculated deadlocks: 2030736 positions 7011203 pushes 11 seconds
::
:: D. A* search + transposition table + precalculated deadlocks + corrals: 1231376 positions 3299797 pushes 7 seconds 
::
:: It's astonishing that a rather general mechanism like corral-pruning (B. 21 seconds) 
:: is nearly as effective as a highly specialized mechanism like the precalculated deadlocks (C. 11 seconds). 

(The text does not explicitly mention that "Forwards search - no packingorder" means finding push-optimal solutions.)

_____
(Q) : PI-corrals and push-optimality

[4] (Brian Damgaard's "Scribbles"):

:: Dynamic deadlocks - hindsight approach 
:: [...]
:: Briefly explained:
::
:: Corrals are "fences" on the board built by a set of boxes. 
::
:: I-corrals are fences where all participating boxes only can be pushed inwards in the next push. 
::
:: PI-corrals are I-corrals where the player has access to all the outer boxes in the corral, 
:: so all their inwards pushes are legal moves in the current position. In other words, no outside 
:: boxes on the board blocks the player's access to the corral boxes. 
::
:: When there is a PI-corral on the board, the solver can prune all other box-pushes. 
:: The search narrows down to the corral boxes only. This follows from the facts:
::
:: 1) The corral has to be opened sooner or later anyway 
:: (provided not all boxes are located at goal squares, of course).
::
:: 2) Pushing a box inwards, into the corral, doesn't interfere with the ability to 
:: push outside boxes later. (This entails that PI-corral pruning even has the extremely 
:: pleasant property that it doesn't interfere with the push-optimality of a solution.) 

_____
(R) : A diagram example from [4], showing the difference between I-corrals and PI-corrals

[4] (Brian Damgaard's "Scribbles"):

:: A corral
:: 
:: ##### 
:: #__$_
:: #___$@
:: #__$_
:: ###__
:: 
:: An "I-corral" is a corral where all boxes in the outer fence only can move inwards in their first move. 
:: An example:
::
:: Here is an I-corral which also happens to be a "PI-corral", a term we'll introduce in a moment:
::
:: ##### 
:: #___$
:: #__$@
:: #__$_
:: ###__
:: 
:: Note how the corral in the first example wasn't an I-corral because the middle 
:: box could be pushed to a cell outside the corral.
:: 
:: A "PI-corral" is the important sub-class of the I-corrals where the player can 
:: reach all the outer corral boxes and perform all their legal inwards moves. 
:: The example above was a PI-corral but the concept is best illustrated by a counter-example:
::
:: An I-corral which isn't a PI-corral because of the outside blocking box:
::
:: ##### 
:: #___$
:: #__$@
:: #__$$
:: ###__
:: 
:: This example isn't a PI-corral because the player cannot push the 3rd box inwards; 
:: there is an outside box that blocks the access. 

_____
(S) : Selected Sokoban related references found in articles by the article authors

These references show that the article authors are well informed and up-to-date about Sokoban literature and programs. 

Title:
  Finding Optimal Solutions to Sokoban Using Instance Dependent Pattern Databases
Authors:
  André Grahl Pereira, Marcus Rolf Peter Ritt, Luciana Salete Buriol
URL retrieved 2016-05-12:
  https://www.aaai.org/ocs/index.php/SOCS/SOCS13/paper/download/7244/6244

Selected Sokoban related references:

Botea, A.; Müller, M.; and Schaeffer, J. 2002. Using abstraction for planning in Sokoban. In Computers and Games, 360–375. 

Culberson, J. C., and Schaeffer, J. 1998. Pattern databases. Computational Intelligence 14(3):318–334. 

Culberson, J. C. 1998. Sokoban is PSPACE-Complete. In Proceedings of the International Conference on Fun with Algorithms, 65–76. 

Damgaard,B. 2013. SokobanYASS. http://sourceforge.net/ projects/sokobanyasc/. 

Demaret, J.-N.; Lishout, F. V.; and Gribomont, P. 2008. Hierarchical planning and learning for automatic solving of Sokoban problems. In 20th Belgium-Netherlands Conference on Artificial Intelligence, 57–64. 

Junghanns, A., and Schaeffer, J. 1999. Domain-dependent single-agent search enhancements. In IJCAI, 570–577. 

Junghanns,A.,andSchaeffer,J. 2001. Sokoban:Enhancing general single-agent search methods using domain knowledge. Artificial Intelligence 129(1-2):219–251. 

Junghanns,A. 1999. PushingtheLimits:NewDevelopments in Single-Agent Search. Ph.D. Dissertation, University of Alberta. 

Meger, M. 2013. JSoko. http://sourceforge.net/projects/ jsokoapplet/. 

Takahashi, K. 2013. Takaken Solver. http://www.ic-net.or. jp/home/takaken/e/soko/. 


Title:
  Solving Sokoban Optimally using Pattern Databases for Deadlock Detection
Authors:
  André G. Pereira, Marcus Ritt, Luciana S. Buriol
URL retrieved 2016-05-12:
  http://www.lbd.dcc.ufmg.br/colecoes/eniac/2014/0090.pdf

Selected Sokoban related references:

[3] J. C. Culberson and J. Schaeffer, “Searching with pattern databases,” in Canadian Conference on Artificial Intelligence, 1996, pp. 402–416. 

[9] J. C. Culberson, “Sokoban is PSPACE-Complete,” in Fun With Algorithms, E. Lodi, L. Pagli, and N. Santoro, Eds., 1999, pp. 65–76. 

[10] A. Junghanns and J. Schaeffer, “Sokoban: Enhancing general single-agent search methods using domain knowledge,” Artificial Intelligence, vol. 129, no. 1–2, pp. 219– 251, 2001. 

[11] D. Dor and U. Zwick, “Sokoban and other motion planning problems,” Computational Geometry, vol. 13, no. 4, pp. 215–228, 1999. 

[12] A. Botea, M. Müller, and J. Schaeffer, “Using abstraction for planning in Sokoban,” in Computers and Games, 2002, pp. 360–375. 

[13] J.-N. Demaret, F. V. Lishout, and P. Gribomont, “Hierarchical planning and learning for automatic solving of Sokoban problems,” in Belgium-Netherlands Conference on Artificial Intelligence, 2008, pp. 57–64. 


Title:
  Solving Sokoban Optimally with Domain-Dependent Move Pruning
Authors:
  Leme, Renato R. 
  Pereira, André G.  
  Ritt, Marcus  
  Buriol, Luciana S. 
URL retrieved 2016-04-20:
  http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=7424030&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D7424030

Selected Sokoban related references:

Botea, A.; M¨uller, M.; and Schaeffer, J. 2002. Using abstraction for planning in Sokoban. In Computers and Games, 360–375. 

Culberson, J. C. 1998. Sokoban is PSPACE-Complete. In Proceedings of the International Conference on Fun with Algorithms, 65–76. 

Damgaard,B. 2013. SokobanYASS. http://sourceforge.net/ projects/sokobanyasc/. 

Demaret, J.-N.; Lishout, F. V.; and Gribomont, P. 2008. Hierarchical planning and learning for automatic solving of Sokoban problems. In 20th Belgium-Netherlands Conference on Artificial Intelligence, 57–64. 

Junghanns, A., and Schaeffer, J. 1999. Domain-dependent single-agent search enhancements. In IJCAI, 570–577. 

Junghanns,A., and Schaeffer,J. 2001. Sokoban:Enhancing general single-agent search methods using domain knowledge. Artificial Intelligence 129(1-2):219–251. 

Junghanns,A. 1999. Pushing the Limits:New Developments in Single-Agent Search. Ph.D. Dissertation, University of Alberta. 

Meger, M. 2013. JSoko. http://sourceforge.net/projects/ jsokoapplet/. 

Takahashi, K. 2013. Takaken Solver. http://www.ic-net.or. jp/home/takaken/e/soko/. 

_____
(T) : The authors of the solver programs JSoko and YASS have not been contacted by the article authors

T.1. Mr. Matthias Meger, the author of JSoko, has informed me by email that he has not been contacted by the article authors.

T.2. I, the author of YASS, have not been contacted by the article authors.

_____
(U) : A very different PI-corral description by one of the article authors
Title:
  Obtendo Soluções Ótimas para o Sokoban com Poda Dependente de Domínio
Author:
  Leme, Renato Reis 
URL retrieved 2016-05-14:
  http://hdl.handle.net/10183/113477

The document "Resumo_37793.pdf" says:

:: Evento Salão UFRGS 2014: SIC - XXVI SALÃO DE INICIAÇÃO CIENTÍFICA
:: DA UFRGS
:: Ano 2014
:: Local Porto Alegre
:: Título Obtendo Soluções Ótimas para o Sokoban com Poda Dependente de
:: Domínio
:: Autor RENATO REIS LEME
:: Orientador LUCIANA SALETE BURIOL
:: [...]
:: O PI-Corral é uma técnica de domínio específico criada por Matthias Meger
:: [...]
:: Um PI-Corral é um conjunto de pedras que cerca uma área não alcançável do mapa a
:: partir da posição atual do jogador. Essas pedras precisam atender a duas condições:
:: devem ser acessíveis, isto é, o jogador deve poder acessá-las a partir da sua posição atual,
:: e elas devem poder ser empurradas somente para dentro de uma zona imediatamente não
:: acessível pelo jogador.

Google translate, Portuguese -> English
URL retrieved 2016-05-14:
  https://translate.google.com/

:: Event Hall UFRGS 2014: SIC - XXVI INITIATION OF SCIENTIFIC HALL
:: OF UFRGS
:: year 2014
:: Location Porto Alegre
:: Title Getting Optimal Solutions for Sokoban with Poda Dependent
:: Domain
:: Author RENATO REIS RUDDER
:: Advisor LUCIANA SALETE BURIOL
:: [...]
:: The PI-Corral is a domain of technical speci fi c created by Matthias Meger 
:: [...]
:: A PI-Corral is a set of stones surrounding a not reachable area of the map to
:: from the current position of the player. These stones must meet two conditions:
:: must be accessible, that is, the player must be able to access them from your current position,
:: and they must be able to be pushed only in an area not immediately
:: accessible by the player.

The document is about the same material as the PI-corral article. The document predates the PI-corral article. Despite of small inaccuracies in the mechanical translation, the following facts are clear.

U.1. 
It is the author's intention to describe the PI-corral definition used by the Sokoban community. It is not the intention to introduce a new and deviating definition, even though that is what it does. The rest of the author's implementation of PI-corral pruning presumably operates with box sets matching this deviating definition, but that does not change the fact that the author's intention in this text is to describe Mr. Meger's PI-corral definition.

U.2.
This is not a description which matches the I-corral definition used by the Sokoban community (2.2.3, H, I, J).

U.3
This is not a description which matches the PI-corral definition used by the Sokoban community (2.2.4, H, I, J).

There is a small ambiguity in the text, so perhaps it could be read as a correct PI-corral description, but the four authors of the PI-corral article most certainly do not want that interpretation. Leme's text predates the PI-corral article, and if it contained a correct PI-corral description, then the article authors could not feign stupidity as an explanation for the misrepresentation of PI-corrals in the PI-corral article, and for their false claims of having discovered PI-corrals and PI-corral pruning themselves.

U.4.
This is not the same false description of PI-corrals as found in the PI-corral article. The latter presents I-corrals as if they were PI-corrals (see 4.2). But what Leme describes here is something completely different. There is a small ambiguity in the text, but it is fair to say that the text describes a subset of an I-corral, more precisely, the subset of boxes in an I-corral which the player can reach and push into the corral.

(Most readers of this document cannot be expected to be interested in such a technical and logical subtlety. Readers, who are not willing to spend the time and energy it takes to understand the fundamental difference, must take my word for it, as a practitioner in the field, when I say that the difference is as big as the difference between the color brown and a horse, taking into account that not all horses are brown.)

_____
(V) : Date of Publication of "Solving Sokoban" 
Mr. Timo Virkkala has informed me by email that his master's thesis "Solving Sokoban" [3] was published on the internet 2012-02-23 in connection with the following announcement on "Stack Overflow", a web site which according to its own description "is a question and answer site for professional and enthusiast programmers".

URL retrieved 2016-05-25:
  http://stackoverflow.com/questions/4237462/sokoban-solver-tips

:: I have written my Master's thesis on Sokoban algorithms. 
:: I aimed to provide a good overview on the techniques used in Sokoban solvers. 
:: It does not provide definite answers, but might provide a good starting point 
:: for someone interested in writing a Sokoban solver.
::
:: http://weetu.net/Timo-Virkkala-Solving-Sokoban-Masters-Thesis.pdf
::
:: answered Feb 23 '12 at 21:32
::
:: Weetu

_____
(W) : Forward pruning in early game-playing computer programs
Title:
  Toward an Analysis of Forward Pruning
Authors:
  Stephen J. J.
  Dana S. Nau
URL retrieved 2016-06-11:
   https://www.aaai.org/Papers/Symposia/Fall/1993/FS-93-02/FS93-02-004.pdf

The document says:
:: Several early game-playing computer programs used forward pruning 
:: (i.e., the practice of deliberately ignoring nodes that are believed 
:: unlikely to affect a game tree’s minimax value), but this technique 
:: did not seem to result in good decision-making.

_____
(X) : Informal Overview

Please note that this overview is very informal and intentionally sacrifices rigor for clarity.

_______________________________________________________________________________________________________
Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence

Four academics at a university in Rio, Brazil, published an article in 2015 about a programming mechanism (a so-called algorithm) of great importance for Sokoban solver programs. The article authors say that they have invented/discovered this mechanism.

There are just a few problems with the article.

_________________________________________________________________________________________________________
X.1. The idea is not new. The mechanism is Matthias Meger's brilliant PI-corral algorithm, from 2005!

Your first reaction is probably to think: 
- Sigh, how boring. Isn't this just one of those frequently occurring situations, where people independently get the same idea? Typically, the original discoverer, or somebody else (me, in this case) is just unhappy, if credits are not given where credits are due. 

No, not this time. The article authors fully admit in the article that they know about Matthias' idea. The article even describes the idea in great detail.

This must make you think:
- But how it that possible? The article authors cannot say that they know about Matthias' idea, and at the same time claim having invented the mechanism themselves?

Exactly. That is impossible. But the article authors have found a way out.

________________________________________________________________________________________________________
X.2. They misrepresent (dare I say "lie about"?) what it was, that Matthias discovered back in 2005!

Figuratively speaking, the article authors say that Matthias only discovered one side of the coin, and that his mechanism therefore is weak. The article authors have discovered that the coin has two sides. By looking at both sides, the article authors have been able to create a new mechanism, which is strong. So they say.

This must make you think:
- Maybe the article authors just misunderstood Matthias' idea? 

I'll return to that later, but first there is a more pressing matter. The story takes another bizarre turn, which you probably not have seen coming.

____________________________________________________________________________________________________________
X.3. To add insult to injury, they say that Matthias and I are idiots, who have not understood anything!

According to the article authors, Matthias and I have only seen one side of the coin, and we mistake the resulting weak algorithm for the strong algorithm, i.e., the algorithm created by the article authors after they discovered the second side of the coin!

After all the injustice already done to Matthias, I'm sad to say that as the petty person I am, this is the point where I go from a feeling of the utmost indignation on his behalf, to extreme and bloodthirsty rage. I don't like being called an unintelligent idiot, for the wrong reasons!

You surely wonder, why I suddenly appear in all this. The reason is, that I happened to write the first published, detailed description of Matthias' idea. My description is the article authors' only source of information, and therefore the article authors refer to Matthias and me as "they". 

So when the article authors say "they have only seen one side of the coin", and "they mistake the weak mechanism for the strong mechanism", then the article authors are in effect calling both Matthias and me for unintelligent idiots.

At this point, you may think:
- But isn't it rather easy for the readers of the article to find out that something is terribly wrong? After all, this is an academic article, and academic articles are always heavily underpinned with references to all the used material. So when the article readers inspect the referenced material, they'll immediately see what is wrong with the article, won't they?

You have probably already guessed the answer: No, not a chance!

It takes a little trickery to avoid the disclosure. It's a marvelous trick, which I didn't know about, and I can warmly recommend that you pay attention and learn, in case you also haven't seen it before. Maybe you can find a respectable usage for it some day.

_____________________________________________________________________________________________
X.4. How to avoid that fact-finding people smoke you out, when everything you say is false!

(Yes, I am also aware of the tautology in that heading. I just meant is sounded good anyway.)

As far as a crime story goes, this is not a good one because there is one crucial piece of the puzzle I haven't given you yet, and you cannot find the solution based on just the facts you already have. The missing piece will be revealed shortly, as a part of the trick recipe. The trick is best explained by taking the concrete article as an example.

X.4.1.
The article authors say that Matthias and I have implemented the weak mechanism in our respective solver programs, JSoko and YASS, but that we mistake it for the strong mechanism. (What we have implemented from the very beginning is, of course, the complete and strong mechanism.)

X.4.2.
The article authors put the JSoko and YASS projects on the article's list of references, as the only material related to Matthias' idea.

As an acute reader, you think:
- But then the fact-finding article reader can easily find out that the article is wrong, by a simple inspection of JSoko and YASS!?

If only it were so simple, but it isn't. It's time to reveal the secret ingredient. 

X.4.3.
The fact-finding article reader is in for a surprise. There is not a single sentence in JSoko and YASS about the algorithm, the article talks about! 

The reason is, that Matthias and I implemented the algorithm in our respective solvers a long time before the algorithm got its name, and by happenstance the name has not crept into the project's material in later versions. The name appeared in public for the first time in my description of the algorithm, which was put on a wiki on the internet ca. 2010. Here there were good chances that other programmers and academics would find it, and it worked. Already in 2011, Matthias' idea was given its first in-depth academic treatment in a master's thesis about Sokoban solver programming.

X.4.4.
Now think about the situation for our unfortunate fact-finding article readers. They can only assume that everything the article says about Matthias' idea can be substantiated by looking at JSoko and YASS, given that this is the article's only referenced material about the algorithm.

But when the article readers find nothing in JSoko and YASS about an algorithm with such a name, then the article readers will just conclude, that the article authors have used the word "they" in a broader sense, as a reference to even more, but unspecified, source material from the Sokoban community.

A more tenacious fact-finding article reader may dig deeper into JSoko and YASS and find out, that even though the name of the algorithm is never mentioned, both solvers do implement something which looks very much like what the article talks about. The only difference is, that the implemented algorithm is clearly the strong algorithm, and not the weak algorithm as the article authors said.

This makes the fact-finding article reader think:
- Aha, the projects must have been updated in the meantime from the weak algorithm to the strong algorithm, in light of the article authors' findings! 

What a marvelous trick! The deception comes full circle, and there is no chance that the fact-finding article reader finds out about the article authors' falsities. 

__________________________________________
X.5. Are they stupid, or are they lying?

If the article had made a reference to the description on the wiki of Matthias' idea, then they would have shown willingness to be subject to control. As it stands, the article readers are not given a chance to check the veracity of the article authors' falsities, so speculations about stealing and lying is inevitable, also because there are several pieces of circumstantial evidence pointing in that direction.

If the article authors aren't stealing and lying, then their article is a display of incompetence, stupidity, and indecency for a great many reasons.

X.5.1.
Nobody else have had problems understanding the description found on the wiki of Matthias' idea. The already mentioned master's thesis is a good example. It is inconceivable that as many as four article authors should have misunderstood it all.

X.5.2.
The article authors have not made any research whatsoever. Even if they had misunderstood the description on the wiki, they should immediately have realized their mistake after reading some of the other descriptions, including the description found in the already mentioned master's thesis.

X.5.3.
The article authors have not lifted a finger to check if JSoko and YASS really just implemented the weak algorithm. A quick look at the projects' material would immediately have revealed that JSoko and YASS implement the strong algorithm.

X.5.4.
If the article authors really thought that JSoko and YASS were flawed, then at least one of four authors could be expected to do what every normal and decent person would have done after having written an article about it, namely to alert Matthias and me about the problem.

X.5.5.
At last we come to the amusing and ironic culmination. The article authors claim having developed the strong algorithm, but the algorithm they present is flawed! An important ingredient is missing from their definition, so it is not the promised strong algorithm. When that ingredient is added, then the resulting algorithm is, of course, Matthias' idea! 

What a happy end, with a good laugh!
_______________________________________________________________________________________________________

_______________________________________________________________________________________________________
End of text document
Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence.txt
_______________________________________________________________________________________________________
Personal tools