The A* algorithm for decoding linear block codes is known to be an efficient tree-search method for decoding short linear block codes. We propose to employ the early acquired information of some parity bits to speed up the tree search. Analysis for the number of required information bits for obtaining the parity bits is provided. In addition, two versions of the modified A* algorithm which take advantage of the advanced information of parity bits are provided. Simulation results show that there is advantage in reducing the number of search tree edges in each proposed version as compared with two existing A* algorithms which do not consider the early information of parity bits.