The Minority Game (MG) is a prototypical model for an agent-based complex adaptive system. In MG, an odd number of heterogeneous and adaptive agents choose between two alternatives and those who end up on the minority side win. It is known that if $N$ agents play MG, they self-organize to a globally efficient state when they retain the memory of the minority side for the past $m \sim \log_2(N)$ rounds (Challet & Zhang 1997). However, the global efficiency becomes extremely low when the memory of the agents is reduced i.e, when $m << \log_2(N)$. In this work, we consider an MG in which agents use the information regarding the exact attendance on a side for $m$ previous rounds to predict the minority side in the next round. We show that, when employing such strategies, independent of its size, the system is always in a globally efficient state when the agents retain two rounds of information ($m=2$). Even with other values of $m$, the agents successfully self-organize to an efficient state, the only exception to this being when $m=1$ for large values of $N$. Surprisingly, in our model, providing the agents with a random $m=1$ fake history results in a better efficiency than real histories of any length.